[알고리즘] 동적 계획법이란?(Dynamic Programming, DP)

목차 

1. 동적 계획법 개념
2. 일반적인 피보나치 구현
3. 메모제이션
4. bottom-up 구현
5. top-down 구현

 

1. 동적 계획법 개념

큰 문제를 작은 문제로 나누어서 푸는 방법

 

* 반대 개념: 결정적 프로그래밍 (BFS, DFS 등이 결정적 프로그래밍 방식임)

 

* DP를 사용하는 경우

1. 큰 문제를 작은 문제로 나눌 수 있는 경우
2. 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일한 경우

 

2. 일반적인 피보나치 재귀 구현

 

재귀의 경우 같은 로직을 여러번 반복하기 때문에 비효율적인 계산이 될 확률이 높다. 

 

재귀를 활용한 피보나치 구현코드

 

# 1로 만들기

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

fibo(5)

피보나치 코드에서의 중복

 

따라서 이런 비효율성을 없애기 위해 DP라는 방식이 있다.

 

3. 메모제이션

dp 방식에선 메모제이션이 활용된다. 메모제이션은 이전의 계산결과를 기록해, 중복되는 과정을 생략하기 위해 쓰이는 방법이다. 

 

4. bottom-up 구현 방식

 

dp의 구현 방식은 두 가지가 있는데 그 중하나는 bottom-up 방식이다.

이는 작은 문제부터 차례대로 아래에서부터 푸는 방식이다.

 

bottom-up 예제 코드

fiboData = list()
fiboData.append(0)
fiboData.append(1)

def bottomUp(n):
    for i in range(2,n+1):
        fiboData.append(fiboData[i-1] + fiboData[i-2])
    
    return fiboData[n]

print(bottomUp(10))

기존의 배열에 순서대로 값을 저장해서 문제를 푸는 것으로 기존의 피보나치 수열의 재귀 구현보다 더 효율적이다.

 

4. top-down 구현 방식

나머지 하나는 top-down 방식이다.

이는 큰 문제를 작은 문제로 쪼개면서 푸는 방식이다.

 

top-down 예제 코드

fiboData = [0] * 100


def topDown(n):
    if n <= 2:
        return 1
   
    if fiboData[n] == 0:
        fiboData[n] = topDown(n-1) + topDown(n-2)
    return fiboData[n]