하루 세 가지의 주제를 골라 문제를 풀어봅시다.
- 다익스트라
- 분할 정복
- 위상 정렬
다익스트라
- 문제 : 알고스팟
- 난이도 : Gold 4
- 해설
- 문제의 분류가 왜 다익스트라 문제로 분류되어있는지 알다가도 모르겠는 문제입니다.
- 가장 기본적으로 최단거리를 찾을 수 있는 방법인 BFS 알고리즘으로 문제를 해결하였습니다.
- 소스코드 : https://www.acmicpc.net/source/30454741
분할 정복
- 문제 : 버블 소트
- 난이도 : Gold 1
- 해설
- 가장 문제가 되었던 것은 당연 시간이었습니다.
O(n^2)의 시간복잡도를 가진 버블 정렬을 사용하면서 문제를 해결하기에는 문제의 N값인500,000이 문제였습니다.- 그렇다면 더 작은 시간복잡도를 가진 정렬방법을 사용하면서 버블 정렬과 같은 효과를 가진 것이 필요했습니다.
- 가장 알맞은 정렬방법은
Merge Sort입니다. - 소스 코드 : https://www.acmicpc.net/source/30478850
위상 정렬
- 문제 : 게임 개발
- 난이도 : Gold 3
- 해설
- 이전에 풀었던 ACM Craft와 상당히 유사한 문제입니다.
- ACM Craft와 다른 점이라고 한다면 모든 건물의 건설시간을 결과로 표시하는 것만 다른 문제였습니다.
- 소스 코드 : https://www.acmicpc.net/source/30489627
