[알고리즘-백준(DP)] 백준 2748(DP), 10870(Recursive) 피보나치의 수 차이

이번 포스팅에서 동적 프로그래밍(DP, 동적 계획법, 메모이제이션 풀이) 에 대한 간단한 정의와 문제 풀이를 해볼 것이다

동적 계획법에 대한 깊은 이해와 이론적 설명은 추후에 알고리즘 이론 에서 다루기로 하겠다.

 

동적 계획법이란?

 

피보나치 수열을 동적 계획법에 표현을 하곤 한다.

 

동적 프로그래밍은 큰 문제를 작은 문제로 나누어 해결하려는 문재 해결 전략이다.

 

이는 분할 정복과 특정 문제의 재귀 호출 비슷한 개념이지만 가장 큰 차이점은 메모이제이션(Memoization) 을 하느냐 안 하느냐에 따라 달렸다고 한다.

Memoization

 

메모제이션이란, DP에서 작은 문제들이 해결될 때 해당 결과를 저장하여 다른 부분의 동일한 계산에, 저장된 결과를 사용하는 것을 뜻한다.

메모이제이션을 효과적으로 설명하기 위해서는 피보나치 수열을 이용한 DP가 가장 효율적인데 한 번 바로 확인해보자.

 

백준 10870번 : 재귀호출

 

백준 문제 10870 은 재귀호출을 이용해서 피보나치 수열을 완성시키는 것이 목적인데 아래의 입력을 잘 봐보자.

n이 20보다 작거나 같은 자연수로 제한되어 있는데 수행 시간은 1초이다.

 

package stage.stage09_Recursive;

import java.util.Scanner;

public class Prob02_FibonacciNumvbers {

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        int num = input.nextInt();

        System.out.println(fibonacci(num));

    }

    private static int fibonacci(int num){

        if(num >= 2) return fibonacci(num - 1) + fibonacci(num - 2);

        else return num;

    }
}

 

위와 같은 코드로 피보나치 수를 재귀호출 한다면 시간 복잡도는 2^n 이 될 것이다. 하지만 문제에서 봤듯이 n이 20보다 작거나 같은 자연수를 이 시간 복잡도에 적용한다면

 

 

100만이 조금 넘는 수로 1초에 1억번 계산을 한다는 가정하에 충분히 피보나치를 재귀 호출로써 해결해도 된다는 소리다

 

하지만 n이 커진다면 어떻게 될까?

 

이러한 물음에서 동적 프로그래밍이 시작한다.

 

동적 프로그래밍은 아까 위에서 말 했듯 메모제이션으로 메모리의 낭비를 줄인다고 했는데 위와 같은 방식의 재귀 호출이 심각한 메모리의 낭비가 있다는 것을 알 수 있다.

 

private static int fibonacci(int num){
    if(num >= 2) return fibonacci(num - 1) + fibonacci(num - 2);
    else return num;
}

 

만약 n 6이면

 

 

이런 식으로 중복이 계속 누적되고 결국 필요없는 메모리의 낭비가 존재한다. 백준의 2748번과 같이 n이 90까지 허용된다면 다음과 같은 동적 프로그래밍으로 해결해야 바람직하다.

 

백준 2748번 : 동적 계획법

 

 

이에 대한 코드를 동적 프로그래밍의 메모제이션을 이용하여 풀어보자면 다음과 같다. (코드를 유심하게 보길 바란다)

 

package stage.stage09_Recursive;

import java.util.Scanner;

public class Prob03_Fibonacci2 {

    static long[] memo;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        memo = new long[91]; // 기억할 공간이 n 만큼이므로 n+1을 할당

        int n = input.nextInt();

        System.out.println(fibonacci(n));
    }

    private static long fibonacci(int n){

        if(n <= 1)  return n; //fibonacci(0) 와 fibonacci(1)은 각각 0과 1이 므로 바로 return

        else { // 그렇지 않을 경우

            if(memo[n] > 0) return memo[n]; //메모에 값이 저장된 경우

            else memo[n] = fibonacci(n - 1) + fibonacci(n - 2); // 값이 저장되지 않은 경우

            return memo[n];
        }
    }
}

 

위와 같이 static 필드로 memo라는 배열에 값을 담고 한 번 fibonacci() 메서드가 수행되면 memo에 값을 먼저 검사한 뒤 memo에 대한 결과가 없을 때만 재귀적으로 호출하는 방식을 바로 DP적 풀이라고 한다.