[알고리즘] 동적 계획법(Dynamic Programming, DP) 개념 정리

 

 

다이나믹 프로그래밍이란?

• 다이나믹 프로그래밍(Dynamic Programming, DP) 알고리즘은 메모리 공간을 약간 더 사용하면서 연산 속도를 비약적으로 증가시킬 수 있는 기법이다.

• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

• 다이나믹 프로그래밍의 구현은 일반적으로 탑다운(top-down) 방식과 보텀업(bottom-up) 방식

 

 

 

조건

다이나믹 프로그래밍은 다음 조건들을 만족할 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있고 그 작은 문제의 답을 모에서 큰 문제를 해결할 수 있는 경우

2. 동일한 작은 문제를 반복적으로 해결해야하는 경우

 

 

 

메모이제이션(Memoization)

• 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나다.

• 한 번 계산한 결과를 말 그대로 메모리 공간에 메모하는 기법이다.

  • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.

  • 갑을 기록해 놓는다는 점에서 캐싱이라고도 한다.

• 메모이제이션은 한 번 구한 정보를 리스트에 저장하는 형태로 구현할 수 있다.

  • 이 리스트를 보통 DP테이블이라고 부른다.

 

 

 

탑다운(top-down) vs 보텀업(bottom-up)

• 탑다운 방식은 재귀함수로 구현할 수 있고, 보텀업 방식은 반복문으로 구현할 수 있다.

• 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.

• 뭐가 더 좋은지는 문제마다 다르다. 하지만 일반적으로 재귀함수를 사용하는 것 보다 반복문을 사용하는 것이 성능이 좀 더 좋다(오버헤드가 줄기 때문에). 시간 복잡도 측면에서는 동일하다.

• 따라서 특정 케이스를 제외하고는 그냥 자신이 편한걸로 쓰면 된다.

 

 

---

 

 

 

피보나치 수열문제는 다이나믹 프로그래밍 기법을 통해 효율적으로 풀 수 있는 문제 중 하나이다.

피보나치 수열 문제를 통해 DP문제의 흐름을 살펴보자.

 

 

우선 피보나치 수열을 점화식으로 나타내면 다음과 같다.

a[n] = a[n-1] + a[n-2],
a[1] = 1, a[2] = 1

>> n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수

 

 

99번째 피보나치 수열을 구한다고 할 때 DP방식을 활용하지 않고, 재귀 함수를 사용하여 해결하면 다음과 같다.

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

print(fibo(99))

이렇게 하면 n이 커질 수록 계산했던 함수가 반복적으로 호출되기 때문에 수행 시간이 기하급수적으로 늘어난다.

이런 문제에서 다이나믹 프로그래밍 기법을 사용하면 시간을 매우 단축시킬 수 있다.

 

 

 

* 탑다운 방식을 이용한 코드

# DP테이블 초기화 (1부터 99까지 계산 가능하다고 가정)
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]


print(fibo(99))

 

 

* 보텀업 방식을 이용한 코드

# DP테이블 초기화
d = [0] * 100


# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99


# 피보나치 함수 반복문으로 구현
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]


print(d[n])