[DP 다이나믹 프로그래밍] 코드 패턴과 특징

DP란,

 피보나치처럼 작은 문제로 분할하여 현재의 값을 구하는 문제에 대해 메모리 공간을 활용함으로써 속도를 비약적으로 줄이는 기법이다. 점화식으로 표현되는 문제들을 DP기법을 활용할 경우 효율적으로 답을 구할 수 있다.

점화식이란,

인접한 항들 사이의 관계식을 의미한다. 예를 들어 수열에서의 각 항을 An이라고 부를때, 우리는 점화식을 이용해 현재의 항을 이전항에 대한 식으로 표현할 수 있다. DP로 해결할 수 있는 가장 대표적인 유형인 피보나치의 점화식은 A(n+2) = A(n+1) + An 으로 표현할 수 있다. 

프로그래밍과 점화식

n번째 피보나치수를 f(n)이라고 표현할 때, f(4)를 구하고자 할 때 f(2)와 f(1)은 항상 1이므로 이때는 호출을 정지하는 코드를 넣어 재귀함수로 풀 수 있다. 아래 코드를 보면 코드 형태가 위에 표현된 점화식과 꽤나 닮아있음을 확인할 수 있다.

 

아래 재귀함수에선 사용하지 않았지만, 피보나치 처럼 수열을 다룰 때, 프로그래밍에서는 리스트(파이썬)을 이용해 처리한다.

# 재귀함수로 구현한 피보나치
def fibo(x):
    if x == 1 of x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)
print(fibo(4))

 

 

재귀함수를 이용한 구현

  이처럼 수학적 점화식을 프로그래밍으로 표현하기 위해 재귀함수를 사용한다면, n의 수가 커질 때 심각한 문제가 생기게 된다. 시간 복잡도가 엄청나게 커지기 때문이다.

 

  n이 6이라면, f(6)을 연산하기 위해 f(5)와 f(4)를 연산하고, 또 f(5)는 f(4) + f(3)이고, 앞 단의 f(4)를 위해 f(3)과 f(2)를 연산하기 때문에  O(2**n)  의 지수 시간이 소요된다. 살짝만 들여다봐도, f(4)가 반복연산으로 들어있고, 그 하단으로 줄줄이 이어지는 f(3), f(2)들도 중복되어 연산을 수행하게 된다. 

 

따라서 결과값을 이미 저장된 배열에서 불러옴으로써 시간복잡도를 획기적으로 줄이고, 보다 효율적인 해결이 가능하도록 하는 것이 DP기법이다.

 

DP의 조건

DP는 아래의 조건을 만족할 때, 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 

 

DP의 기법 중 하나인 메모이제이션은 한 번 구한 결과를 메모리 공간에 저장해두고, 다시 호출할 때, 저장되어있던 값을 그대로 불러오는 기법이다. 메모이제이션은 캐싱이라고도 한다.

# DP의 메모이제이션을 사용한 소스코드
# top down

d = [0] * (7)
def fibo(x):
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    else:
        d[x] = fibo(x-1) + fibo(x-2)
        return d[x]
print(fibo(6))

메모이제이션을 사용할 경우 f(6)을 구할때, 호출하는 함수는 f(5), f(4), f(3)이 되고, 이로써 시간 복잡도는 O(N)이 된다.

 

탑다운(top down)과 바텀업(bottom up)

  큰 문제를 해결하기 위해 작은 함수를 호출하는 것은 탑 다운 방식에 해당하고, 반복문을 사용해 작은 것부터 답을 도출해 나가는 것은 바텀 업 방식이라고 한다. (d[x] = fibo(x-1) + fibo(x-2)) 점화식의 형태가 작은 것들의 합이라고 탑다운인 것이 아니라, 함수의 호출을 스택 구조의 원리에 기반해, 호출 순서가 큰 수 -> 작은 수로 진행하게 되는 것이 탑다운의 관건이다. 반대로 바텀업은 반복문을 이용해 배열을 작은 수부터 차례로 채워나가는 원리에 기반한다.

 

바텀 업 방식의 소스코드는 이렇다.

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

 

 

요약

점화식으로 표현되는 문제들은 재귀 함수, DP의 탑다운, DP의 바텀업(반복문)을 사용해 구현할 수 있다. 재귀함수는 O(2**n)의 시간복잡도를 가지기에 DP의 메모이제이션을 활용하면 O(n)으로 줄일 수 있다. 메모이제이션은 배열의 값에 호출값을 저장해둠으로써 함수가 다시 필요할 때, 중복 호출이 아닌 배열의 값을 읽어옴으로써 호출 기능을 대체한다.

 

+ 동적 계획법(DP, Dynamic Programming)과 동적 할당(Dynamic Allocation)

프로그래밍에서 Dynamic은 '프로그램 실행 중에-' 의 의미를 가진다. 동적 할당의 경우, 프로그램 실행 중에 프로그램 실행을 위한 메모리를 할당하는 기법을 뜻한다. 그러나 DP의 dynamic은 이런 의미와는 관련이 없다.

 

* 참고

책 '이것이 취업을 위한 코딩테스트다'

다음에 더 읽어봐야지
https://doing7.tistory.com/75