[Algorithm] 다이나믹 프로그래밍 (Dynamic Programming)

나동빈님의 서적 '이것이 취업을 위한 코딩테스트다'를 읽고 정리하였습니다.

다이나믹 프로그래밍

다이나믹 프로그래밍(Dynamic Programming)은 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘이다.

 

 

중복되는 연산을 줄이자

최적의 해를 구하기에 시간 또는 메모리 공간이 매우 많이 필요한 문제들은 컴퓨터로도 해결하기 어려운 문제다. 컴퓨터의 연산 속도와 메모리 공간은 한정적이기 때문이다. 따라서 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.

다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있다. 대표적인 방법이 바로 다이나믹 프로그래밍(Dynamic Programming)기법으로 동적 계획법이라고도 불린다.

 

 

사용 조건

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

 

메모이제이션

메모이제이션(Memoization)은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다.

 

 

정리

다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

분할 정복(Divid and Conquer)과 다이나믹 프로그래밍의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.

 

 

재귀 함수와 반복문

재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에서 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다.

따라서 재귀 함수 대신에 반복문을 사용하여 오버헤드를 줄일 수 있다. 일반적으로 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋다.

가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 단순 반복문을 이용한 보텀업 방식으로 구현하자.시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다. 'recursion depth(재귀 함수 깊이)'와 관련된 오류가 발생할 수 있다. 이 경우 sys 라이브러리에 포함되어 있는 setrecursionlimit() 함수를 호출하여 재귀 제한을 완화할 수 있다.

 

 

두 가지 방식

• 탑다운(Top-Down) 방식
  • 하향식
  • 재귀 함수를 이용
  • 큰 문제를 해결하기 위해 작은 문제를 호출
  • 메모이제이션은 탑다운 방식에 국한되어 사용하는 표현
    • 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미
  • 예) 피보나치 함수를 재귀 함수로 구현(탑다운 다이나믹 프로그래밍)

# 한 번 계산된 결과를 메모이제이션(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]


print(fibo(99))

• 바텀업(Bottom-Up) 방식
  • 상향식
  • 단순히 반복문을 이용
  • 작은 문제부터 차근차근 답을 도출
  • 예시) 피보나치 함수를 반복문으로 구현(바텀업 다이나믹 프로그래밍)

# 앞 서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째와 두 번째 피보나치 수는 1
d[1], d[2], n = 1, 1, 99

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

print(d[n])