[알고리즘, Python] 재귀(Recursion)와 동적 프로그래밍(Dynamic Programming) | Leetcode N-th Tribonacci Number

Recursion과 Dynamic Programming에 대해 간략하게 정리하고 Leetcode 문제를 풀어보자.

---

Recursive solution은 한 문제를 여러 서브 문제로 쪼개 결과를 합치는 방법이다.

 

이러한 Recursive solution에는 크게 세 가지의 접근 방식이 있다.

 

바로 Top-down approach, bottom-up approach, 그리고 half-and-half approach다.

 

bottom-up 은 f(0) -> f(1) -> f(2)->...->f(n) 이런 식이고, 탑다운은 반대로 생각하면 된다.

 

하프앤하프의 대표적인 예로는 binary search와 merge sort가 있다.

---

Recursion

우선 Recursion은 공간복잡도가 비효율적이다.

 

모든 Recursive 알고리즘은 iterative 하게 구현 가능하므로, 재귀를 이용한 방법보다 복잡할지라도 반복으로 구현하는 것이 좋다.

 

Dynamic Programming

Dynamic Programming이란 recursive 알고리즘에서 중복되는 subproblems 즉 반복되는 호출을 찾고 그 호출 결과를 cache하는 것을 말한다.

---

Leetcode에서 tribonacci 문제를 풀기 전에 대표 예제로 사용되는 피보나치를 통해 각 방법이 어떻게 다른지 정리해보자.

 

1. 재귀 알고리즘

우선 재귀 알고리즘으로 구현해보자.

def fibonacci(n):
    if i == 0:
    	return 0
    if i == 1:
    	return 1
    return fibonacci(n-1) + fibonacci(n-2)

이 경우 런타임은 무엇일까?

 

호출하는 경우를 트리 그림으로 그려보면 대략 O(2^n)이라는 것을 쉽게 알 수 있다. (실제로는 약 O(1.6^n)정도 된다)

2.  Top-down 동적 프로그래밍 (Memoization)

다음은 탑다운 방식으로 구현해보자.

def fibonacci(i):
    if i == 0 or i == 1:
        return i
    if memo[i] == 0:
        memo[i] = fibonacci(i-1, memo) + fibonacci(i-2, memo)
    return memo[i]

이 경우 런타임은 O(n)이 된다. (트리로 생각해보면 대략 2n개의 노드가 있다.)

3. Bottom-up 동적 프로그래밍

마지막으로 bottom-up으로 구현해보자.

def fibonacci(n):
    if n == 0 or n == 1:
        return n
    memo = [0] * (n+1)
    memo[0] = 0
    memo[1] = 1
    for i in range(2, n):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[n-1] + memo[n-2]

f(0)과 f(1) 값을 알고 f(2)부터 차례대로 값을 구해 최종 f(n)을 구하는 방법이다.

 

그런데 이 방법을 자세히 보면 굳이 memo array를 사용하지 않고도 단순히 변수 두 개로 문제를 해결할 수 있다는 점을 알 수 있다.

def fibonacci(n):
    if n == 0:
        return 0
    a, b = 0, 1
    for i in range(2, n):
        c = a + b
        a = b
        b = c
    return a + b

---

이제 트리보나치 수열을 구현해보자.

 

Leecode에서 문제보기

https://leetcode.com/problems/n-th-tribonacci-number/

N-th Tribonacci Number - LeetCode

---

피보나치와 비슷하게 접근하자.

 

t0 = 0, t1 = 1, t2 = 1이다.

 

t_n = t_n-3 + t_n-2 + t_n-1 이므로  t3 = t0 + t1 + t2, t4 = t1 + t2 + t3 ... 이런순서로 계산하게 된다.

 

따라서 순서대로 t값을 구해서 t_n 에 도달하면 반복문을 멈추는 방법으로 구현할 수 있다.

def tribonacci(n):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1

    n3, n2, n1 = 0, 1, 1

    for _ in range(2, n):
        n3, n2, n1 = n2, n1, n3+n2+n1
    return n1

---

Reference

- Cracking the Coding Interview - Chapter 8. Recursion and Dynamic Programming