[Java] 피보나치수열 with memoization

피보나치 수열

1, 1, 2, 3, 5, 8, 13, 21, ...

public class Fibo {
    public static long fiboByRecursion(long n) {
        if (n == 1 || n == 2)
            return 1;
        
        return fibo(n-1) + fibo(n-2);
    }
    
    public static long fiboByLoop(long n) {
        if (n == 1 || n == 2)
            return 1;
        
        long sum = 1;
        long prev = 1;
        long temp;
        
        for(long i=3; i<=n; i++) {
            // sum은 n-1
            // prev는 n-2
            temp = sum;
            sum = sum + prev;  // n-1 + n-2
            prev = temp;       // n-2에 n-1을 대입
        }
        
        return sum;
        
    }
    
    public static void main(String[] args) {
        System.out.println( Fibo.fiboByRecursion(10) );
        System.out.println( Fibo.fiboByLoop(10) );
    }
}

n이 작을때는 문제 없으나 40 이상으로 넘어가면 수행시간이 기하급수적으로 증가한다.

중복계산을 없애기 위해 memoization을 사용하자.

반환형이 long임에도 n이 커지면 오버플로가 발생할 수 있다는 점을 유의하자. 

public class Fibo {
    
    static final long memo[] = new long[200];
    
    public static long fibo(long n) {
        
        if(memo[n] > 0)
            return memo[n];
        
        if (n == 1 || n == 2)
            return memo[n] = 1;
        
        return memo[n] = fibo(n-1) + fibo(n-2);
    }
    
    public static void main(String[] args) {
        System.out.println( Fibo.fibo(8) );
    }
}

memoization을 적용하였다

TBC

#1

0과 1로 이루어진 문자열이 있다. 이 문자열에는 1이 연속하여 나올 수 있지만 0이 연속하여 나올 수는 없다.

예를 들어 1111, 110111, 010101, 1101110은 올바른 문자열이지만 000, 1100111 등은 잘못된 문자열이다.

길이가 n인 올바른 문자열은 몇 개일까?

#2

n개의 계단을 한 번에 하나 또는 두개씩 올라간다. n개의 계단이 있을 때 이를 올라가는 방법은 몇 가지인가?

#3

매일 1/2 확률로 회사에 지각하는 사람이 있다. 3일 연속 지각했을때에만 팀장에게 혼난다. 20일간 출근할 때, 한 번도 혼나지 않을 확률은 얼마일까? 매일 2/3 확률로 지각할 경우의 확률은?