[알고리즘] 다이나믹 프로그래밍(DP)에 대해 알아보자! (+Python 구현)

본 포스팅에서는 다이나믹(동적) 프로그래밍에 대해 알아봅니다.

📚 목차

1.  다이나믹 프로그래밍이란?
2.  다이나믹 프로그래밍 예제
3.  재귀함수 기반 구현
        3.1.  소스코드
        3.2.  문제점
            3.2.1.  연산 복잡성
            3.2.2.  문제 발생의 원인
            3.2.3.  문제 해결 방안
4.  다이나믹 프로그래밍 기반 구현
    4.1.  탑 다운 방식(재귀함수 활용)
        4.1.1.  메모이제이션이란?
        4.1.2.  소스코드
        4.1.3.  특징
    4.2.  바텀 업 방식(반복문 활용)
        4.2.1.  소스코드
        4.2.2.  특징

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

다이나믹(동적) 프로그래밍은 큰 문제를 작은 문제로 나누어 연산 속도와 메모리를 최대한으로 활용하기 위한 기법입니다. 특정 값을 얻기 위해 매번 같은 결과를 반환하는 연산을 굳이 반복해서 수행한다면 문제를 효율적으로 해결할 수 없습니다. 이럴 때 사용하는 것이 다이나믹 프로그래밍이며 아래 2가지 조건을 모두 만족할 때만 사용할 수 있습니다.

 

• 조건1) 큰 문제를 작은 문제로 나눌 수 있다.
• 조건2) 작은 문제로부터 구한 결괏값을 큰 문제에서도 활용 가능하다.

아직 이해가 안 되셨다고요? 괜찮습니다. 아래 예시와 함께 살펴보시면 금방 이해하실 수 있으실 겁니다.

2.  다이나믹 프로그래밍 예제

다이나믹 프로그래밍의 대표적인 활용 예시는 피보나치 수열의 프로그래밍 구현입니다. 피보나치 수열(Fibonacci Function)은 1, 2번째 항이 모두 1일 때 \(n\) 번째 요소를 \((n-1)\)번째 요소와 \((n-2)\)번째 요소의 합으로 표현하는 수열입니다. 피보나치 수열은 다음 수식 1 과 같이 점화식을 활용해 표현할 수 있습니다. 참고로 점화식이란 인접한 항들 사이의 관계식입니다.

 

수식 1. 피보나치 수열의 점화식

\(n\)번째 피보나치 수를 \(f(n)\)이라고 할 때, 4번째 피보나치 수인 \(f(4)\)를 구하기 위해서는 함수 \(f\)를 \(f(1)\)이나 \(f(2)\)를 마주할 때까지 \(f\)를 반복 수행해야 합니다. 아래 그림 1 은 \(f(4)\)를 구하는 과정입니다. 즉, \(f(3)\)과 \(f(2)\)를 먼저 구하고, \(f(3)\)을 구하기 위해 다시 \(f(2)\)와 \(f(1)\)을 구해야 합니다.

 

그림 1. 4번째 피보나치 수를 구하는 과정 표현

피보나치 수열을 구현하는 방법은 크게 2가지입니다. 재귀함수와 다이나믹 프로그래밍입니다. 두 방법을 각각 알아보며 장단점을 비교해 보겠습니다.

3.  재귀함수 기반 구현

다이나믹 프로그래밍을 활용하는 방법은 다음 섹션에서 다루고, 우선 재귀함수를 활용하여 피보나치 수열을 구현해 봅니다. 이를 통해 왜 다이나믹 프로그래밍 기법이 필요한지 알아봅니다.

3.1.  소스코드

# 재귀 함수를 활용한 피보나치 함수 구현
def fibo (x):
    # 종료 조건 (전달인자가 1 또는 2일 때 1을 반환)
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)

n = 4
print("fibo({}) = {}".format(n, fibo(n)))

위 소스코드와 같이, 파이썬을 통해 4번째 피보나치 수인 \(a_{4}\)의 값을 출력해 보겠습니다.

fibo(4) = 3

이처럼 비교적 간단하게 피보나치 수를 구하는 코드를 작성할 수 있었습니다.

3.2.  문제점

재귀함수 기반의 구현은 간단하지만 치명적인 한계가 있습니다.

3.2.1.  연산 복잡성

하지만 만약 우리가 찾아야 하는 값이 6번째 피보나치 수라면 어떨까요? 아래 그림 2 와 같이 연산 횟수가 기하급수적으로 늘어난 것을 확인하실 수 있습니다. 이처럼 일반적인 재귀함수 방법으로 구현한 소스코드의 시간 복잡도는 빅오 표기법을 이용하면 \(O(N^{2})\) 으로 표현할 수 있습니다. 즉, 우리가 구해야 하는 \(N\) 값이 \(30\)이라면 약 \(10\)억 가량의 연산을 수행해야 하는 것이죠.

 

그림 2. 6번째 피보나치 수를 구하는 과정 표현

3.2.2.  문제 발생의 원인

연산 횟수가 이렇게 기하급수적으로 증가하는 이유는 무엇일까요? 그림 2 에서 파란색으로 표시한 것처럼 3번째 피보나치 수를 구하는 연산은 3회씩이나 불필요하게 반복되는 것을 확인하실 수 있습니다. 다시 말해, \(f(3)\)은 3회 호출된 것이죠.

3.2.3.  문제 해결 방안

그럼 어떻게 이러한 비효율적인 연산을 개선할 수 있을까요? 바로 다이나믹 프로그래밍을 활용하는 것입니다.

4.  다이나믹 프로그래밍 기반 구현

이제 피보나치 수열을 다이나믹 프로그래밍을 활용하여 구현해 봅니다. 다이나믹 프로그래밍은 2가지 문제 풀이 방식이 있습니다.

• 1) 탑 다운(Top-Down, 하향식) 방식: 가장 큰 문제부터 시작하여 작은 문제 순으로 답을 찾아가는 방식으로, 주로 재귀 함수 활용
• 2) 바텀 업(Bottom-Up, 상향식) 방식: 가장 작은 문제의 답부터 찾아가는 방식으로, 주로 반복문 활용

탑 다운 방식보다 바텀 업 방식을 활용했을 때 다이나믹 프로그래밍의 성능이 좋다는 점에서 일반적으로 다이나믹 프로그래밍하면 바텀 업 방식을 떠올리시면 됩니다. 그럼에도 공부하는 차원에서 2가지 방법 모두 활용하여 피보나치 수열을 구현해 보겠습니다.

4.1.  탑 다운 방식(재귀함수 활용)

탑 다운 방식은 메모이제이션(Memoization) 기법을 활용합니다.  메모이제이션 기법과 이를 활용한 실제 구현 방법까지 알아보도록 하겠습니다.

4.1.1.  메모이제이션(Memoization)이란?

메모이제이션(Memoization)은 한 번 연산을 통해 구한 결괏값을 메모리에 저장해 두었다가 같은 식의 연산을 재호출하면 메모리에 저장한 값을 불러와 활용하는 기법입니다. 메모이제이션은 값을 저장한다는 점에서 캐싱(Cashing)이라고도 부릅니다.

4.1.2. 소스코드

메모이제이션 기법을 활용해 피보나치 수열을 구현해 보겠습니다. 방법은 간단합니다. 연산 수행 값을 리스트에 저장하고 필요할 때마다 리스트에서 가져오면 됩니다. 실제 소스코드를 통해 알아보죠.

# 계산된 결과를 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]

n = 99
print("fibo({}): {}".format(n, fibo(n)))

한 번 해결한 문제의 결괏값을 리스트에 저장해 두었다가 추후에 동일한 문제를 해결해야 할 때 리스트에서 해당 결괏값을 가져오는 코드입니다.

 

실행결과

fibo(99): 218922995834555169026

4.1.3.  특징

위와 같이 메모이제이션을 활용해 앞서 살펴본 예시와 같이 6번째 피보나치 수를 구하는 과정을 시각화하면 그림 3 과 같습니다. 가장 큰 문제인 \(f(6)\)를 시작으로 \(f(5), f(4), ..\) 순서로 점차 작은 문제를 호출하고 결괏값을 저장하고 가져오는 과정을 \(f(1)\)과 \(f(2)\)를 만날 때까지 반복합니다.

그림 3. 메모이제이션 기법을 활용해 6번째 피보나치 수를 구하는 과정 시각화

장점

메모이제이션 기법을 활용하면 파란색 노드만 연산해 주면 되기 때문에 연산의 효율을 극대화할 수 있습니다. 회색 노드는 사실상 방문하지 않아도 됩니다. 왜냐하면 이미 계산된 결괏값이 리스트에 저장되어 있거나 1을 반환(i.e., \(f(1)\) 또는 \(f(2)\))하면 되기 때문입니다.

 

한계점

재귀함수를 사용하면 함수를 호출할 때 메모리에 적재되는 일련의 과정을 거쳐야 하기 때문에 *오버헤드(ovehead)가 발생할 수 있습니다. 반면, 재귀함수가 아닌 반복문을 활용한다면 오버헤드를 단축시킬 수 있습니다. 따라서 일반적인 경우에는 대부분 재귀함수보다 반복문을 활용했을 때가 다이나믹 프로그래밍 성능이 우수합니다.

* 오버헤드(overhead)란?

오버헤드란 어떤 연산을 수행하기 위해 필요한 간접적인 시간 또는 메모리 등을 말합니다. 예를 들어, A라는 연산을 처리하기 위해 7초가 소요되고 안정성 등을 위해 추가적으로 B라는 처리까지 수행하는 데 10초가 걸렸다고 하죠. 그렇다면 여기서 오버헤드는 3초가 됩니다. 나아가, 만약 B라는 처리 효율을 개선하여 A와 B를 처리하는데 8초가 걸렸다면, 2초의 오버헤드를 단축시켰다고 말할 수 있습니다.

4.2.  바텀 업 방식(반복문 활용)

바텀 업 방식이 탑 다운 방식에 비해 효율적이므로 다이나믹 프로그래밍을 구현한다고 하면 일반적으로 바텀 업 방식을 떠올리시면 됩니다.바텀 업 방식으로 피보나치 수열을 구현해 봅니다.

4.2.1.  소스코드

# 계산된 결과를 memoization 하기 위해 리스트 초기화
d = [0] * 100

d[0] = 1 # a_1 = 1
d[1] = 1 # a_2 = 1

# 바텀 업 방식: 반복문 활용
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

n = 99
print("fibo({}): {}".format(n, fibo(n)))

바텀 업 방식에서 결괏값을 저장해 두는 리스트를 DP 테이블이라고 부릅니다.

 

실행결과

fibo(99): 218922995834555169026

4.2.2.  특징

장점

바텀 업 방식은 오버헤드를 단축시킬 수 있어 탑 다운 방식에 비해 더욱 효율적인 성능을 갖는다는 장점이 있습니다.

 

시간 복잡도

다이나믹 프로그래밍의 시간 복잡도는 \(O(N)\) 입니다. 왜냐하면 \(f(1)\)을 계산한 값을 \(f(2)\)를 계산하는 데 사용하고, \(f(2)\)를 계산한 값을 \(f(3)\)을 계산하는 데 사용하는 방식으로 이어지기 때문이죠.

---

포스팅 내용에 오류가 있을 경우 댓글 남겨주시면 대단히 감사드리겠습니다.

그럼 오늘도 즐거운 하루 보내시길 바랍니다😊

고맙습니다.