먼저 책이랑 프린트를 보시오..
동적계획법(dynamic programming)
- 문제를 여러개의 하위 문제로 나누어 푼다음 결합 (이전의 결과를 활용하여 다음 결과를 산출하는 것)
- 문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이를 찾아냄.
-> 느릴 수 있으나 정확한 결과를 갖다 줌.
ex) 플로이드, 벨만포드, 다익스트라, 비터비, 배낭문제, CYK(Cocke-Younger-Kasami)
1) 플로이드-워셜 알고리즘
- 경유점, 시작점, 끝점을 모두 루프를 돌아 모든 노드 쌍들에 대한 최단의 경로를 선택.
2) 벨만-포드 알고리즘
- 시작점은 고정되어 있고, 경유점, 끝점 루프를 돌아 시작점으로 부터 최단의 경로를 선택.
- 시작점이 고정되있는걸 빼면 플로이드와 유사하고, 음수를 처리할 수 있는걸 빼면 다익스트라와 유사하다.
- 음수의 가중치를 처리할 수 있다. (다익스트라는 -1로 처리하기도 하고 그리디이기도 하기 때문에 불가)
- 방향성 존재
3) 다익스트라 알고리즘 (greedy라 하기도 하는데 왜 그럴까??)
- 시작점은 고정되어 있고, 시작점에서 각각의 목적지까지 최소의 비용으로 갈 수 있는 루트를 찾는다.
- 방향성 존재
탐욕적 방법(greedy algorithms)
- 전체적인 상황을 고려하지 않고, 순간순간 가장 최적의 풀이를 선택.
- 빠르고 항상 최적해를 구하진 않지만, 대체로 최적해에 가깝게 구해냄.
1) 프림 알고리즘
- 현재 점들의 집합에서 총 edge 합이 최소가 되도록 연결 시키는 것.
- 방향성 없음
2) 크루스칼 알고리즘
- 시작점에 관계없이 최소의 cost를 갖는 edge부터 연결하면서 모든 노드들이 이어질 때 까지 하기