말하는 컴공감자의 텃밭

보호되어 있는 글입니다.

보호되어 있는 글입니다.

먼저 사람 수와 파티의 수가 주어진다.진실을 아는 사람들이 주어지고, 이후에 파티에 참가하는 인원이 주어진다.거짓말을 하려면 해당 파티에 진실을 아는 사람이 없어야 한다. 간단한 문제지만 구현을 어떻게 할지 고민이 됐다. 먼저 진실을 아는사람이 파티에 존재한다면, 해당 파티에 있는 사람은 모두 진실을 듣게된다.해당 파티에 진실을 모르고 있던 사람들을 진실을 아는 집단에 추가하여 업데이트한다.이후 진실을 아는사람이 없는 파티마다 정답에 ++ 해주면 된다. 따라서 진실을 아는사람을 큐에 넣고, 각각의 사람에게 어떤 파티를 참여했는지 정리한다.BFS를 통해 해당파티에 진실을 아는 사람이 있다면 해당 파티에 있는 전원을 진실 집단에 추가한다.해당 파티를 visited 를 통해 진실된 사람이 있는지 체크해주고 마..

오늘은 해장 알고리즘..비전공자와 함께 토크토크하며 시작합니다..  문제를 정리하면 배열이 주어지고, 해당 배열에서 3가지를 선택해서 0에 가장 가깝게 만드는게 관건이다.입력은 3  🔹 인풋은 5,000 숫자 세개를 모두 탐색하게되면 N³. = 125,000,000,000 이 된다.시간 제한 1초, 10⁸ 안팎이어야 하므로 이분탐색을 활용해서 시간을 log 대로 줄여보자. 해결 프로세스1. 숫자를 정렬하자.2. 두개를 먼저 이중 포문으로 고정하자.3. 나머지 숫자는 고정된 값 + 탐색하는 값으로 0과 가까운지 확인하며 이분탐색으로 찾자.4. 저장된 용액보다 0과 가깝다면 업데이트 해자.5. 0을 만들거나, 모든 경우의 수를 따졌다면 최적의 결과를 출력하자. 정렬에 N log N, 이중 포문 N², 이진..

정점과 가중치가 존재하는 간선이 주어진 상태에서 우리는 모든 정점을 가장 적은 비용으로 연결한 그래프를 최소 신장 트리라고 말한다. MST(Minimum Spanning Tree) 라고 말하며 이러한 문제에서 사용되는 알고리즘이 바로 프림과 크루스칼 알고리즘이다. 같은 목적을 지니고 있지만 접근방식이 조금 다른데 유념해서 알아보자 프림 알고리즘한 정점에서 시작해서 연결된 간선들 중 가장 가중치가 낮은 간선을 선택하며 트리를 확장하는 방식이다.시작점에서 점진적으로 최소 스패닝 트리를 완성해 나가는 그리디한 방식인데 순서는 다음과 같다.  초기화:임의의 정점을 선택해 시작한다.선택한 정점을 기준으로 연결된 간선 중 가중치가 가장 작은 간선을 선택한다.트리 확장:선택된 간선에 연결된 정점을 트리에 추가한다.이..

최소 스패닝 트리  최소 스패닝 기본 문제이다.모든 정점이 연결되어야 하고, 각 연결된 간선이 최소값으로만 구성이 되어야 한다.크루스칼과 프림 알고리즘으로 해결할 수 있는데, 두가지로 풀어보았다.🔽 알고리즘 차이점 확인https://hb-in99.tistory.com/191 최소 신장 트리를 위한 프림, 크루스칼 알고리즘정점과 가중치가 존재하는 간선이 주어진 상태에서 우리는 모든 정점을 가장 적은 비용으로 연결한 그래프를 최소 신장 트리라고 말한다. MST(Minimum Spanning Tree) 라고 말하며 이러한 문제에서 사hb-in99.tistory.com  프림 알고리즘 1234567891011121314151617181920212223242526272829303132333435363738394..

마인크래프트 문제를 요약하면 땅을 평평하게 하고 싶다.N x M 크기의 맵이있고, 내 인벤토리엔 B 개수의 블럭이 주어진다.맵의 숫자만큼의 높이로 블럭이 쌓여져 있고, 쌓는데 1초, 치우는데 2초가 걸린다.블럭이 존재하지 않다면 더이상 사용할 수 없고, 블럭을 치우면 인벤토리에 들어오게 된다. 모든 땅의 높이가 같게하는 방법에서 가장 최단 시간을 구하고,동시간대가 존재한다면 가장 높이 쌓은 높이를 출력하면 된다. 높이가 기본적으로 0부터 256까지이고 음수가 될수 없어 범위는 0 이다.시간계산이기 때문에 임의의 높이 X를 정하고, X를 기준으로 시간을 계산해 주었다.X보다 낮은 높이의 땅이라면 1 * (X - (현재 땅의 높이))X보다 높은 높이의 땅이라면 2 * Math.abs(X - (현재 땅의 높..

도시 분할 계획  마을에는 경로가 존재하고, 분리해서 이 경로를 없애면서 유지비용을 최대한 줄이는 문제다.마을 내부에서 서로 다른 집을 방문할 수 있어야하고, 마을이 분리됐다면 분리된 마을끼리는 연결되지 않아도 된다.이게 말로만 풀어쓰니까 이게 무슨..? 싶은데 그림으로 정리하면 편하다. 파란 부분을 A마을, 붉은 부분을 B마을이라고 하자,A 마을끼리 모두 연결되어 있고, B 마을끼리 모두 연결되어 있다.A와 B 마을 사이에 연결되는 부분이 오늘 문제의 포인트다.분할되는 부분이기 때문에 유지비가 들지 않는다.그림을 다시보면 모든 점이 연결된 그래프고, 우리는 유지비를 최소한으로 유지하고 싶으므로많은 경로가 존재한다면 그 중 유지비가 적은 값으로 연결을 시켜야 할것이다. 결국 이건 학부때 배웠던 최소 스패..