[ Algorithm ] 다이나믹 프로그래밍

다이나믹 프로그래밍 (Dynamic Programming)

다이나믹 프로그래밍은 문제에서 "최적 부분 구조" 또는 "반복되는 부분 문제"에 해당하는 경우

사용할 수 있는 알고리즘이다.

 

1. 최적 부분 구조
   => 커다란 문제를 작은 문제로 나눌 수 있고 그 형태가 모두 유사하다면 이를 모아서 큰 문제를 해결하는 것
2. 반복되는 부분 문제
   => 형식이 동일한 작은 문제를 반복적으로 해결해야 할때의 문제

 

점화식과 최적 부분 구조

점화식은 인접한 항으로서 현재 값을 결정하는 관계식을 말하며

점화식은 주로 최적 부분 구조를 만족한다는 특징이 있다.

• 피보나치 수열 (점화식): a(n) = a(n -1) + a(n-2), [ (a(1) = 1, a(2) = 1 ]

 

점화식의 구성요소

"초기항"과 "인접한 항과의 관계"가 필요하다.

점화식은 재귀함수로 표현이 가능하며 재귀함수의 경우 종료조건이 반드시 있어야 하는데

종료조건이 점화식의 초기항 과 같은 역할을 수행한다.

function fibo(n) {
	if (n == 1 || n == 2) return 1; // 종료조건이 없으면 무한루프된다.
    return fibo(n - 1) + fibo(n - 2); // 점화식
}

 

다이나믹 프로그래밍의 형태 예시

function dp() { /*
    1. 종료하는 조건
    2. 이미 해결한 문제 = 정답을 return
    3. 점화식 계산
*/ }

다이나믹 프로그래밍 문제를 해결하는 과정은

1. 점화식을 찾아내고
2. 구현방식을 상향식, 하양식을 선택한 후에
   상향식: 반복문을 통해 초기항부터 계산 방법
   하양식: 재귀함수로 큰 항을 구하기 위해 작은 항을 호출하는 계산 방법
3. 점화식을 코드로 구현해주면 된다.
   < 계산이 완료된 값을 담는 테이블을 주로 DP테이블이라고 부른다. >

 

마치며...

다이나믹프로그래밍에 대해서 혼란스러울땐 피보나치 수열을 떠올리는 것이 가장 좋은 것 같다.