Hyun's_Devlog

https://www.acmicpc.net/problem/7211

유니온 파인드의 기본 문제다.

풀이 방법

입력되는 간선 정보를 저장한다.

이때 국가소유의 간선인지 아닌지 또한 저장해야 한다.

간선정보를 비용순서로 정렬. 모든 단선을 탐색하며 유니온 과정을 수행한다.

• 해당 간선이 국가소유의 간선이며 최소 스패닝 트리에 포함되어야 하는 간선이라면 비용을 0으로 하여 필요한 비용으로 추가한다.
• 해당 간선이 국가소유의 간선이지만 최소 스패닝 트리에 포함하면 안 되는 간선이라면 해당 간선의 비용을 필요한 비용에서 빼준다.
• 국가소유의 간선이 아니라면, 최소 스패닝 트리에 포함되는지 여부를 확인한 뒤 필요한 비용에 반영하면 된다.

필요한 비용이 0보다 작다면 0을 출력. 그 이상이라면 해당 비용을 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/3271

번역기능으로 문제를 봐도 이해되지 않아 헤맸다. chatGPT를 통해 번역과 설명을 보고 나서 이해하여 정답을 받았다..

기본적인 최소 스패닝 문제.

풀이 방법

B마리의 벌들이 F개의 꽃을 최소 스패닝 트리로 구성하여 각 구역을 분담하여 탐색하게 된다. 이때 각 벌들이 분담받은 이동 경로 중 한 번에 가장 많이 이동한 거리의 최솟값을 출력하라는 얘기.

따라서 크루스칼 알고리즘을 컴포넌트가 B개가 될 때까지 진행하고, 이때까지 가장 많이 이동한 거리를 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/17090

그래프 탐색 문제. 시간초과를 해결하지 못해 결국 풀이를 찾아보았다.

풀이 방법

배열 범위 밖으로 탈출할 수 있는 노드의 수를 반환해야 한다.

단순히 깊이우선으로 모든 노드에 수행하게 되면 시간초과가 일어난다.

미로의 각 칸에서 넘어가는 다음 칸은 지정되어 있다. 따라서 이미 탐색을 수행한 노드의 끝이 맵 밖으로 이어지는지,  아니면 맵을 탈출 하지 못하고 사이클을 형성하는지 미리 저장해 둔다면 시간 내에 정답을 반환할 수 있다.

미로와 같은 크기의 N*M 2차원 visited 배열 생성. 특정 좌표를 아직 탐색하지 않았다면 -1, 해당 좌표가 탈출하지 못하는 좌표라면 0, 미로를 탈출할 수 있는 좌표라면 1을 저장한다.

깊이 우선 탐색을 수행. 다음 좌표가 미로 밖이라면 1 반환. 아닌 경우에는 처음 방문 좌표인지 확인하여 처음 방문 하는 곳이라면 (-1) 다음 좌표로 재귀호출이 이루어지며 해당 좌표에 결괏값이 저장된다. 

탐색을 통해 1의 개수를 정답으로 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/13397

이분탐색으로 접근했다.

풀이 방법

배열의 크기 N이 최대 5000으로 작은 값에 속한다. 따라서 이분탐색으로 찾게 될 값은 구간의 최대 점수를 찾는 문제로 접근했다.

즉 이분탐색으로 mid값을 고정하고 길이 N의 배열을 순차탐색하면서 탐색 중인 구간의 최댓값 - 최솟값이 mid보다 크다면 구간을 나누어 마지막까지 탐색이 끝났을 때 구간의 개수가 M이하라면 최대 점수를 더 낮은 쪽을 탐색, 개수가 M보다 크다면 최대 점수가 더 큰 쪽으로 이분 탐색을 이어가면 된다.

입력 예제를 기준으로 동작을 그림으로 나타내면 다음과 같다. 이분탐색 mid 값이 3, 5, 4 일 경우 각각의 구간의 개수 조건을 확인. 구간의 최댓값이 5일 경우에 조건을 만족하므로 5가 정답이 된다.

정답 코드

https://www.acmicpc.net/problem/8983

이분탐색으로 접근했다.

풀이 방법

주어지는 사대의 위치를 오름차순으로 정렬한다.

이후 주어진 각 동물의 좌표를 기준으로 사대의 위치 0부터 M-1까지 이분탐색을 통해 사격 거리 L에 포함되는지를 확인하였다.

이때 사격거리 L에 포함되지 않는다면 동물의 위치가 비교한 사대보다 왼쪽이라면 즉 (동물의 x축 좌표 < 사대의 x축 좌표)이라면, 현재 사대보다 더 왼쪽에 위치한 사대를 탐색하면 되고, 그 반대라면 보다 오른쪽에 위치한 사대를 탐색하면 된다.

해당 방법으로 접근한다면 O(100,000 * log100,000) 즉 O(500,000)에 탐색이 가능하다.

정답 코드

https://www.acmicpc.net/problem/17471

조합을 통한 완전탐색 + 유니온파인드로 접근하였다.

접근 방법

입력으로 주어지는 구역의 최대개수는 10이다. 따라서 각 구역이 두 가지 선거구로 선택되는 경우의 수를 계산하면 2^10 즉 1024의 경우의 수가 발생. 이후 각 조건에서 유니온 파인드를 수행한다.

유니온 파인드에서 두 노드가 결합되는 조건은 서로 인접하며 정해진 선거구가 같은 경우만 결합하는 것으로 하였다. 마지막으로 컴포넌트의 수가 2인 경우만 각 선거구의 인구수를 확인하여 정답을 반영하면 된다.

정답 코드

https://www.acmicpc.net/problem/1700

풀이 방법

핵심은 콘센트가 가득 차있을 경우 어떤 전기용품을 뺄지를 결정하는 것이다.

정답은 앞으로 사용하지 않을 기기 혹은 앞으로 사용할 예정인 기기로 가득 차있는 경우라면 그중에서 가장 나중에 사용할 기기를 빼면 된다.

질문게시판에 좋은 예제가 있어 해당 예제로 설명하면 다음과 같이 동작한다.

3 10
1 2 3 4 4 5 2 1 1 4

정답 코드

https://www.acmicpc.net/problem/5582

처음엔 길이가 짧은 문자열에서 부분문자열을 뽑아낸 뒤 길이가 긴 문자열에 포함되는지 여부를 통해서 접근했지만 당연하게도 시간초과.

동적계획법 태그를 보고서 접근법을 생각해 봤지만 결국 풀이를 찾아봤다. 점화식부터 말하면 다음과 같다.

dp[i][k] = dp[i-1][k-1] + 1

여기서 2차원 배열 dp는 해당 위치의 문자로 끝나는 공통 부분 문자열의 길이를 뜻한다.

풀이

문자열 A = "AACD"와 문자열 B = "SSAB"를 기준으로 설명하면 다음과 같이 작동한다.

문자열 A의 길이 N, 문자열 B의 길이 M 일 때, (N+1)*(M+1) 크기의 2차원배열 dp를 생성. 0으로 초기화한다.

1부터 N, 1부터 B까지 2중 반복문을 탐색하면서 점화식을 통해 계산한 값 중 최댓값이 정답이다.

두 문자열의 i번째와 k번째 문자가 일치했다는 것은 두 문자열의 i-1번째와 k-1번째 문자로 끝나는 공통 부분 문자열에 현재 문자를 이어 붙여 한 글자 더 긴 공통부분 문자열을 만들 수 있다는 뜻이 된다.

즉 O(N*M) 의 시간복잡도를 통해서 해당 문제를 해결할 수 있다.

정답코드