인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

네 DP라고 볼 수 있으며 정확히는 DP + 그리디 알고리즘이다 라고 보시면 됩니다.

DP는 큰 문제를 작은 문제로 나누어 해결하며, 작은 문제의 최적해를 이용해 큰 문제의 최적해를 구하는 기법인데 다익스트라 알고리즘도 한 번 방문한 정점에서의 최단 경로를 기록하고, 이를 바탕으로 다음 정점으로의 최단 경로를 계산한다는 점에서 유사합니다.

DP는 동일한 문제를 여러 번 계산하지 않도록, 이전에 계산한 결과를 메모이제이션 하는데 다익스트라 알고리즘은 우선순위 큐에 이미 계산된 최단 경로를 이용해 중복 계산을 방지하며, 매번 가장 짧은 경로를 선택해 다음 계산을 진행합니다.

정리하자면, 다익스트라 알고리즘은 DP + 그리디 알고리즘의 특징이 있는 알고리즘입니다. (현재 상태에서 최선의 선택을 하여 전체 최적해를 구하는 방식)

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.