동적 프로그래밍(DP) 2 문제와 그래프 문제(프림 알고리즘, 다익스트라 알고리즘) 2개로 총 2문제입니다. 기한은 11/29 (일) 자정까지입니다.

동적 프로그래밍에 해당하는 두 문제는 강의 자료에 나와있는 pseudo code 참고해서 풀어주세요. 다만 강의 자료에는 생략되어 있는데, 동적 프로그래밍을 위해 별도 배열(행렬)을 할당할 때 초기값으로 무한대 값을 입력해주어야 합니다. 이때 무한대 값은 적당히 큰 값으로 입력해도 충분합니다 (예 100000)

그래프 문제에서도 초기 비용(dist 값등)들을 무한대 값으로 초기화해야 하는데 마찬가지로 적당히 큰 값(예 100000) 을 할당하면 충분합니다. 또 다익스트라 문제에 오류가 있는데 '양방향' 그래프가 아닌 '단방향' 그래프입니다. 다익스트라 문제에서 입력으로 주어지는 간선 정보 (x, y, z) 는 x -> y 로만 간선이 향하고 있으며 그 간선의 가중치는 z 라는 의미입니다. 구현에서 각 정점에서 저장해야 할 dist나 방문 여부 등의 정보들은 정점들이 index(숫자)로 표현되므로 배열로 관리하면 쉽게 구현 가능합니다. 프림과 다익스트라 문제를 풀려면 최소힙을 구성해야 하는데 이는 라이브러리를 사용하면 편하게 구현 가능합니다. 각 언어 별로 사용 가능한 힙 라이브러리(우선순위큐)는 아래와 같습니다. 참고 바랍니다.

C 없음(직접 힙 구현 필요) C++ priority_queue + greater<> Python heapq (min-heap) Java PriorityQueue