[알고리즘] 다이나믹 프로그래밍 기본 개념과 대표 문제 피보나치 수열

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

 

기본 개념

최적화 문제를 해결하는 알고리즘 기술이다.

전체 문제의 최적 해가 부분 문제의 최적 해를 포함함을 활용한다.

이전에 계산한 값을 저장함으로써 동일 계산의 반복을 제거한다.

 

재귀적 구조

- 큰 문제 안에 닮음꼴의 작은 문제가 들어있는 구조다.

- 관계중심으로 문제를 간명하게 파악 가능하다.

 

재귀적 해법

- 잘 쓰면 보약, 잘못 쓰면 맹독이다.

- 심각한 중복 호출이 일어나는 경우가 있다.

 

> 재귀적 해법이 바람직한 예

- 퀵 정렬, 병합 정렬 등의 정렬 알고리즘

- 계승(factorial) 구하기

- 그래프의 DFS

 

> 재귀적 해법이 치명적인 예

- 피보나치수 구하기

- 행렬곱셈 최적순서 구하기

 

 

대표 문제 : 피보나치 수

아주 간단한 문제이지만 DP의 취지와 구현이 모두 포함되어 있다

 

f(n) = f(n-1) + f(n-2) 

f(1) = f(2) = 1

 

 

재귀적 알고리즘 (규모가 큰 수열의 경우 엄청난 중복 호출이 발생한다)

fib(n) 
{ 
        if (n = 1 or n = 2) 
            then return 1; 
        else return (fib(n-1) +fib(n-2)); 
} 

print (fib(n));

 

다이나믹 프로그래밍 적용 알고리즘

f[1] ← 1;
f[2] ← 1; 

for i ← 3 to n 
	f[i] ← f[i-1] + f[i-2]; 

 print( f[n] );

 

시간복잡도 : O(n)

선형시간에 완료된다.

 

 

다이나믹 프로그래밍의 적용 요건

1. 최적 부분구조 (optimal substructure )

큰 문제의 최적 해에 하위 문제의 최적 해가 포함된다.

2. 하위 문제들의 중복 

재귀적 해법으로 풀면 같은 하위 문제에 대한 호출이 많이 발생한다.