다이나믹 프로그래밍(Dynamic Programming)이란 무엇일까?

다이나믹 프로그래밍의 의미

다이나믹 프로그래밍(Dynamic Programming)은 한국말 뜻 그대로 해석하면 동적 프로그래밍입니다. 프로그래밍을 동적으로 하다니.. 춤이라도 추면서 프로그래밍을 하는 걸까요? 다이나믹 프로그래밍은 이름부터 어려워서 마음의 장벽을 느꼈는데, 이 방법을 고안한 벨만이 멋진 단어(..)라 펀딩을 위해서 사용했다고 합니다.

사실 다이나믹 프로그래밍은 어떠한 문제를 풀 때 작은 범위로 나누고, 동일한 부분은 기억하여 중복을 막아 문제를 해결하는 기법입니다. 분할 정복(Divide and Conquer)에 메모이제이션(Memoization)을 추가한 개념이라 보시면 됩니다. 즉, 작은 문제의 답이 바뀌지 않는 점을 이용해 큰 문제를 푸는 것입니다. 다이나믹 프로그래밍을 구성하는 큰 두 가지의 개념은 아래에 서술합니다.

• 분할 정복(Divide and Conquer): 복잡한 문제를 잘게 나누어 푸는 기법
• 메모이제이션(Memoization): 반복되는 부분은 기억하여 불필요한 중복을 막는 기법

다이나믹 프로그래밍 이용 예시

흔히 다이나믹 프로그래밍의 예시로 제안되는 것이 피보나치 수열(fibonacci Sequence)입니다.

피보나치 수열이란? 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 과 같이 이 전의 두 항을 합친 값이 그 다음의 값이 되는 수열입니다.

피보나치 수열은 앞의 두 개의 값을 재귀함수를 이용하여 간단히 풀 수 있지만, 만약 엄청 거대한 크기의 피보나치 수열을 구하고자 할 때는 어떨까요? 소요시간이 무지막지하게 길어져서 원하는 시간 내에 원하는 답을 얻지 못할 수 있습니다.

메모리: 살..려..줘.....

여기에 메모이제이션 개념을 추가해봅시다! 피보나치 수열은 언제 구해도 각 항의 값이 일정하죠?

파이썬을 이용한 피보나치 수열 구현

계산 결과는 항상 같으므로, 메모이제이션을 사용해도 좋습니다. 아래는 파이썬으로 구현한 피보나치 함수입니다. fibo 배열에 피보나치 함수의 값들을 기록하여 불러오는 방식입니다.

def fibonacci(n):
    fibo = [0, 1]
    if n < 2:
        return fibo[n]
    else:
        for i in range(2, n+1):
            fibo.append(fibo[i-2] + fibo[i-1])
    return fibo[n]

슬라이딩 윈도우 기법을 이용한 피보나치 수열 구현

참고로 슬라이딩 윈도우 기법을 이용해서 문제를 풀 수도 있습니다. 아래의 코드는 슬라이딩 윈도우 기법으로 피보나치 수열을 파이썬으로 구현하였습니다.

def fibonacci_2(n):
  v0, v1 = 0,1
  if n < 2:
    return n
  for i in range(n-1):
    v2 = v0 + v1
    v0, v1 = v1, v2
  return v2

알고리즘 문제를 풀다보면 다이나믹 프로그래밍을 이용하여 문제를 풀어야 하는 경우가 많습니다. 이번에 공부한 것을 바탕으로 다음에는 관련된 문제를 가져와 풀어보도록 하겠습니다!