DP, Dynamic Programming 동적 계획법 알고리즘과 예제

동적 계획법이란?

 

크기가 크거나 복잡한 문제를 효율적으로 풀기위해 작거나 간단한 어러개의 문제로 나눠서 푸는 방법으로, 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.

입력 크기가 작은 문제들을 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하고, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘 설계기법으로 프로그램 성능의 향성을 기대할 수 있다.

---

피보나치 수를 구하는 함수에 DP알고리즘 적용하기

 

1. 문제를 부분 문제로 분할
   • fibonacci(0) = 0, fibonacci(1) = 1
   • fibonacci(n) =  fibonacci(n-1) + fibonacci(n-2) (n>=2)
2.  
3. 가장 작은 부분 문제부터 해를 구한다.
4. 부분문제들의 해를 테이블에 저장하고 이를 이용하여 상위 문제의 해를 구한다.

메모제이션은 위 과정의 3번과 같이 부분 문제들의 해를 메모리에 저장하는 기법으로 동적 계획법 알고리즘에서 핵심이 되는 기술이므로 중요한 개념이다.

---

DP 알고리즘 구현하는 방식

 

1. recursive 방식

함수의 호출을 이용한 재귀적 방법이다.
재귀적 구조는 엄청난 중복호출이 발생할 수 있으므로 내부에 시스템 호출 스택을 사용하는 overhead가 발생할 수 있다.

def fibo(n):
	if n<2:
    	return n
    else:
    	return fibo(n-1) + fibo(n-2)

 

2. iterative 방식

반복문을 이용한 반복적 방법
Memoziation을 반복적 구조에 사용하여 DP알고리즘을 구현하는 거이 위의 재귀적 구조에 비해 실행속도와 성능면에서 보다 효율적.
반복문을 이용하여 작은 값부터 상위로 값을 구해나간다.

def fibo(n):
	f = [0,1]
    for i in range(2, n+1):
    	f.append(f[i-1] + f[i-2])
    return f[n]