동적 프로그래밍은 한 번 계산된 값을 메모리에 저장한 후, 저장된 값을… | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지

동적 프로그래밍은 한 번 계산된 값을 메모리에 저장한 후, 저장된 값을 필요할 때마다 가져다 쓰는 방법이다. 동적 프로그래밍을 적용하여 구현한 다음 Java 프로그램에서 피보나치 수열 fibo(6)을 구하기 위해 저장되어 있는 fibo(3)의 결과를 가져다 쓰는 횟수는?
public class Fibonacci {
    static int[] dp = new int[100];

    public static void main(String[] args) {
        System.out.println(fibo(6));
    }

    public static int fibo(int num) {
        if(num == 0) {
            return 0;
        }
        if(num == 1) {
            return 1;
        }
        if(dp[num] != 0) {
            return dp[num];
        }
        return dp[num] = fibo(num - 1) + fibo(num - 2);
    }
}

0

1

2

3

fibo(6)을 구하는 동안 저장된 fibo(3)의 값을 꺼내 쓰는 것은 한 번이다.
호출은 fibo(6)→fibo(5)→fibo(4)→fibo(3)→fibo(2) 순으로 왼쪽 가지를 먼저 내려가며 dp[2]·dp[3]·dp[4]·dp[5]를 차례로 저장한다.
fibo(3)은 fibo(4) 안에서 처음 계산되고, 이후 fibo(5)가 오른쪽 가지로 fibo(3)을 부를 때 dp[3]을 반환한다. fibo(6)의 오른쪽 가지 fibo(4)는 dp[4]에서 바로 반환되므로 fibo(3)을 다시 부르지 않는다.
0회는 fibo(5)의 오른쪽 호출이 저장값으로 처리된다는 점을 놓친 것이다.
2회나 3회는 저장값이 없을 때처럼 fibo(4)를 다시 전개한 경우로, 메모이제이션에서는 일어나지 않는다.