<청춘> 격정적으로 사는 것

밤을 새고 공부한 다음 날 새벽에 느꼈던 생생한 환희와 야생적인 즐거움을 잊을 수 없다

자료구조 알고리즘

다이나믹 프로그래밍 (Dynamic Programming) / 동적계획법 - 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

수학도 2021. 7. 21. 00:25

컴퓨터를 활용해도 해결하기 어려운 문제?

  • 최적의 해를 구하기에 시간이 매우 많이 필요한 문제 - 컴퓨터 연산 속도에 한계가 있음
  • 메모리 공간이 매우 많이 필요한 문제 - 메모리 공간을 사용할 수 있는 데이터의 개수가 한정적

다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있다.

→ 다이나믹 프로그래밍 (Dynamic Programming) / 동적계획법

 

 

피보나치 수열

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

피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 수열이다.

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

 

점화식이란 인접한 항들 사이의 관계식으로, 점화식을 이용해 수열을 간결하게 표현할 수 있다.

피보나치 수열의 점화식은 a1=1, a2=2, an+2=an+1+an (단, n ≥1인 자연수) 이다. 

이를 해석하면

n번째 항 = (n-1)번째 항 + (n-2)번째 항

단, 1번째 항 =1, 2번째 항 = 1

 

그럼 점화식에 따라서 실제로 피보나치 수를 구하는 과정을 어떻게 표현할 수 있을까?

n번째 피보나치 수를 f(n)이라고 표현할 때 f(4)를 구하려면

f(4)

= f(3) + f(2)

= {f(2) + f(1)} + f(2) 이므로

f(3)을 1번

f(2)를 2번

f(1)을 1번 호출해야 한다.

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

 

하지만 이렇게 작성하면, f(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나 심각한 문제가 생길 수 있다. 이 소스코드의 시간 복잡도는 O(2^N)으로, 만약 N = 30이면, 약 10억번의 연산을 수행해야 한다.

 

f(6)를 구하려면

f(6)

= f(5) + f(4)

= f(4) + f(3) + f(3) + f(2)

= f(3) + f(2) + f(2) + f(1) + f(2) + f(1) + f(2)

= f(2) + f(1)  + f(2) +f(2) + f(1) + f(2) + f(1) + f(2) 이므로 

f(5)를 1번

f(4)를 2번

f(3)을 3번

f(2)를 5번

f(1)을 3번 호출해야 한다.

 

즉, n이 커질수록 f(n)을 반복해서 호출하는 수가 많아진다.

 

이와 같은 문제에서, 한 번 계산한 문제는 다시 계산하지 않도록 하기 위해 사용하는 알고리즘이 다이나믹 프로그래밍(동적계획법)이다.

 

다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다.

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

 

메모이제이션 (Memoization)

다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다. 캐싱(Caching)이라고도 한다.

 

 

피보나치 수열을 메모이제이션 기법을 사용하여 해결해보자.

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100


# 피보나치 함수를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(n):
    # 종료 조건(1 혹은 2일 때 1을 반환)
    if n == 1 or n == 2:
        return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[n] != 0:
        return d[n]
    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[n] = fibo(n - 1) + fibo(n - 2)
    return d[n]


print(fibo(99))

위의 코드는 99번째 피보나치 수를 구하도록 했음에도 불구하고 금방 정답을 도출하는 것을 알 수 있다.

 

 

즉, 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 

더보기

사실 퀵 정렬에서도 큰 문제를 작게 나누는 방법을 사용한다.

퀵 정렬은 정렬을 수행할 때 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 한다.

이는 분할 정복 알고리즘으로 분류된다.

 

다이나믹 프로그래밍과 분할 정복의 차이점

다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.

 

피보나치 함수가 종료될 때 어떤 함수를 호출했는지, 현재의 피보나치 수를 출력하도록 코드를 만들어 확인해보자.

# 탑다운 방식

d = [0] * 100

def fibo(n):
    print('f(' + str(n) + ')', end =' ')
    if n == 1 or n == 2:
        return 1
    if d[n] != 0:
        return d[n]
    d[n] = fibo(n-1) + fibo(n-2)
    return d[n]


fibo(6)
f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

호출 순서 : 빨간색

f(6) 

= f(5)                          + f(4)

= f(4)                 + (f3) + f(4)

= f(3)         + f(2) + f(3) + f(4)

= f(2) + f(1) + f(2) + f(3) + f(4) 

 

위의 호출순서를 보면 f(1)을 구한 다음 그 값이 f(2)를 푸는 데 사용되고, f(2)의 값이 f(3)을 푸는 데 사용되는 방식으로 이어진다. 따라서 이 때 시간복잡도는 O(N)이 된다.

 

이처럼 재귀함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down)방식이라고 한다. 혹은 하향식이라고도 한다.

 

 

물론, 재귀함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다. 따라서 재귀함수 대신에 반복문을 사용하여 오버헤드를 줄일 수 있다. 일반적으로 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋다.

 

단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 바텀업(Bottom-Up)방식이라고 한다. 혹은 상향식이라고도 한다.

# 바텀업 방식

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])

 

다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이다. 바텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.

 

 

코딩테스트를 위한 다이나믹 프로그래밍

주어진 문제가 다이나믹 프로그래밍 유형임을 파악해야한다.

특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자.

 

 

출처 

나동빈, 『이것이 취업을 위한 코딩테스트다 with 파이썬』, 한빛미디어(주), 2020년