5. 동적계획알고리즘

최적화 문제를 해결하기 위한 알고리즘

다단계 해결 알고리즘

부분문제를 모두 해결한 후 큰 크기의 부분문제들을 해결
각 단계의 부분문제의 답을 기반으로 전체문제의 답을 구하는 방법

분할정복과의 차이점

부분문제들 사이의 관계

분할정복 알고리즘은 부분문제의 해의 중복을 허용하지 않음 하지만
동적 계획 알고리즘에는 부분문제들 사이에 의존적 관계가 존재

5.1. 모든 쌍 최단 경로 문제

각 쌍의 점 사이의 최단 경로를 찾는 문제

5.1.1 다익스트라 알고리즘의 경우

시간복잡도 O(n^3)

5.1.2 floyd 알고리즘(동적)

시간복잡도O(n^3)