매일 3개의 주제를 골라 문제를 풀어봅시다.
- 트리에서의 다이나믹 프로그래밍
- 분할 정복
- 큐
트리에서의 다이나믹 프로그래밍
- 문제 : 사회망 서비스(sns)
- 난이도 : Gold 3
- 해설
- 참조한 풀이 : https://minhamina.tistory.com/98
- 처음으로 마주한 트리에서의 다이나믹 프로그래밍 문제입니다.
- 해결하지 못한 문제입니다. 위 풀이를 참조하여 해결했습니다. 해결하지 못했으므로 다른 문제를 하나 더 풀 것입니다.
- 문제 : 트리와 쿼리
- 난이도 : Gold 5
- 해설
- 문제는 하나의 트리를 만들고 Q개의 쿼리를 입력받으면 쿼리의 값을 root로 하는 subtree의 모든 정점의 개수를 구하면 되는 문제입니다.
- 매번 쿼리를 입력받을 때마다 해당 쿼리를 root로 하는 subtree의 모든 정점을 구하는 것은 많은 시간이 들 것입니다.
- 따라서 트리의 모든 subtree에서 정점의 개수를 미리 구하면 될 것 입니다.
- 소스코드 : https://www.acmicpc.net/source/30273421
- 너무 쉬운 문제이므로 한 문제 더 풀겠습니다.
- 문제 : 인하니카 공화국
- 난이도 : Gold 2
- 해설
- 1번 섬을 root로 하여 dfs(deepth first search) 알고리즘을 통해 순환하면서 Leaf 노드에서 특정 노드까지 폭파시켜야 하는 다리에 필요한 다이너마이트보다 노드까지 가는 다리를 터트리기 위한 다이너마이트 중 작은 값을 저장해오면서 구하면 됩니다.
- 무슨 소리인지 모르시겠다고요? 저도요...
- 소스코드 : https://www.acmicpc.net/source/30275016
분할 정복
- 문제 : 행렬 제곱
- 난이도 : Gold 4
- 해설
- A행렬의 4제곱은 A행렬을 4번 곱한 것과 같습니다. 이것은 A행렬의 제곱을 2번 곱한 것과 같습니다.
- 그렇다면 b번 곱한 것은 어떻게 될까요?
- 위 의문을 바탕으로 분할 정복을 수행하면 됩니다.
- 소스코드 : https://www.acmicpc.net/source/30283476
큐
- 문제 : 좋은 친구
- 난이도 : Gold 3
- 해설
- 해당 문제가 왜 큐 카테고리에 전시되어있는지 알 수 없습니다.
Queue자료구조로 해당 문제를 풀 수 있는 방법을 찾아봐야 할 것 같습니다.- 저는 첫 번째 이름부터 마지막 이름까지 이름의 길이의 수를 저장해두는 방식으로 해결했습니다. 즉, 배열에서 부분합을 구하는 방법을 적용했다고 할 수 있습니다.
- 소스코드 : https://www.acmicpc.net/source/30296580
