[코테] DP - 다이나믹 프로그래밍이란?

다이나믹 프로그래밍: 하나의 문제를 단 한번만 풀도록 하는 알고리즘

ex) 피보나치 수열

 

어떨 때 사용? 

1. 큰 문제를 작은 문제로 나눌 수 있을 때 - 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤 처리

     -> 이 과정에서 메모이제이션(memoization) 사용해야함: 이미 계산한 결과를 배열에 저장

2. 작은 문제로부터 구한 결괏값을 큰 문제에서도 활용 가능

 

2가지 문제 풀이 방식

1. 상향식(바텀 업) 방식: 가장 작은 문제의 답부터 찾아가는 방식, 반복문 사용

2. 하향식(탑 다운) 방식: 가장 큰 문제부터 시작하여 작은 문제 순으로 답을 찾아가는 방식, 재귀 함수 활용

 

1. 상향식(바텀 업) 방식

# 계산된 결과를 memoization 하기 위해 리스트 초기화
d = [0] * 100

d[0] = 1 # a_1 = 1
d[1] = 1 # a_2 = 1

# 바텀 업 방식: 반복문 활용
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

n = 99
print("fibo({}): {}".format(n, fibo(n)))

2. 하향식(탑 다운) 방식

# 계산된 결과를 memoization 하기 위해 리스트 초기화
d = [0] * 100

# 탑 다운 다이나믹 프로그래밍 기법과 재귀 함수를 활용한 피보나치 수열 구현
def fibo (x):
    # 종료 조건 (전달인자가 1 또는 2일 때 1을 반환)
    if x == 1 or x == 2:
        return 1
    
    # 계산된 결괏값이 존재할 경우 해당 결과값 반환
    if d[x] != 0:
        return d[x]
        
    # 계산된 결괏값이 존재하지 않을 경우 피보나치 수열의 결과를 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

n = 99
print("fibo({}): {}".format(n, fibo(n)))

 

참고:[알고리즘] 다이나믹 프로그래밍(DP)에 대해 알아보자! (+Python 구현) (tistory.com)