Hyun's_Devlog

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

풀이 방법

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

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

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

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

정답 코드

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

최단거리 탐색 알고리즘으로 접근한 문제다. 

풀이

특정 정점에서 다른 정점까지의 최단거리를 계산하는 다익스트라 알고리즘을 사용했다. 이때 핵심은 주어지는 T의 범위가 40,000이라는 점이다. 즉 매 연습마다 40,000번의 그래프 탐색이 일어난다면 시간초과로 이어진다.

정점의 개수 N이 최대 300이며 간선의 최대 개수는 25,000인 점을 고려한다면 이전에 사용했던 정보가 중복으로 요구된다는 합리적인 결론에 도달한다.

따라서 다익스트라 알고리즘을 구현한 뒤 결과 값을 저장할 수 있는 <시작점, 각 정점까지의 최단거리> 형태의 딕셔너리를 생성하여 이전에 요구한 적 없는 시작점이 주어진다면 다익스트라 알고리즘을 통해 해당 결과를 저장한다. 반대로 이전에 요구한 적이 있던 시작점이라면 해당 시작점으로부터의 최단거리 정보는 이미 저장되어 있으므로 바로 출력이 가능하다.

즉 매 횟수마다 최단거리를 계산할 경우 O(4,000 * 25,000)의 시간복잡도로 인해 시간초과가 일어나겠지만, 모든 정점에서 다익스트라 알고리즘을 미리 수행한 결과를 이용한다면 O(300 * 25,000)의 시간복잡도로 시간 단축이 가능하다는 얘기다.

정답 코드

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) 의 시간복잡도를 통해서 해당 문제를 해결할 수 있다.

정답코드

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

최단거리 탐색 문제다. 다익스트라 알고리즘으로 접근했다.

풀이

접근 가능한 정점과 N-1번 정점을 이어주는 간선들만 저장했다.

swift에는 다른 언어들과 달리 Heap이 구현되어있지 않아서 일반적인 경우에는 일반 큐를 사용하여 매 순환마다 정렬 작업을 하여 탐색하였는데 이번 문제는 간선정보가 최대 300,000개가 주어지므로 Heap 구현이 필요했다.

그런데 마주한 시간초과. 질문게시판을 찾아보니 다익스트라 알고리즘의 원리를 잘 고민하면 우선순위 큐를 더 빠르게 탐색이 가능하다고 한다. 

우선 다익스트라 알고리즘은 비용이 낮은 순으로 정렬된 우선순위 큐를 탐색하여 매 순간 각 정점으로의 최소비용을 갱신하게 된다.

즉, [현재 정점의 최소비용 + 현재 정점에서 다음 정점까지의 비용] 계산을 통해 다음 정점의 최단거리 정보를 갱신하는데, 이때 우선순위 큐에서 꺼낸  현재 정점의 정보가 최소 비용이 아니라면 결국 다음 정점까지의 정보를 탐색할 필요가 없다는 얘기다.

따라서 매 탐색마다 최단거리 정보를 담고 있는 cost[curr]와 우선순위 큐에 담겨있는 curr.cost 와의 비교를 통해서 최단거리보다 큰 비용이라면 continue를 통해 시간단축이 가능하다.

정답 코드

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

유니온파인드와 그래프탐색으로 접근했다.

풀이

모든 정점을 방문하게 된다면 시간초과가 일어난다.

예제를 보면 3~1, 3~5, 3~4, 3~2, 6~4, 6~2 총 6개의 구간이 정답이다.

검은색 정점을 시작으로 빨간색 정점으로만 이어지는 경로의 개수. 즉 우리는 연속되는 빨간색 정점을 컴포넌트로 묶어 개수를 미리 저장해 놓으면 보다 빠르게 탐색이 가능해진다.

따라서 인접한 빨간색 정점끼리는 유니온을 통해 하나의 컴포넌트로 묶어내어 개수를 저장하고, 컴포넌트에 인접한 검은색 정점의 개수를 파악하면 해당 컴포넌트에서 발생되는 누텔라 트리의 개수를 구할 수 있게 된다. 

해당 과정은 bfs를 통해 O(N)만에 정답을 구할 수 있다.

정답 코드

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

그래프 탐색과 유니온파인드로 접근했다.

풀이

정점 N개와 간선 N개를 가진 트리는 한 개의 사이클을 가지고 있는 트리이다. 따라서 정점 u에서 v로 가는 경로가 사이클을 거쳐가게 된다면 경로는 2개가 되고, 경로에 사이클이 없다면 경로는 1개가 되는 것이다.

따라서 사이클에 속해있는 정점을 파악한 뒤 유니온 파인드를 수행하다. 연결하려 하는 두 정점의 경로가 사이클에 속한 경로라면, 정점을 연결하지 않고 넘어간 뒤, 쿼리가 주어질 때, 두 정점의 부모가 같다면 1 아니면 2를 출력하면 정답이다.

주어진 예제를 통해 보면 정점 1 - 2 - 3으로 사이클이 이루어진다. 따라서 정점 1, 2, 3 사이의 간선을 없애고 쿼리에서 서로 다른 컴포넌트의 경로를 물어보면 해당 경로는 사이클을 통한 경로가 있다는 뜻이므로 2를 출력, 같은 컴포넌트 내의 경로를 물어보면 1을 출력하면 된다.

사이클 검출은 진입차수가 1인 정점부터 너비 우선 탐색을 수행하여 찾아내었다. 

정답 코드

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

유니오 파인드와 그래프 탐색으로 접근했다.

풀이

2차원 지도를 1차원 배열로 매핑한 뒤 지도에 적힌 움직임 대로 그래프 탐색을 수행한다.

탐색을 수행하면서 현재 위치와 다음으로 이동할 위치의 번호끼리 합병해 주면 된다.

컴포넌트의 개수를 출력해 주면 정답이다.

단, 중복 방문을 막는 과정에서 실수하여 WA를 받았다.

반례는 문제에 주어진 예제를 보고 생각해 냈다.

3 4

SWWW

SEEN

EEEN

방문했던 위치여도 아직 방문하지 않은 곳에서 진입이 가능하기에 방문했던 위치도 무조건 유니온 동작을 수행해야 한다.

정답 코드

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

유니온 파인드로 접근했다.

풀이

원수를 담는 배열 enemy 2차원 배열을 생성하여 원수 관계가 들어오면 양방향으로 추가.

친구 관계가 입력되면 유니온을 통해 컴포넌트를 합친다.

모든 입력이 들어오고 나면 enemy 배열을 탐색하면서 원수의 원수를 찾아 서로 연결해 주면 된다.

남아있는 컴포넌트의 개수를 출력하면 정답이다.

정답 코드