[알고리즘] : 동적 계획 알고리즘 및 플로이드 워샬 알고리즘 기초

동적 계획 알고리즘 ( Dynamic Programming (DP) )

입력 크기가 작은 부분 문제들을 해결하고 그 해들을 이용해 보다 큰 크기의 부분 문제들을 해결하여 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘입니다.

 

분할 정복은 중복이 되지 않습니다.

동적 계획 알고리즘은 중복을 허용합니다.

 

ex] 피보나치 = 0 1 1 2 3 5 8 13 21 - - - -

 

플로이드 - 워샬 알고리즘

간단하게 플로이드 알고리즘이라고 부릅니다.

플로이드 알고리즘의 시간 복잡도는 O(n^3)으로 다익스트라 알고리즘을 n번 사용할 때의 시간 복잡도와 같습니다.