동적 프로그래밍 기초 - 피보나치 수열(메모제이션)

코딩 인터뷰 완전 분석이라는 책에서 동적 프로그래밍 공부의 기초로 피보나치 수열 문제를 다뤘었다.

그 때 메모제이션이라는 기법으로 중복 호출되는 부분을 캐시처럼 저장하여 사용하는 방법이 있어서 한 번 훑고 넘어간 적이 있다.

그런데 딱 그 문제가 릿코드 https://leetcode.com/problems/climbing-stairs/ 에서 나왔다!!

리마인드 할 겸 정리하려한다.

기존의 피보나치의 경우 보통 이런 방식이다.

public int climbStairs(int n) {
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        return climbStairs(n-2) + climbStairs(n-1);
    }

하지만 이 피보나치의 재귀 트리를 나타내보면 각 노드는 두 개의 자식 노드를 가지는 구조로써 시간 복잡도가 O(2의 n승)이 된다.

 

왜 O(n) or O(n의 2승)이 아닐까?

각 호출에 소요되는 시간이 O(1)이므로 트리 전체의 노드의 개수와 수행 시간은 같다. 따라서 총 호출 횟수가 수행 시간이 된다.

그로인해 40번째 이후부터 갑자기 걸리는 시간이 급격하게 증가한다.

 

나또한 아무 생각없이 위와같이 풀었다가 n=45에서 타임아웃이 발생하였다.

 

아 이게 그 메모제이션으로 풀어야하는건가보다!! 어떻게 했더라??

바로 책을 펼쳤다.

 

책의 메모제이션이라는 개념을 참고해서 리팩토링 ㄱㄱ

public int climbStairs(int n) {

        //메모제이션을 사용한 피보나치 수열 리팩토링
        return climbStairs(n, new int[n+1]);
    }

    private int climbStairs(int n, int[] memozation) {
        if(n==0 || n==1){
            return 1;
        }
        if(memozation[n] == 0){
            memozation[n] = climbStairs(n-1, memozation ) + climbStairs(n-2, memozation);
        }

        return memozation[n];
    }
}

f(4) = f(3) + f(2)
f(5) = f(4) + f(3)

위의 예를 보면 f(3)이 두 번 호출 된 것을 볼 수 있다.

이런 부분들을 메모제이션으로 저장된 값을 바로 사용함으로써 모든 노드의 개수는 대략 2n개 수행시간은 O(n)이 된다.

기억해두자.