동적 계획법 수학적 최적화 방법이자 알고리즘 패러다임입니다. 이 방법은 1950년대 Richard Bellman이 개발하였으며 항공 우주 공학에서 경제학에 이르기까지 수많은 분야에 적용되었습니다.  두 맥락 모두 복잡한 문제를 재귀적으로 더 간단한 하위 문제로 나누어 단순화하는 것을 말합니다. 일부 결정 문제는 이런 식으로 분해할 수 없지만, 여러 시점에 걸친 결정은 종종 재귀적으로 분해됩니다. 마찬가지로 컴퓨터 과학에서 문제를 하위 문제로 나누고 하위 문제에 대한 최적 솔루션을 재귀적으로 찾는 방식으로 문제를 최적으로 해결할 수 있다면 최적 하위 구조가 있다고 합니다. (출처: 위키디피아)  위키디피아에서 동적 프로그래밍, 통칭 동적 계획법(약칭 DP)을 위와 같이 설명하고 있다. 이것을 나만의 설명으..

PS + 알고리즘 공부했던 것 복습도 할 겸 써보는 알고리즘 설명(?)으로 첫 번째는 최단 경로 알고리즘 중 하나인 플로이드 - 워셜 알고리즘이다.  최단 경로 문제는 그래프 상에서 두 정점 (노드) 사이의 최단 경로를 찾는 문제로 여러 알고리즘을 이용하여 해결할 수 있다. 플로이드 - 워셜, 다익스트라, 벨만 - 포드, A * 알고리즘 등으로 최단 경로 문제를 해결할 수 있다. 각 알고리즘의 특징은 다음과 같다.플로이드 - 워셜모든 정점들 사이의 최단 경로를 구할 수 있다. 3중 루프를 사용한다.다익스트라두 노드 사이의 최단 경로를 구할 수 있지만, 두 노드 사이의 가중치에 음수가 존재한다면 사용할 수 없다.벨만 - 포드다익스트라와 같이 두 노드 사이 최단 경로를 구할 수 있으며, 음수 가중치가 존재하..