(JAVA) 백준 문제 풀이 - 동적계획법 단계 - 24416번 알고리즘 수업 - 피보나치 수열 (브론즈 1)

이번 문제는 동적 프로그래밍을 이용하여 피보나치 수열을 풀어보는 문제이다.

기존에 재귀를 이용하여 피보나치 수열을 계산하는 것을 해보았지만, 이번에는 동적 프로그래밍을 이용하여 더 빠르고 효율적인 프로그래밍을 하는것이 목적이다.

그럼 우선 동적 계획법에 대해서 자세하게 살펴보자.

---

동적 계획법(Dynamic Programming) 이란...

동적 계획법(줄여서 DP라고 부르기도 한다.) 을 간단하게 설명하면 답을 재활용하는 것이다. 

좀 더 본질적인 의미를 살리자면 기억하며 풀기라고 생각해도 되겠다.

어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거의 구한 해를 활용하는 것이 동적 계획법의 핵심이다.

문제를 작은 문제로 쪼개어 생각한다는 점에서 분할 정복 알고리즘과 비슷하게 보이기도 한다.

다만, 두 알고리즘의 차이는 한번 계산한 부분을 저장해두고 다시 이용한다는 점에서 다르다.

이 때문에, 동적 계획법에서는 한번 푼 문제를 어떻게 최대한 많이 이용할 것인가가 속도 향상에 가장 중요한 부분이 된다.

---

왜 동적 계획법을 사용해야 하는가?

그럼 어떤 상황에서 동적 계획법을 사용하는가?

이번 문제인 피보나치 수열 계산을 생각해보자.

위 문제를 재귀로 구성하면 굉장히 심플하다.

fib(n) {
    if (n = 1 or n = 2)
    then return 1;  # 코드1
    else return (fib(n - 1) + fib(n - 2));
}

어떤 숫자 n이 주어지면 n-1 + n-2를 계속하여 호출하면 되기 때문이다.

그런데 이렇게 하면 n이 늘어날수록 함수 호출은 기하급수적으로 늘어나게 된다.

시간 복잡도야 어떻게든 한다고 해도 공간 복잡도의 경우 스택이 과도하게 쌓이면 스택 오버플로우라고 하여 프로그램이 튕겨버리게 되기 때문에 아예 쓸모없는 프로그램이 되어버리는것.

 

동적 계획법은 이런 상황을 방지하기 위해서 이미 한번 풀었던 문제는 저장해두고 같은 문제를 다시 호출하는 경우 저장된 값을 가져와서 사용하는 방식으로 해결한다.

다만, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용 할 수 없다.

 

그럼 피보나치 수열을 살펴보자. 피보나치 수열의 함수 호출 트리는 다음과 같다.

 

위 그림을 보면 알 수 있듯, f(3), f(2), f(1)이 중복되어 나타나는 것을 확인 할 수 있다.

그 말은, 한번 계산된 값을 재활용 할수 있다는 의미가 된다.

그렇다면 본격적으로 동적 계획법의 형태로 피보나치 수열을 계산해 보자!

---

Top-Down과 Bottom-UP

동적계획법의 대표적인 방법으로는 Top-Down과 Bottom-Up 방식이 있다.

문자 그대로, 위에서부터 하위로 내려오는 것과, 밑에서부터 위로 올라가는 방식이다.

즉, Top-Down은 큰 문제부터 작은 문제로 분할해 가는 것이고, Bottom-Up은 작은 문제부터 쌓아서 큰 문제로 합하는 것이다.

그럼 코드를 살펴보자.

 

1.Top-Down

int memo[100]{}; //메모이제이션 공간. 전역 변수이므로 0으로 초기화
int fibonacci(unsigned int n)
{
  if (n<=1) //0번째, 1번째 피보나치 수
    return n;
  if (memo[n]!=0) //메모가 있는지 확인(0으로 초기화되었으므로 0이 아니라면 메모가 쓰인 것임)
    return memo[n]; //메모 리턴
  memo[n]=fibonacci(n-1) + fibonacci(n-2); //작은 문제로 분할
  return memo[n];
}

코드를 보면 똑같이 재귀하지만 재귀를 할때 값을 배열에 저장하는 것을 알 수 있다.

그리고 배열에 값이 있는 경우(이미 한번 풀었던 문제를 뜻한다) 바로 해당 인덱스의 값을 리턴한다.

이렇게 하면 풀었던 것을 또 풀지 않고 바로 다음으로 넘어 갈 수 있게 되는 것이다.

 

2.Bottom-Up

int f_data[N] = {1, 1}; // N은 정의하기 나름
int last_pos = 1; // 마지막으로 계산한 지점. 이 코드에선 이미 f_data[1]까지 정의되어있기 때문에 1로 초기화한다.
int f(int n) //피보나치 수열의 제 n항을 구한다. 배열의 관점에서는 n-1번째 요소를 구하는 것.
{
    int i;
    if(f_data[n-1] == 0)  // 아직 구한 적이 없으면 구한다
    {
        for(i=last_pos+1; i<n; ++i)
        {
            f_data[i] = f_data[i-1] + f_data[i-2];
        }
        last_pos = n-1;
    }
    return f_data[n-1];
}

Bottom-Up은 반대로 제일 아래 값을 먼저 계산 한 후, 위로 올라가면서 값을 채워 나가는 형태이다.

for문 마지막에 최종값을 반환하므로 우리는 피보나치 n항을 반환받을 수 있다.

 

중간에 주석을 보면 Memoization이라는 말이 나오는데 간단하게 설명하면 가장 최근에 메모된 상태값이라고 생각하면 되겠다.

앞서 설명하였듯이 동적 계획법의 핵심은 계산된 값을 저장해두고 재활용 하는 것인데 이 저장해 두는 것을 메모하는 것과 같다고 해서 Memoization이라고 부른다. 

단, memoization은 Top-Down 방식에서 해당 되고 Bottom-Up 방식에서는 Tabulation이라고 부르니 헷갈리지 말자.

 

나는 위의 코드를 적용하여 다음과 같이 문제를 풀었다.

import java.io.*;
import java.util.*;

class Main{
    public static int n,cnt;
    public static StringBuilder sb = new StringBuilder();
    public static int[] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        br.close();
        arr = new int[n+1];

        sb.append(fib(n));
        fibo(n);
        sb.append(" ").append(cnt);
        System.out.println(sb.toString());
    }

    public static int fib(int n){
        if(n== 1 || n == 2) return 1;
        else return (fib(n-1) + fib(n-2));
    }

    public static int fibo(int n){
        arr[0] = arr[1] = 1;

        for (int i = 2; i < n; i++) {
            cnt++;
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n-1];
    }
}

Bottom-Up 방식을 적용하여 해결하였는데, 우리가 출력해야 하는 값은 해당 항의 값이 아니라, 함수가 얼마나 사용 되었는지이므로 중간에 cnt라는 int값을 사용하여 함수 출력 횟수를 계산하였다.

정리하다가 중간에 생각난 것인데 사실 중간에 fib함수는 쓸 필요가 없이 fibo에서 리턴된 최종 값을 반환해도 무방하다.

어차피 재귀는 피보나치의 n항만큼 재귀하기 때문에 값과 호출 횟수가 동일하기 때문이다.

---

참고 자료

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법 - 나무위키

https://hongjw1938.tistory.com/47