Hyun's_Devlog

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

다이나믹 프로그래밍 문제다.

풀이

우선 1부터 6까지 1,2,3을 이용한 대칭 수식을 생각하면 점화식을 위한 조건이 만들어진다.

7부터는 앞서 생각한 경우의 수식에 양쪽으로 1+...+1, 2+...+2, 3+...+3의 형태로 대칭으로 늘려나가면 된다.

즉 dp[num] = dp[num-2] + dp[num-4] + dp[num-6]이라는 점화식을 세울 수 있다.

7부터 100,000까지 반복문을 돌려 정답배열을 만든후 입력값을 인덱스로 정답을 출력하면 된다.

정답 코드

점화식을 세우는건 항상 어렵다..,

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

너비우선탐색으로 접근한 문제다.

풀이

입력받은 지뢰의 충격이 큰 순서부터 터트리면서 너비우선탐색을 수행한다. 이때 터트리는 지뢰의 번호를 입력받은 뒤 오름차순으로 정렬하여 출력하면 된다.

정답 코드

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

누적합과 이분 탐색을 통해 접근하였다.

풀이

두 배열의 누적합을 통해 부 배열을 생성, 두 개의 부 배열 중 하나의 부 배열을 오름차순 정렬한 뒤 이분 탐색을 수행, (T - 다른 부배열의 원소) 값을 찾아낸다면 해당 값의 개수만큼 정답을 추가하여 마지막에 출력하면 된다.

정답 코드

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

유니온 파인드와 플로이드 와샬로 접근 가능한 문제다. 문제 속 함정에 걸려 시간을 많이 소비한 문제다. 문제를 꼼꼼히 읽도록 하자.

풀이

입력받은 간선 정보를 통해 유니온 파인드를 통해 컴포넌트를 구분, 2차원 배열을 통해 각 노드 간의 거리를 갱신한다. 입력이 완료되면 플로이드 와샬 알고리즘을 통해 각 노드 간의 최소거리를 구한다. 

유니온 파인드를 통해 알게 된 루트 노드를 입력하면 해당 컴포넌트의 최소 의사전달시간을 구하면 된다. 여기서 주의할 점은 문제에 주어진 "위원회에서 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록"이라는 부분이다. 해당 부분이 무엇인지 잘 생각하고 접근해야 한다.

다음으로 주의할 점은 "각 위원회의 대표 번호를 작은 수부터 차례로 한 줄에 하나씩 출력한다." 부분이다. 처음에 아무 생각 없이 0부터 n까지 순번으로 탐색하면 당연하게 순번대로 출력이 될 거라고 생각했으나, 낮은 순번의 루트를 호출하여 더 높은 번호가 대표가 되는 경우가 존재한다. 결국 대표의 번호를 따로 담아 정렬한 뒤에 출력해주었다.

정답 코드

조건에 대한 이해력이 너무나도 중요한 문제였다.

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

유니온 파인드 문제다. 문제는 같지만 입력 범위가 넓은 14595 문제를 풀다가 시간 초과하여 범위가 좁은 해당 문제부터 풀어보았다.

풀이

들어온 입력에 맞게 범위 단위로 유니온을 해준뒤 루트의 개수를 세면 된다. x < y 라는 조건이 있으니, x의 루트만 찾아낸 후 x+1 ~ y 범위까지 전부 x의 루트로 변경하면 된다.

정답 코드

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

유니온 파인드 문제다. 오일러 경로를 이용해야 한다.

풀이

문제에서 주어지는 것은 모든 간선을 한 번에 이용하면서 모든 노드의 순회가 가능하냐는 것이다. 즉 주어진 도형을 한 손 그리기가 가능하냐로 생각이 가능하다. 

이에 관한 공식이 있는지 찾아보았는데, '오일러 경로'에 대한 자료를 찾을 수 있었다. 각 노드의 진입, 진출 차수의 합이 짝수이면 한붓그리기가 가능하며, 예외적으로 차수가 홀수인 것이 2개라면 한붓 그리기가 가능하다고 한다.

차수가 홀수인 것이 0개 또는 2개라면 한붓그리기가 가능하다

따라서 문제에서 요구하는 것을 요약하자면, 모든 정점이 하나의 컴포넌트인지, 그렇다면 각 노드의 차수가 홀수인 경우가 0 또는 2라면 해당 그래프는 퍼레이드가 가능한 그래프인 것으로 출력하면 된다.

정답 코드

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

최소 스패닝 트리 문제다. 단 여기서 간선의 비용이 최대가 되게 구하면 된다. 주의할 점은 숭이가 위치한 곳과 혜빈이가 위치한 곳이 다리로 연결된다는 보장이 없다는 것을 숙지하고 풀어야 한다. 이것 때문에 오답 판정을 받았다.

풀이

입력되는 간선의 가중치, 즉 무게가 높은 순으로 간선의 정보를 정렬한 뒤, 가중치가 높은 순서로 유니온을 수행한다. 유니온을 수행할 때마다 들고 갈 수 있는 빼빼로의 무게를 작은 값으로 갱신, 마지막으로 숭이와 혜빈이의 위치가 같은 컴포넌트에 속해있는지 확인한 후, 같은 컴포넌트가 아니라면, 빼빼로를 전달할 수 없는 것이므로 0을 출력, 같은 컴포넌트가 맞다면 갱신해온 무게 값을 출력하면 된다.

정답 코드

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

유니온 파인드 문제다. 추가적으로 그래프 탐색을 통해 접근했다.

풀이

문제에 "지도 밖으로 나가는 방향은 주어지지 않는다"는 입력 조건이 있다. 그 얘기는 주어지는 좌표 어느 부분이던 탐색 시 무조건 사이클이 일어난다는 것이고, 문제의 답은 사이클이 일어나는 영역에 하나씩 "safe zone"을 설치하면 된다는 이야기. 요약하자면 깊이 우선 탐색을 통해 유니온파인드를 통해 컴포넌트의 개수를 반환하면 되는 것이다.

예제의 입력을 기준으로 사이클이 일어나는 영역을 색으로 표시해 놓았다. 두 개의 구역으로 나뉘며, 구역 하나당 하나의 "safe zone"을 설치하면 최소 개수를 구할 수 있다.

고민했던 점은 유니온을 할 때, 어떻게 구별하느냐인데, 이전에 풀었던 문제에서 2차원 배열을 번호로 매겨서 1차원 배열에 대입하여 풀었던 기억이 나서 그 부분을 사용했다. 즉 깊이 우선 탐색을 하면서 해당 위치의 번호와 다음 위치의 번호를 유니온, 루트가 같다면 종료. 모든 좌표에 대해서 깊이 우선 탐색을 수행한 뒤, 컴포넌트의 개수를 출력해주면 된다.

정답 코드