[파이썬 알고리즘 문제풀이] 네트워크 선 자르기(Top-Down : 재귀, 메모이제이션)

문제 :

Note

다이나믹 프로그래밍 문제는 점화식으로 나타낼 수 있고, 점화식으로 나타낸 문제는 재귀로도 구할 수 있다. 재귀를 잘 다루는 방법은 가장 종료시점부터 생각해 보는 것이다. 그리고 함수를 잘 정의해야한다. 이 함수는 무엇을 의미하는지 이 문제를 풀기위해 recur 함수는 dy[N]을 구하는 함수 dy[N]은 Nm길이를 1m,2m로 자르는 방법의 수. 즉 Nm를 1m,2m로 자르는 방법의 수를 구하는 함수이다. 이 함수의 동작 과정을 상태 트리로 표현 한다면 아래와 같다.

 

재귀를 타고 가다보면 중복되는 함수 호출이 발생한다. 이를 메모이제이션 기법을 이용하면 중복되는 연산의 횟수를 줄일 수 있다.

그리고 재귀 함수는 재귀를 타고 내려간 상태에서 생각할 수도 있고, 재귀를 타기 전 부모노드의 위치에서 생각할 수도 있는데

첫 번째 코드는 부모노드에서 생각한 함수이다. 중복된 연산을 줄이기 위해 재귀 호출 함수를 하기 직전에 자식 노드를 호출할지 말지를 미리 체크했다. recur(n)에서 recur(n-1)을 호출할지 말지 recur(n-2)를 호출할지 말지 체크하는 것이다.

두 번째 코드는 자식노드로 내려가서 현재 함수에서 구할 값이 이미 구해졌는지 체크하는 방식으로 호출 횟수를 제한했다. recur(n)은 dy[n]을 구하는게 목적인데 dy[n]이 이미 구해졌다면 recur(n-1)과 recur(n-2)를 재귀 호출 할 필요가 없는 것이다. 바로 dy[n]을 return 해주면 된다.

Code1

import sys

def recur(n):
    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))

Code2

import sys

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

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

print(recur(n))