[동적계획법] - 프로그래머스 고득점 kit

다이나믹 프로그램 : "한 번 계산한 문제는 다시 계산하지 않도록 한다." -> 메모제이션 기법

 

<조건>

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

동적 계획법 vs 분할 정복

• 동적 계획법: 소문제 종속적
  (피보나치 수열): 소문제가 상위 문제에 영향을 끼치며 원소들이 종속적이다.
• 분할 정복: 소문제 독립적
  (퀵 정렬, 병합 정렬) : 각각 분할된 원소들이 정렬 과정에서 다른 원소들의 영향을 미치지 않는다.

동적 계획법 vs 탐욕법

• 동적 계획법: 모든 가능성 고려 → 항상 최적의 결과 도출
• 탐욕법: '현 상태' 에서 가장 최적의 경우를 판단하여 결정 → 문제에 따라 최적해가 구해지지 않을 수 있다.