[파이썬 알고리즘 문제풀이] 동적계획법이란? 네트워크 선 자르기(Bottom-Up)

문제 :

Note

다이나믹프로그래밍으로 사고하는 연습이 전혀 안되어 있음을 알게 해준 문제였다. 나는 재귀, 트리, 그래프 등으로만 사고를 하여 문제를 해결하는 타입이였다. 이유는 지금까지 그런 유형의 문제를 많이 풀면서 트리로, 그래프로, 재귀로 사고하는 과정이 익숙해기 때문이다. 컴퓨터공학은 사고하는 방법을 배우는 학문이다. 사고를 이론화한 다른학문과는 아주 다른 특이한 학문이다.

이론과 실전의 융합. 실전을 통해 이론의 사용을 명확히 이해할 수 있다. 개념을 정확히 이해하는 것은 매우 중요하지만 문제풀이, 실전경험을 통해 이론이 더 강화 될 수 있다. 제대로 알고 피나는 연습으로 몸에 이론이 달라붙으려면 실전연습이 많이 필요하다. 그렇다고 항상 이론을 먼저 알아야하는 것은 아니다. 실전 연습을 통해 노하우가 쌓이고, 이 경험이 이론적으로는 어떤지 유기적으로도 바뀔 수 있다. 유연한 사고가 필수이다.

서론이 길었다. 나는 맨처음에 이문제도 재귀적으로 접근하려고 했다. 문제의 예시의 등장한 4를 자르는 방법을 트리로 그리려고 한 것이다. 물론 이렇게 접근할 수도 있을거 같긴 하지만 시간복잡도가 좋지 않을것 같다.

아직 익숙하지 않은 부분문제로 큰 문제를 해결하는 다이나믹프로그래밍적으로 사고하지 못했다. 이 문제를 풀면서 다이나믹프로그래밍 사고방식이 조금 뭔지 알것 같다.

두 번째 약간의 힌트로 문제 풀이를 했다. 강의 내용을 통해 얻은 몇가지 힌트는 당연 다이나믹프로그래밍의 핵심은 작은 단위로 문제를 먼저 생각해볼 수 있다는것. 예를 들면 입력값 7부터 생각하는 것이 아니라 1,2부터 생각해보는 것이다. 직관적으로 1m, 2m로 자르는 방법을 생각할 수 있는 단위로 줄여서 생각해보는 것이다.

그리고 문제를 잘 읽는 것이다. 우리가 구하는 것은 자르는 방법이다. 그리고 어떻게 자르는 방법이냐 1m, 2m길이로 자르는 방법이다. 이 문장에서 아이디어를 떠올릴 수 있는데, 부분해에서 추가되는 새로운 길이를 1m가 늘어난 길이 2m가 늘어난 길이로 다시 해석해 볼 수 있다. 이렇게 되면 피보나치와 같은 문제로 위 문제를 해결할 수 있다.

예를 들면 3m는 1m에 2m가 더해진 것이고, 2m에 1m가 더해진 길이이다. 즉 3m는 1m+2m로 2m+1m로 자를 수 있다. 1m 자르는 법과 2m 자르는 법은 직관적으로 또는 작은 문제로 먼저 구한적이 있기 때문에 3m는 1m 자르는법의 수 더하기 2m자르는법의 수로 구할 수 있다.

f(N)이 Nm의 길이의 줄을 자르는 방법 이고, 이를 점화식으로 나타내면 f(N) = f(N-1)+f(N-2)이다.

Code

import sys
#sys.stdin = open("input.txt","rt")

n = int(input())
dy = [0]*(n+1)

dy[0]=0
dy[1]=1
dy[2]=2

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

import sys

def recur(n):
    if n >0:
        if n == 1:
            dy[n] = 1
            return dy[n]
        elif n == 2:
            dy[n] = 2
            return dy[n]
        else:
            if dy[n-1] ==0:
                dy[n-1] = recur(n-1)
            if dy[n-2] ==0:
                dy[n-2] = recur(n-2)
            dy[n] = dy[n-1] + dy[n-2]
            return dy[n]

n = int(input())
dy = [0]*(n+1)

print(recur(n))