SWEA 4869.종이 합치기를 풀면서 DP를 처음 적용해보았다.
DP가 처음이라면 코드없는 프로그래밍님의 영상을 추천한다.
https://www.youtube.com/watch?v=eJC2oetXaNk

이 글의 코드는 위 영상에서 피보나치로 설명하신 부분을 종이 합치기 문제에 적용한 것이다.

재귀 vs DP

재귀

자기 자신을 호출
n을 더이상 쪼개지지 않을 때까지 쪼갠다.(하향식)

def paper_naive(n):
    if n == 1:
        return 1
    elif n == 2:
        return 3
    else:
        return paper_naive(n-1) + 2*paper_naive(n-2)

DP

이전의 계산한 값을 저장함으로써 동일한 계산의 반복 수행 제거

DP + 재귀 (하향식, top-down)

arr = [0, 1, 3]

def paper_recur(n):
    if n < len(arr):
        return arr[n]
    else:
        paper = paper_recur(n-1) + 2*paper_recur(n-2)
        arr.append(paper)
        return paper

• arr : 계산값을 저장해두는 배열
• n을 쪼개면서 모든 결과값을 배열에 저장
• n이 크면 최대 재귀 깊이 초과 에러 발생

DP + 반복 (상향식, bottom-up)

def paper_dp(n):
    if n == 1:
        return 1
    elif n == 2:
        return 3
    arr = [0, 1, 3]
    for i in range(3, n+1):
        paper = arr[i-1] + 2*arr(i-2)
        arr.append(paper)
    return arr[n]

• 반복문을 활용, n이 될때까지 결과값을 배열에 저장
• 상향식에서 발생하는 문제(최대재귀깊이초과) 해결
• 속도 빠름