계단오르기 문제를 재귀함수를 이용해서 풀려고 하다가 동적계획법에 대해 알게되어 관련 내용을 정리해본다
동적계획법이란?
- 복잡한 문제를 간단한 여러개의 문제로 나눠 푸는 방법
- 부분 문제 반복(Overlapping subproblems)와 최적 부분 구조(Optimal substructure)를 가지고 있는 알고리즘을 짧은 시간 안에 풀 때 사용
이해하기 쉬운 예시로 피보나치 수열에 대해 살펴보자
재귀함수 형태의 피보나치 수열
수학적인 정의로 볼때, 매우 간단하고 명료하게 표현할 수있지만,
컴퓨터가 계산하기에는 부적합하다고 한다.
f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2) when n > 1
파이썬에서는 재귀함수를 이용해 간단하게 함수를 만들어볼 수 있다.
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)n이 작은 값일 때는 괜찮지만, n이 조금만 커져도 시간복잡도와 공간복잡도가 기하급수적으로 증가하게 된다. n = 35쯤 입력하면 멍하게 있는 자신을 보게 된다.
동적 계획법 형태의 피보나치 수열
동적계획법에서는 반복되는 계산을 막기 위해 이전에 계산했던 내용을 배열에 저장한다.
대표적으로는 top-down과 bottom-up이 있다고 한다.
Top-down
메모이제이션(memoization)을 이용한 재귀함수 방식
큰 문제부터 시작해서 작은 문제로 분할해가면서 풀 수 있는데, 계산된 값들을 메모리에 저장해서 다시 계산하지 않아도 된다.
def fib_2(n):
d = [0]*(n+1)
def fib(n):
if n == 1 or n == 2:
return 1
if d[n] != 0:
return d[n]
d[n] = fib(n-1) + fib(n-2)
return d[n]
return fib(n)Bottom-up
최초 값부터 차례대로 계산해 table에 저장하는 타뷸레이션(Tabulation)방식
시작부분은 f(0), f(1)부터 시작해 더해가면서 최종적으로 f(n)에 도달한다.
def fib_3(n):
F = [0 , 1]
for i in range(2, n+1):
F.append(F[-1] + F[-2])
return F[-1]계단오르기 문제
최대 한 번에 m개의 계단을 올라갈 수 있을때, n개의 계단을 올라가는 방법의 수는?
점화식을 생각해보면 마지막에 한 번에 얼마의 계단을 올라가느냐를 고민해보면 된다.
최대 m 계단을 올라갈 수 있다면,
마지막에 1계단 + 마지막에 2계단 + ... + 마지막에 m계단 올라간 경우
f(n, m) = f(n-1, m) + f(n-2, m) + ... + f(n-m+1, m) + f(n-m, m)
초기 조건
- 최대 올라갈 수 있는 계단수가 1이라면 가능한 경우의 수 => 1가지
- n < m 일 경우 f(n, m) = f(n, n)
- n == m 일 경우, f(n, n) = f(n-1, n-1) * 2
a) 1 계단을 먼저 올라가고, m-1 계단을 올라가는 경우의 수
b) m-1 계단을 먼저 올라가고, 1계단을 올라가는 경우의 수
c) m계단을 한 번에 올라가는 경우의 수
이때, 1과 2에서 1계단 씩 만으로 올라가는 경우가 겹치므로
f(n, n) = f(n-1) + f(n-1) - 1 + 1
결과적으로 값이 도출 되려면 f(n-1, m) ~ f(n-m, m)까지의 값이 보장되어야 하므로,
n <= m 인 값들에 초기 값을 부여해 주어야 하는 것 같다
def clmb(n, m):
memo = [[0] * (m+1) for _ in range(n+1)]
def clmb_recur(n,m):
if n < 1 or m < 1:
return 0
elif m == 1:
return 1
elif n == m:
return 2 * clmb_recur(n-1, n-1)
elif n < m:
return clmb_recur(n, n)
for i in range(1, m+1):
memo[n][m] += clmb_recur(n-i, m)
return memo[n][m]
return clmb_recur(n, m)
