Algorithm

[파이썬(Python)] 다이나믹 프로그래밍

Reife 2023. 3. 7. 11:20

나동빈 님의 이것이 취업을 위한 코딩 테스트다 with 파이썬을 학습 목적으로 정리한 글입니다.

 

프로그래밍에서 다이나믹 또는 동적인 것은 어떠한 동작이 프로그램 수행 중에 일어나는 것을 의미합니다. 실행 중에 메모리를 할당하거나, CSS를 변경하는 것을 동적이라고 할 수 있습니다. 하지만 알고리즘 문제 유형에서 가르키는 다이나믹은 그 의미가 아닙니다. 이번에는 코딩테스트의 관점에서 다이나믹 프로그래밍이 무엇이고, 어떤 문제를 해당 방식으로 풀면 좋은지 알아보겠습니다.

 

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

어떤 문제를 작은 문제로 분할하고, 중복된 문제는 한 번만 풀어서 효율성을 높이는 프로그래밍 방식을 의미합니다. 일반적으로 사용되는 '다이나믹'의 의미와 큰 연관성은 없어보이는데, 이 방법을 고안한 Bellman에 따르면, dynamic이라는 표현을 통해 해당 방법이 여러 (작은) 단계로 구성되어 있다는 사실을 나타내고 싶었고, 또 단순히 dynamic이라는 표현이 기억에 잘 남을 것 같아서 이처럼 명명했다고 합니다.

 

적용 예시

 

1 1 2 3 5 8 13 21 34 55 89 144 233 ...

 

피보나치 수열입니다. 이 수열의 특징은 1항과 2항은 1이고, 세 번째 항부터는 이전 두 항의 합이 해당 항의 값이 된다는 것입니다. n항의 값이 무엇인지 알려면 이전의 항을 알아야하고, 결국 1항부터 더해나갈 수 밖에 없습니다. 피보나치 수열의 10항을 구하는 코드를 재귀적으로 표현하면 다음과 같습니다.

def fibonacci(n):
	if n == 1 or n == 2:
    	return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))

 

먼저 fibonacci(9) + fibonacci(8)이 호출되고, 각각 fibonacci(7) + fibonacci(8)과 fibonacci(8) + fibonacci(7)을 호출합니다. 이처럼 매 회 각 항은 2개의 함수를 호출하므로, 연산 횟수는 n이 조금만 커져도 기하급수적으로 증가합니다. 엄밀히 따져서는 조금 차이가 있지만  일반적으로 이 방식의 시간복잡도는 O(2^n)라고 표현합니다. 분명 비효율적인 알고리즘입니다. 

 

그런데 각 항을 살펴보면 동일한 연산이 중복되는 것을 확인할 수 있습니다. 위에서 든 예시만 보더라도 fibonacci(8)이 중복되었고, n이 클수록 이러한 중복도 많아질 것이라는 것을 우리는 직관적으로 알 수 있습니다. 이 중복을 줄이는 것으로 피보나치 수열을 구현하는 데 효율을 꾀할 수 있을 것입니다.

 

중복되는 연산을 줄여서 효율성을 높여야 할 때 다이나믹 프로그래밍이 도움이 될 수 있습니다. 다이나믹 프로그래밍을 사용할 수 있는 조건은 다음과 같습니다.

 

1. 큰 문제를 작은 문제로 분할할 수 있다.
(≒ 재귀적으로 표현이 가능하다)

2. 작은 문제의 답이 큰 문제에서도 유효하다.

 

재귀 함수를 이용한 하향식 다이나믹 프로그래밍

피보나치 수열을 구현한 재귀 함수의 효율성을 높이기 위해서 메모이제이션 기법을 도입합니다. 메모이제이션은 연산 결과를 저장해두고, 필요할 때 호출해서 사용하는 방법입니다. 캐싱이라고도 합니다. 이를 통해 메모리 공간을 더 사용하는 대신 속도를 높일 수 있습니다. 시간복잡도는 O(N)로 상당히 개선됨을 알 수 있습니다.

 

# 메모이제이션을 위한 리스트 초기화(0부터 100까지)
d = [0] * 101

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    
    if d[n] != 0:
        return d[n]
    d[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return d[n]

print(fibonacci(100))

 

위 소스코드와 같이, 재귀함수를 사용해서 큰 문제를 작은 문제로 분할하는 방법을 다이나믹 프로그래밍 중에서도 탑다운 방식(하향식)이라고 합니다. 반대로, 작은 문제부터 풀어나가는 방식은 바텀업 방식(상향식)이라고 합니다.

또한, 연산 결과를 저장하는 리스트의 명칭도 하향식과 상향식에서 차이가 있습니다. 위 코드에서 처럼 하향식에서 사용되는 리스트는 '메모이제이션'이라고 하고, 다음으로 다루게 될 상향식에서 사용하는 리스트는 'DP 테이블'이라고 합니다. 

 

 

반복문을 이용한 상향식 다이나믹 프로그래밍

재귀함수는 구현하고, 이해하기가 직관적이라는 장점이 있지만, 실행 과정에서 많은 함수가 메모리에 적재되므로 오버헤드가 발생할 수 있습니다. 또한, 재귀 함수의 스택 크기가 부족해서, recursion depth와 관련된 오류가 발생할 수 있습니다. 이를 개선하기 위해 반복문을 사용해보겠습니다.

 

d = [0] * 101

d[1] = 1
d[2] = 1
n = 100

for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

 

재귀적 풀이 방법과 달리 인덱스는 3부터 시작해서 목표 인덱스까지 차례차례 더해 나갑니다. 재귀 함수 대신 반복문을 사용했다는 차이점 외에도, 아래에서부터 위로 올라가는 상향식이라는 차이가 있습니다. 

 

 

 

Preference

https://www.quora.com/Why-is-dynamic-programming-called-dynamic-programming