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

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

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

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