알고리즘 5) 다이나믹 프로그래밍

다이나믹 프로그래밍

• 다이나믹 프로그래밍은 한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법이다.
• 다이나믹 프로그래밍을 이용하면 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있다.
• 다이나믹 프로그래밍은 그 자체로도 다양한 문제로 출제될 수 있는 유형이지만, 그래프 이론 등 다양한 알고리즘에서도 자주 사용된다.
  • ex) Floyd Warshall 알고리즘

1) 다이나믹 프로그래밍 예시 - 피보나치 수열

문제

피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치 수열을 구현하라.

문제 해설

• 피보나치 수열의 점화식은 다음과 같이 표현할 수 있다 ($a_1=1, a_2=1$)
  $a_n=a_{n-1}+a_{n-2}$
• 파이썬에서는 이러한 수열을 리스트 자료형으로 표현할 수 있다.
• 위 점화식에 따라서 실제로 피보나치 수를 구하는 과정을 표현하는 방법은 아래와 같다.
  • n번째 피보나치 수를 f(n)이라고 표현할 때 4번째 피보나치 수 f(4)를 구하려면 다음과 같이 함수 f를 반복해서 호출할 것이다. 그런데 f(2)와 f(1)은 항상 1이기 때문에 f(1)이나 f(2)를 만났을 때는 호출을 정지한다

피보나치 수열을 재귀 함수로 풀이

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

• 피보나치 수열을 재귀 함수로 표현하면 f(n) 함수에서 n이 커질수록 수행 시간이 O($2^N$)으로 기하급수적으로 늘어날 것이다.

• 또한 n이 커질수록 동일한 함수가 반복적으로 호출되어 이미 한 번 계산했지만, 계속 호출할 때마다 계산하는 것을 알 수 있다.
• 위의 예시처럼 피보나치 수열을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다.
• 이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.

다이나믹 프로그래밍의 사용 조건

• 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다.
  • 큰 문제를 작은 문제로 나눌 수 있다.
  • 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
• 피보나치 수열은 위의 조건을 만족하여 다이나믹 프로그래밍으로 해결할 수 있다.

피보나치 수열을 다이나믹 프로그래밍으로 풀이

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
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))

• 피보나치 수열은 다이나믹 프로그래밍 기법 중 메모이제이션 기법을 이용해 풀이할 수 있다.
  • 메모이제이션은 한 번 구현한 결과를 메모리 공간에 메모해두고 같은 식을 호출하면 메모한 결과를 그대로 가져오는 기법이다.
  • 파이썬에서는 단순히 한 번 구한 정보를 리스트에 저장하고 같은 정보가 필요하면 값을 리스트에서 가져오면 된다.

2) 다이나믹 프로그래밍 작성 방법

• 다이나믹 프로그래밍을 이용한 소스코드 작성 방법은 2가지가 있다.
  • 보텀업(Bottom-Up) 방식 : 단순히 반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식
    • 다이나믹 프로그래밍의 전형적인 형태
    • 보텀업 방식에서 사용되는 결과 저장용 리스트를 'DP 테이블'이라고 부른다.
  • 탑다운(Top-Down) 방식 : 재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
    • 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.
    • 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해놓는 넓은 개념을 의미하므로 다이나믹 프로그래밍과 별도의 개념이다.
• 피보나치 수열을 보텀업 방식으로 풀면 아래와 같다. 동일한 원리를 적용하되 단순히 반복문을 이용하여 문제를 해결한 것으로 이해하면 된다.

# 앞서 계산된 결과를 저장하기 위한 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])

3) 다이나믹 프로그래밍과 분할 정복 알고리즘 비교

• 다이나믹 프로그래밍과 분할 정복 알고리즘은 큰 문제를 작게 나눈다는 점에서 유사하다.
• 둘의 차이점은 아래와 같다.
  • 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있지만, 분할 정복 알고리즘은 그렇지 않다.
  • 즉, 한 번 해결한 문제를 다시금 해결하는지 여부가 차이점이다.

4) 코딩 테스트에서 다이나믹 프로그래밍

① 문제를 푸는 첫 단계는 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이다.

• 특정 문제를 완전 탐색으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지와 해결하고자 하는 부분 문제들의 중복 여부를 확인한다.

② 다이나믹 프로그래밍으로 해결할 수 있는 문제라면 일단 재귀 함수로 작성해본다.
③ 메모이제이션을 적용할 수 있는 문제라면 코드를 개선한다.
④ 하지만 가능하다면 재귀 함수를 이용하는 탑다운 방식 보다는 보텀업 방식으로 구현하는 것이 좋다.

• 시스템상 재귀 함수의 스택 크기가 한정되어 'recursion depth'와 관련된 오류가 발생할 수 있기 때문이다.