[JAVA] 피보나치 수열

문제 유형

DP(다이나믹 프로그래밍)이고 DP 알고리즘의 핵심 중 하나인 메모이제이션 알고리즘을 이용해서 풀어야 한다. 메모이제이션 알고리즘은 중복되는 결과를 저장함으로써 알고리즘의 실행 속도를 향상시킬 수 있다.

 

재귀를 이용해서 풀 수도 있지만 재귀의 경우 숫자가 커지면 중복되는 메소드가 많아져서 실행 속도가 느려진다.

fibo(2)를 구할 때 fibo(1)을 한 번만 구해도 되지만 fibo(6)을 구하려면 fibo(1)을 8번 호출해야한다. 이미 구한 값을 또 계산할 필요가 있을까? 따라서 메모이제이션 방법을 추천한다.

 

풀이법

1.재귀적으로 푼다.

2. for문과 배열을 이용해 메모이제이션 알고리즘을 사용한다.

 

코드1: 재귀

public class Main {

    public int fibo(int N) {
        if (N == 1)
            return 1;
        else if (N == 2)
            return 1;
        else return fibo(N-2) + fibo(N-1);
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        for (int i=1; i<=N; i++) {
            System.out.print(T.fibo(i) + " ");
        }
    }
}

코드2:메모이제이션

import java.util.Scanner;

public class Main {

    static int[] dp;    // dp 배열 선언
    public int fibo(int N) {
        if (dp[N] > 0) return dp[N];    // 0이 아니면 미리 구한 값
        if (N == 1) return dp[N]=1;
        else if (N == 2) return dp[N] = 1;
        else return dp[N] = fibo(N-2) + fibo(N-1);  // 구한 값은 배열에 저장하고 리턴한다.
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        dp = new int[46];   // 인덱스는 항 번호를 의미하고 원소값은 항의 값을 의미한다.
        for (int i=1; i<=N; i++) {
            System.out.print(T.fibo(i) + " ");
        }
    }
}

느낀 점

피보나치를 재귀와 메모이제이션으로 푸는 방법을 잘 숙지하고 차이점도 잘 숙지하자. 코딩 인터뷰에 자주 등장하는 소재다.