재귀 소개 및 DP의 맛

알고리즘 문제를 풀다보면 맞닥뜨리는 흔한 문제는 재귀와 DP다.

 

하지만 일반적으로 재귀적 사고를 한다는 것 자체가 쉽지 않다. 다양한 문제를 풀면서 내가 느낀건

1. 반복 되는게 있어야 한다. => 문제를 더 작게 만들 수 있어야 한다.
2. 탈출 지점이 있어야 한다.

여기서 더 중요한 건 2번이다. 탈출 지점이 정확하게 없으면 재귀적으로 풀 수 없다.

 

재귀의 대명사 피보나치 수열을 풀어봤다.

def fibo(n):
    if n <= 1:
        return n

    return fibo(n-1) + fibo(n-2)

재귀적인 함수를 작성 할 때는 항상 탈출문 먼저 작성하는게 좋다. 피보나치 수열도 정말 다양한 방식으로 구현 할 수 있다. 내가 구현한 방법은 그 중 하나.

위의 함수로 로컬 머신에서 n=35의 실행시간을 측정해보니 대략 40초가 나온다. 음-청 느리다.

 

여기에 Memoization을 묻혀 보려고 한다. DP를 사용하는데 핵심 기술이기 때문에 여기서 먼저.

def fibo(n, lookup):
    if n <= 1:
        lookup[n] = n

    if lookup[n] is None:
        lookup[n] = fibo(n-1, lookup) + fibo(n-2, lookup)

    return lookup[n]

 

위의 코드는 대략 0.001초가 나온다. 성능 차이가 굉장하기 때문에 메모리 공간을 더 사용하는게 전혀 아깝지 않다.

 

DP의 핵심 기술인 Memoization의 맛을 봤다. 다음엔 DP를 다뤄보자.