반응형
다이나믹프로그래밍
-
다이나믹 프로그래밍 ( 동적 계획법 )Knowledge/Algorithm 2019. 9. 6. 16:38
- 다이나믹 프로그래밍이란 다이나믹 프로그래밍은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 당연히 큰 문제를 작은 문제를 나누는 것과 다이나믹은 아무런 관련이 없다 이 용어를 처음 사용한 Richard Bellman은 그냥 '다이나믹'이 멋있어 보여서 사용했다고..ㅋ 다이나믹 프로그래밍으로 풀 수 있는 문제는 두가지 속성을 만족해야 한다. 1. Overlapping Subproblem ( 겹치는 부분 문제 ) : 큰 문제를 여러개의 부분 문제로 나누어서 풀 때 부분 문제간의 중복이 발생 가능해야 한다. 2. Optimal Substructure ( 최적 부분 구조 ) : 문제의 정답을 작은 문제의 정답을 통해 구할 수 있어야 한다. 예를 들어 대전에서 부산을 갈 때 최적의 루트가 대구를 거치는 거..