동적 계획법(dynamic programming)

동적 계획법

복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법

 

원리

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

2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.

3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다. 이를 memoization 기법이라고 한다.

4. 동적 계획법은 top-down 방식과 bottom-up 방식으로 구현할 수 있다.

 

피보나치 수열 공식

D[N] = D[N-1] + D[N-2] //  N번째 수열 = N-1번째 수열 + N-2번째 수열

 

구현 방식

1. 동적 계획법으로 풀 수 있는지 확인하기

2. 점화식 세우기

3. 메모이제이션 원리 이해하기

4. top-down 구현 방식 이해하기

주로 재귀 함수 형태로 구현한다.

5. bottom-up 구현 방식 이해하기

주로 반복문 형태로 구현한다. top-down은 런타임 에러가 발생할 수 있으므로 bottom-up이 보다 더 안전한 방식이다.

 

출처 : Do it! 알고리즘 코딩테스트 자바편