[알고리즘] 동적 계획법(Dynamic Programming)

동적 계획법이란?

  - 문제를 가장 작은 단위로 분할 > 부분 문제의 해를 활용 해 보다 큰 부분 문제를 해결 >
    최종적으로 전체 문제를 해결하는 알고리즘

  - 분할 정복과 비슷하게 문제를 잘게 나누어 접근하나 분할정복과는 성능차이가 있다.

  - Memoization (메모이제이션) 기법을 사용

    프로그램 실행 시 이전에 계산한 값을 저장 및 재사용 함으로써 
    재 계산을 방지하고 전체 실행속도를 빠르게 하는 기술

  - 부분 문제는 해결 후 상위 문제 해결 시 재 활용됨

분할 정복과의 차이점

분할정복	동적 계획법
분할한 문제가 반복되지 않음	분할한 문제가 반복되어 재활용 가능
조합 폭발(Combinatorial explosion)이 발생할 확률이 있다.	조합 폭발(Combinatorial explosion)이 발생하지 않는다.

조합 폭발

 

 

동적 계획법의 조건

  - Overlapping Subproblem : 겹치는 부분(작은) 문제

잘게 나눈 문제가 중복이 되는 경우를 뜻합니다.

그림1)동적 계획법

  - Optimal Substructure : 최적 부분 구조

문제의 정답을 작은 문제의 정답에서 부터 구할 수 있다.

 

동적 계획법 구현 방식

  - Top-down : (큰 문제를 작은문제로 쪼개면서 푼다.)재귀로 구현

  - Bottom-Up : (작은 문제부터 차례대로 푼다.)반복문으로 구현

문제 1 : Top-down으로 구현했을때 주의할점은 무엇이 있을까요?

재귀가 깊어지면 stack overflow가 발생할 수 있으니 문제의 크기가 어느정도인지 가늠하고 Top-down을 써도 되는지 판단한다.