[Algorithm] 다이나믹 프로그래밍 개념

이번엔 알고리즘 하면 알아야 하고 코딩 테스트에서도 자주 출제되는 다이나믹 프로그래밍에 대해서 알아보도록 하겠습니다.

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

다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘입니다. 다이나믹 프로그래밍은 한 번 해결했던 문제를 다시금 해결한다는 점이 특징입니다. 그래서 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결이 됐던 것이니까 다시 해결할 필요가 없다고 반환하는 것입니다. 다이나믹 프로그래밍 방식에는 큰 문제를 해결하기 위해 작은 문제를 호출하는 탑다운(Top-Down) 방식과 작은 문제부터 차근 차근 답을 도출해 큰 문제의 해답을 구하는 방식으로 바텀업(Bottom-up) 방식이 있습니다. 탑다운 방식에는 주로 재귀함수를 바텀업 방식에는 반복문을 사용합니다.
탑다운 방식은 하향식이라고도 하며, 바텀업 방식은 상향식이라고도 합니다. 다이나믹 프로그래밍의 전형적인 방식은 바텀업 방식입니다. 바텀업 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현입니다. 다이나믹 프로그래밍과 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념입니다. 한 번 계산된 결과를 어딘가에 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있습니다. 이에 대한 설명을 위해 다이나믹 프로그래밍을 설명하기 위해서 자주 사용되는 피보나치 수열을 이용해 설명을 진행해 보도록 하겠습니다.

피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열입니다. 피보나치 수열은 다음과 같은 형태로 끝없이 이어집니다.

1 1 2 3 5 8 13 21 34 55 89 $\dots$

수학자들은 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게 표현합니다. 우리는 점화식을 이용해 현재의 항을 이전의 항에 대한 식으료 표현할 수 있습니다. 예를 들어 피보나치 수열의 점화식은 다음과 같이 표현할 수 있습니다.

$a_{n+2} = f(a_{n+1}, a_n) = a_{n+1}+a_n$

결과적으로 피보나치 수열에서는 첫 번째 항과 두 번째 항의 값이 모두 1이기 때문에 최종적으로 피보나치 수열을 나타낼 때에는 다음과 같이 정의할 수 있습니다.

$a_n = a_{n-1} + a_{n-2}, a_1 = 1, a_2 = 1$

이를 해석하면 다음과 같습니다.

• n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
• 단, 1번째와 2번째 피보나치 수는 1

우리는 위의 식을 참고해서 다음과 같이 프로그래밍을 할 수 있습니다.

# 피보나치 함수를 재귀 함수로 구현

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

하지만 위와 같이 소스코드를 작성하면 심각한 문제가 발생합니다. 바로 fibo 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어납니다. 그 이유는 매번 필요한 값을 구하기 위해서 반복적인 계산을 수행하기 때문입니다. 이 소스코드의 시간 복잡도는, 엄밀히 말하면 피보나치 수열의 정확한 시간 복잡도는 세타표기법을 사용하여 $\theta(1.618\cdots^N)$ 으로 표현할 수 있습니다. 하지만 일반적으로는 빅오 표기법을 이용하여 O($2^N$)의 지수 시간이 소요된다고 표현합니다. 예를 들어 f(100)을 계산하려면 얼마나 연산을 해야하는지 대략적으로 계산해 보겠습니다. $2^10$ 을 약 1,000 이라고 했을 때, 연산 횟수는 약 1,000,000,000,000,000,000,000,000,000,000번입니다. 우리가 일반적으로 사용하는 PC 나 노트북으로는 우리의 수명이 다할 때까지 연산을 진행해도 답을 도출할 수 없을 것입니다.
이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없습니다. 이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있습니다. 하지만 항상 다이나믹 프로그래밍을 사용할 수는 없으며, 다음 조건을 만족할 때 사용할 수 있습니다.

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

피보나치 수열은 이러한 조건을 만족하는 대표 문제입니다. 이 문제를 탑다운 방식인 메모이제이션 기법을 사용해 해결해보도록 하겠습니다. 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나로 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미합니다. 메모이제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 합니다.
메모이제이션 방식으로 피보나치 수열을 구현하면 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오면 됩니다. 이를 소스코드로 나타내면 다음과 같습니다.

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화

d = [0] * 100

# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)

def fibo(x):
  # 종료 조건( 1혹은 일 때 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))

파이썬 프로그램을 실행해보면 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])

다이나믹 프로그래밍 문제 풀이 방법

코딩 테스트에서의 다이나믹 프로그래밍 문제는 대체로 간단한 형태로 출제되므로, 이 책에서 다루는 문제 저옫만 바르게 습득해도 코딩 테스트에서 다이나믹 프로그래밍 문제를 풀기에는 어려움 없을 것이며, 다이나믹 프로그래밍 문제 푸는 방법에 대해서 설명을 하도록 하겠습니다.

1. 문제를 푸는 첫 번째 단계는 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것입니다. 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해봅시다.

2. 일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 아이디어입니다.

3. 가능하다면 재귀 함수를 이용한 탑다운 방식 보다는 바텀업 방식으로 구현하는 것을 권장합니다. 시스템상 재귀 함수의 스택 크키가 한정되어 있을 수 있기 때문입니다. 실제로 앞에서 제시한 재귀적인 피보나치 수열의 소스코드에서 오천 번째 이상의 큰 피보나치 수를 구하도록 하면 recursion depth와 관련된 오류가 발생할 수 있습니다. 이 경우 sys 라이브러리에 포함되어 있는 setrecursionlimit() 메서드를 호출하여 재귀 제한을 완화할 수 있다는 점 정도만 기억하시면 될 것 같습니다.

마치며

이번엔 다이나믹 프로그래밍에 대해서 알아보았습니다. 사실 기법은 아주 간단하다고 볼 수 있습니다. 이전에 구했던 값들을 구해서 저장해 놓고 이미 구한 값이 아니라면 저장해둔 이전 값들을 이용해 구하고자 하는 값을 계산하는 방식입니다. 그래서 다이나믹 프로그래밍의 경우 개념을 익히기 보다는 실제 문제 풀이를 진행해야 실력이 더 늘 것 같습니다. 조만간 코딩 테스트에 주로 나오는 알고리즘들의 개념을 모두 정리한 후 각 단계 별로 문제 풀이도 진행할 때 다시 다뤄 보도록 하겠습니다. 긴 긁 읽어주셔서 감사드리며 잘못된 내용, 오타 혹은 궁금하신 내용이 있으시다면 댓글 남겨주시기 바랍니다.