[알고리즘] 다이나믹 프로그래밍

다이나믹 프로그래밍

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법.
이미 계산된 결과는 별도의 메모리에 저장하여 다시 계산하지 않는 방식.
일반적으로 두 가지 방식 (탑다운 / 보텀업) 으로 구성된다.

다이나믹 프로그래밍은 다음의 조건을 만족할 때 사용할 수 있다.
1. 최적 부분 구조(Optimal Substructure)
큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결한다.
2. 중복되는 부분 문제(Overlapping Substructure)
동일한 작은 문제를 반복적으로 해결한다.

피보나치 수열

피보나치 수열은 대표적인 다이나믹 프로그래밍 예시문제이다.

피보나치 수열이란

1,1,2,3,5,8,13...

이런식으로 나열되는 수열로 다음과 같은 점화식으로 나타낼 수 있다.

피보나치 수열 파이썬 구현

def fivo(n):
	if( n == 1) or (n == 2):
    	return 1
    
    return fivo(n-1)+fivo(n-2)
    
print(fivo(6))

# 출력
8

하지만 이렇게 구현하면 수를 줄여가며 함수를 호출할 때마다 계산을 다시 하게 된다.
ex) fivo(6)라면
이처럼, n을 호출하면 2, 1이 될때 까지 반복호출 및 계산을 수행한다.

다이나믹 알고리즘 개념을 생각하면 한번 계산을 수행한 것은 기록해놓고 함수가 호출될 때 계산된 값이 있다면 그 값을 사용하여 구현할 수 있다.

피보나치 수열 다이나믹 알고리즘

---------탑다운 방식----------

# 계산 결과를 담을 리스트 작성
check = [0]*20

def fivo(n):
    if( n == 1) or (n == 2):
        return 1
    
    if ( check[n] != 0 ):
        return check[n]
    
    check[n] = fivo(n-1)+fivo(n-2)
    return check[n]
        
print(fivo(6))

---------보텀업 방식----------

check = [0] * 20

check[1] = 1
check[2] = 1
n = 6

for i in range(3,n+1):
    check[i] = check[i-1] + check[i-2]

for j in range(1,n+1):
    print(check[j])

이렇게 다이나믹 알고리즘을 활용하면 다음과 같이 구현하여 시간복잡도를 줄일 수 있다.