2023-12-13 PS 공부

오랜만에 업다운랜디를 돌렸다.

 

 

21276: 계보 복원가 호석(G2, Tree)

 

시간 안엔 못 풀었다.. 자신의 조상 노드가 문제에서 주어지므로, 맵(map<string, set<string>>)에 자신의 조상 노드를 모두 담고, 조상 노드를 순회하면서 set의 크기가 자신보다 1 작은 것이 있으면 해당 노드가 자신의 부모 노드가 된다. 부모 노드가 없다면 루트 노드가 되고, 가문의 개수는 루트 노드의 개수와 같다. 이를 이용해 시간복잡도 O(N^2logN)에 계산할 수 있다.

 

별해) 입력받을 때, 자신보다 깊이가 깊은 노드들에 대해 위에서 아래로 가는 단방향 간선을 만들어준다. 이후 위상 정렬을 수행하면 역시 시간복잡도 O(N^2logN)에 해결할 수 있다!

 

 

2492: 보석(G3, Brute-Force)

 

풀이가 전혀 떠오르지 않아서 그냥 답을 봤다 ㅠㅠ

어떠한 최적 위치에 대해서, 아래쪽 변과 왼쪽 변에 가까운 두 점에 정사각형을 밀착시켜도 포함되는 점의 개수는 줄어들지 않는다. 따라서 두 점을 잡고 돌리는 브루트포스와 간단한 예외처리를 이용해 풀이할 수 있다.

 

 

3055: 탈출(G4, BFS, 10:55)

 

4179번 불! 문제와 동일한 문제이다. 물부터 BFS를 돌린 후, 비버의 BFS를 돌리면 깔끔하게 구현할 수 있다.

 

 

16724: 피리 부는 사나이(G3, Union Find, 15:44)

 

답은 그래프의 컴포넌트 개수가 되고, 이는 유니온 파인드로 구현할 수 있다. dfs 스패닝 트리의 back-edge로 푸는 방법도 있는 것 같다. 나중에 공부해 봐야지...

 

 

1222: 홍준 프로그래밍 대회(G2, 정수론)

 

문제를 잘 변형하면 1부터 N까지의 숫자 중 약수-배수 관계에 있는 모든 수 쌍을 세는 문제로 만들 수 있다.

이러한 쌍의 개수는 (N/1) + (N/2) + ... + (N/N)이고, 조화급수의 합은 logN으로 수렴하므로 총 시간복잡도는 NlogN이 된다!

코포에서 보던 테크닉인데 백준에서는 처음 본 것 같다.

 

 

2306: 유전자(G3, DP, 16:37)

 

올바른 괄호쌍 느낌 dp이다. dp[i][j]: i번 인덱스부터 j번 인덱스까지의 가장 긴 KOI 유전자의 길이로 잡으면 O(N^3) dp로 해결할 수 있다.