DP(동적 계획법)

문제를 해결하기 위해 많은 시간, 혹은 많은 공간이 필요한 경우가 나타난다. 이러한 제약된 조건 속에서 문제를 효율적으로 해결하기 위해서는 그에 걸맞는 효율적인 알고리즘이 필요하다. 보통 일반적인 방법으로 문제를 해결할 경우, 매우 많은 연산 횟수 혹은 매우 큰 배열이 필요할 때 효율적인 방법으로 DP를 사용하게 된다.
보통 DP의 문제는 시간 복잡도를 낮추기 위해 공간 복잡도를 올리는 방법을 선택한다. 다시 말하면 같은 연산의 반복을 줄이기 위해서 배열을 생성하고(공간 복잡도는 오른다), 배열에 메모하여 같은 연산의 답이 있을 경우 연산을 하지 않게 한다.(메모이제이션) 배열은 문제 상황에 따라 1차원 혹은 2차원으로 사용된다.
다이나믹 프로그래밍 알고리즘은 대표적인 2가지 방법이 있는데, 하나는 Botton-Up 방식이고 하나는 Top_Down 방식이 있는데 문제를 보면서 차이점을 살펴보도록 하자.
DP 해결 방법은 주어진 문제를 아주 작은 부분의 문제로 바꿔서 해결한다는 아이디어에서 출발한다. 작은 부분의 문제를 해결하고, 그 다음 크기의 부분 문제를 작은 부분의 문제를 해결한 것에 더해서 해결하는 식이다.
이렇게 점진적인 해결이 가능하다면,
1. 큰 문제를 작은 문제로 나눈다.(큰 문제의 축소판으로 만든다)
2. 작은 문제의 해결법은 큰 문제의 해결법과 같다.

DP 문제의 대표적인 방법으로는 피보나치 수열의 문제를 해결하는 방법을 보면 그 방식을 알 수 있다.

피보나치 수열:
'첫 달에 태어난 토끼 한 쌍이 존재한다. 그리고 두 달 이상이 된 토끼는 번식이 가능해진다. 번식이 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다. 이렇게 계속 달이 지난다고 했을 때, n번째 달의 토끼의 수는?'
위의 토끼 한 쌍을 1로 놓고 계산해 보면, [1, 1, 2, 3, 5, 8, 13, 21, 34. . . . . .] 이다.
피보나치 수열은 첫 번째와 두 번째만 제외하고 특정한 수로 배열이 되어 있는 것을 알 수 있다.

F(1) = 1, F(2) = 1, F(n) = F(n-1) + F(n-2)

Bottom-Up

제목 그대로 바닥에서, 아주 작은 부분에서 시작하여 위로(큰 문제) 올라가면서 푸는 방식이다.
n번째 달의 토끼의 수를 알아내기 위해서 1부터 시작하여 n까지 위의 계산식을 적용하면 되는데, 이를 수학에서는 점화식이라고 한다. 위의 형태와 같이 인접한 항들 사이의 관계식을 세울 수 있다면 n번째 항을 구할 수 있다.

def fibo(n):
    for i in range(3, n+1): # 2번째 달 까지의 수는 고정, 3번째 달부터 구한다.
        fiboArr[i] = fiboArr[i-2] + fiboArr[i-1] # i번째 달의 수는 해당 달에서 -1을 한 달과 -2를 한달의 합이다.
        print(fiboArr[i])
    return fiboArr[n]
if __name__ == '__main__':
    n = 20
    fiboArr = [0] * (n + 1) # 점진적인 계산을 위해 배열이 필요.
    fiboArr[1] = 1 # 첫 번째와 두 번째 달은 1이다.
    fiboArr[2] = 1
    fibo(n)
    print(fiboArr[n])
출력:
6765

피보나치 수열은 비교적 쉬운 문제다. 코드를 보더라도 쉽게 구현이 가능해 보이지만, DP의 문제가 주어졌을 때 점화식을 세우고 코드로 구현하는 것은 생각보다 어려운 일이다. 비슷한 문제를 풀어보면서 점화식을 구현하는 방법을 익숙하게 사용할 수 있어야 한다.

Top-Down

이 방식의 문제풀이는 재귀 함수를 사용하기 때문에 조금 더 까다로울 수 있다. Top-Down 방식은 위의 표와 같이 큰 문제에서 시작하여 해결할 수 있는 작은 문제까지 내려간다. 그리고 재귀적으로 다시 본래의 문제로 돌아가면서 해결하는 방식이다. Top-Down 방식을 풀 때 주의할 점은 위와 같이 재귀적으로 탐색하며 내려가기에 메모이제이션으로 한 번 연산한 것은 다시 연산하지 않도록 해야한다. 모든 경우를 재귀적으로 연산을 하게 된다면 빅오 계산법에 따라서 O(2**n)으로 기하급수적으로 연산 횟수가 증가하기 때문에 주의를 해야한다.

def fibo(n):
    if n == 1 or n == 2: # 첫 번째 달과 두 번째 달은 1이다. 
        return 1
    if fiboArr[n] != 0: # 메모이제이션 : 이미 계산된 피보나치 수열이라면 계산된 값을 반환
        return fiboArr[n]
    # 계산이 되지 않았을 경우에 점화식으로 재귀 호출
    fiboArr[n] = fibo(n-1) + fibo(n-2)
    return fiboArr[n]

if __name__ == '__main__':
    n = 20
    fiboArr = [0] * (n + 1)
    fibo(n)
    print(fiboArr[n])
출력:
6765