알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 8. 다이나믹 프로그래밍 - 개념

  • 0
  • 0
0
0

1. 다이나믹 프로그래밍 (Dynamic Programming)

A. 중복되는 연산을 줄이자.

최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제는 컴퓨터를 활용해도 해결하기 어려운 문제이다. 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. 그래서 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.

다이나믹 프로그래밍(Dynamic Programming) (동적 계획법)은 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시킬 수 있는 방법이다.

a. 예시) 피보나치 수열

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다.

![[피보나치수열.png]]

수학자들은 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게 표현한다. 점화식이란 인접한 항들 사이의 관계식을 의미한다. 수열 {a_n}이 있을 때 수열에서의 각 항을 a_n이라고 부른다고 가정할때, 점화식을 이용해 현재의 항을 이전의 항에 대한 식으로 표현할 수 있다.

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

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

이러한 점화식을 인점 3항간 점화식이라 부르는데 인접한 총 3개의 항에 대해서 식이 정의되기 때문이다.

프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다. 수열 자체가 여러 개의 수가 규칙에 따라서 배열된 형태를 의미하는 것이기 때문이다. 리스트나 배열 모두 연속된 많은 데이터를 처리한다는 점은 동일하다.

실제 피보나치 수를 구하는 과정은 그림과 같다. f(2)와 f(1)은 항상 1이기 때문에 f(1)이나 f(2)를 만났을 때는 호출을 정지한다.

![[피보나치수열2.png]]


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)의 지수 시간이 소요된다고 표현한다.

![[피보나치수열3.png]]

위 그림에서 동일한 함수가 반복적으로 호출되는 것을 알 수 있다. 이미 한 번 계산했지만, 계속 호출할 때마다 계산하는 것이다. f(n)에서 n이 커지면 커질수록 반복해서 호출하는 수가 많아진다.

B. 피보나치 수열을 다이나믹 프로그래밍으로 해결하자.

피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다. 이런 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다. 다만 항상 다이나믹 프로그래밍을 사용할 수는 없으며, 다음 조건을 만족해야 한다.

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

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

a. 다이나믹 프로그래밍 - 재귀 함수 (Top-Down)

메모이제이션은 한 번 구한 정보를 리스트에 저장하는 방식으로 구현한다. 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오면 된다.


d = [0] * 100  
  
def fibo(x):  
    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))

다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 사실 큰 문제를 작게 나누는 방법은 퀵 정렬에서도 소개된 적이 있다. 퀵 정렬은 정렬을 수행할 때 정렬할 리스트를 분할하여 전체적으로 정렬이 될 수 있도록 한다. 이는 분할 정복(Divide and Conquer) 알고리즘으로 분류된다. 다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.

다이나믹 프로그래밍은 한 번 해결했던 문제를 다시금 해결한다는 점이 특징이다. 그렇기 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결이 됐던 것이니까 다시 해결할 필요가 없다고 반환하는 것이다.

![[피보나치수열DP재귀적.png]]

색칠하지 않은 부분은 사실상 호출되지 않는다고 이해하자. 호출하더라도 따로 계산하지 않고 리스트에서 값을 가져오거나 바로 1을 반환하기 때문이다. 물론 재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다. 따라서 재귀 함수 대신 반복문을 사용하여 오버헤드를 줄일 수 있다.

다이나믹 프로그래밍을 적용했을 떄의 피보나치 수열 알고리즘의 시간 복잡도는 O(N)이다. 한 번 구한 결과는 다시 구해지지 않기 때문이다. 따라서 실제로 호출되는 함수를 표현하면 아래 그림과 같다.

![[피보나치수열DP재귀적_실제호출되는함수.png]]

재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법은 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down) 방식이라고 말한다. 반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 바텀업(Bottom-Up) 방식이라고 한다.

b. 다이나믹 프로그래밍 - 반복문 (Bottom-Up)

d = [0] * 100  
  
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])

탑다운(메모이제이션) 방식은 하향식이라고도 하며, 바텀업 방식은 상향식이라고도 한다. 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이다. 바텀업 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다. 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념이다. 한 번 계산된 결과를 어딘가에 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.

메모이제이션은 때에 따라서 다른 자료형, 예를 들어 사전(dict) 자료형을 이용할 수도 있다. 사전 자료형은 수열처럼 연속적이지 않은 경우에 유용하다. a_{n}을 계산하고자 할 떄 a_{0} ~ a_{n-1} 모두가 아닌 일부의 작은 문제에 대한 해답만 필요한 경우가 존재할 수 있다.

C. 다이나믹 프로그래밍으로 문제 해결하는 순서

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

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

가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 바텀업 방식으로 구현하는 것을 권장한다. 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다.

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #이것이취업을위한코딩테스트다 #개념 #다이나믹프로그래밍

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.