오랜만에 업다운랜디를 돌렸다.
시간 안엔 못 풀었다.. 자신의 조상 노드가 문제에서 주어지므로, 맵(map<string, set<string>>)에 자신의 조상 노드를 모두 담고, 조상 노드를 순회하면서 set의 크기가 자신보다 1 작은 것이 있으면 해당 노드가 자신의 부모 노드가 된다. 부모 노드가 없다면 루트 노드가 되고, 가문의 개수는 루트 노드의 개수와 같다. 이를 이용해 시간복잡도 O(N^2logN)에 계산할 수 있다.
별해) 입력받을 때, 자신보다 깊이가 깊은 노드들에 대해 위에서 아래로 가는 단방향 간선을 만들어준다. 이후 위상 정렬을 수행하면 역시 시간복잡도 O(N^2logN)에 해결할 수 있다!
풀이가 전혀 떠오르지 않아서 그냥 답을 봤다 ㅠㅠ
어떠한 최적 위치에 대해서, 아래쪽 변과 왼쪽 변에 가까운 두 점에 정사각형을 밀착시켜도 포함되는 점의 개수는 줄어들지 않는다. 따라서 두 점을 잡고 돌리는 브루트포스와 간단한 예외처리를 이용해 풀이할 수 있다.
4179번 불! 문제와 동일한 문제이다. 물부터 BFS를 돌린 후, 비버의 BFS를 돌리면 깔끔하게 구현할 수 있다.
16724: 피리 부는 사나이(G3, Union Find, 15:44)
답은 그래프의 컴포넌트 개수가 되고, 이는 유니온 파인드로 구현할 수 있다. dfs 스패닝 트리의 back-edge로 푸는 방법도 있는 것 같다. 나중에 공부해 봐야지...
문제를 잘 변형하면 1부터 N까지의 숫자 중 약수-배수 관계에 있는 모든 수 쌍을 세는 문제로 만들 수 있다.
이러한 쌍의 개수는 (N/1) + (N/2) + ... + (N/N)이고, 조화급수의 합은 logN으로 수렴하므로 총 시간복잡도는 NlogN이 된다!
코포에서 보던 테크닉인데 백준에서는 처음 본 것 같다.
올바른 괄호쌍 느낌 dp이다. dp[i][j]: i번 인덱스부터 j번 인덱스까지의 가장 긴 KOI 유전자의 길이로 잡으면 O(N^3) dp로 해결할 수 있다.
'PS > 공부' 카테고리의 다른 글
| 2024-03-19 PS 공부 (1) | 2024.03.19 |
|---|---|
| 2024-01-21 PS 공부 (1) | 2024.01.21 |
| 2023-12-06 PS 공부 (0) | 2023.12.06 |
| 2023-12-03 PS 공부 (0) | 2023.12.04 |
