[알고리즘] 백준 1003 피보나치 함수

📖문제

1003 피보나치 함수

 

 

❓구상

피보나치 함수는 대표적인 동적 프로그래밍(Dynamic Programming) 계획법으로 풀 수 있는 문제이다.

우선 문제를 보니 N번째 피보나치 수를 구하는 C++ 함수의 예제가 나와있다.

일단 간단하게 생각하고 fibonacci(n) 에서 n이 0과 1인 경우를 카운팅하면 문제에서 요구하는 출력을 볼 수 있을 것으로 기대 된다.

한번 코드를 살펴보자.

 

시도한 코드.

const [T, ...arr] = require("fs").readFileSync("/dev/stdin", "utf-8").trim().split("\n").map(Number);
const result = new Array(T);
let line = [0, 0];
const fibo = (n) => {
  if (n === 0) {
    line[0] += 1;
    return 0;
  }
  if (n === 1) {
    line[1] += 1;
    return 1;
  }
  return fibo(n - 1) + fibo(n - 2);
};
arr.forEach((e, i) => {
  fibo(e);
  result[i] = line.join(" ");
  line = [0, 0];
});
console.log(result.join("\n"));

 

재귀 함수

1. 모든 배열 순회
2. element 를 fibo 함수에 인자로 넘겨준다.
3. 재귀함수를 통해 fibo 함수의 인자로 0과 1이 전달 되는 것을 카운팅 한다.

 

처음에는 별 의심 없이 문제에서 제공된 함수를 그대로 사용하는 방식을 시도해보았다.

우선 동작을 해보면 기본 예제 입력에 대한 출력은 문제 없이 나오는 것을 확인했고 이 것으로 문제를 제출해보았다.

 

결과는.

 

출력에는 전혀 문제가 없지만 이 코드의 시간 복잡도를 분석해보면

 

1. fibo 함수의 동작

• fibo 함수는 재귀적으로 피보나치 수를 계산한다.
• 재귀 호출은 아래와 같이 이루어진다.
  • fibo(n) 은 fibo(n-1) 과 fibo(n-2) 를 호출한다.
  • 호출 트리는 이진 트리처럼 동작하며, 트리의 깊이는 n 이다.
• 트리의 노드 개수는 2^n 에 비례하므로, 재귀 호출의 시간 복잡도는 O(2^n) 이다.

2. 전체 코드의 동작

• 입력 T : 테스트 케이스의 개수
• 입력 배열 arr : 각 테스트 케이스 n 값이 저장된 배열
• 칵 테스트 케이스 e 에 대해 fibo(e) 를 호출
  • 각각의 fibo(e) 호출은 O(2^n) 의 시간 복잡도를 갖음.

3. 최종 시간 복잡도

모든 테스트 케이스를 처리하는 데 걸리는 시간 복잡도는 O(T*2^n) 을 갖는다.

 

그렇기 때문에 n 이 작은 수인 경우 큰 문제가 없을 수 있지만, 이 문제는 N 이 40보다 작고 0보다 큰 수 이기 때문에 제약 조건인 0.25 초 를 초과하는 경우가 발생하게 되는 것이다.

그렇게 때문에 이 문제는 단순 재귀로 푸는 것이 아닌 동적 프로그래밍 계획법을 활용해 푸는 것이 옳바른 것이다.

코드.

const [T, ...arr] = require("fs")
  .readFileSync("/dev/stdin", "utf-8")
  .trim()
  .split("\n")
  .map(Number);
const result = [];
const fibo = (N) => {
  let dp = [];
  for (let i = 0; i <= N; i++) {
    if (i === 0) dp[i] = [1, 0];
    else if (i === 1) dp[i] = [0, 1];
    else dp[i] = [dp[i - 1][0] + dp[i - 2][0], dp[i - 1][1] + dp[i - 2][1]];
  }
  return dp[N].join(" ");
};
arr.forEach((e) => result.push(fibo(e)));
console.log(result.join("\n"));

 

동적 계획법

동적 계획법은 문제를 작은 단위의 문제로 쪼개 그 패턴을 메모이제이션 하는 방식으로 값을 계속 만드는 것이 아닌, 저장된 값이 다음 값의 계산에 이용되는 방식이다. 

처음에는 이 문제를 처음에 시도한 코드의 함수부분을 하향식으로 구현하면 시간 복잡도가 개선되지 않을까 생각했다.

하지만, 단순히 피보나치 함수에 하향식을 적용하면 중복 계산을 최대한 줄이는 과정속에 0과 1의 카운팅은 당연히 제대로 될 수 없었다.

그래서 결과 값의 패턴에 집중해 보았고 그 결과

n = 0 : [0갯수, 1갯수] = [1, 0]
n = 1  : [0갯수, 1갯수] = [0, 1]
n = 2  : [0갯수, 1갯수] = [1, 1]
n = 3  : [0갯수, 1갯수] = [1, 2]
.
.

 

0의 갯수와 1의 갯수가 n-1 의 0, 1 갯수와 n-2 의 0, 1 갯수의 합과 같음을 알았다.

그렇기에 n 이 0 인 경우와 1 인경우의 값을 dp 배열에 메모이제이션 시키고 그 값을 바탕으로 값을 구해나가면 이 문제를 해결 할 수 있다.

 

🔥배운 점

실버3 등급의 문제라 당연히 문제에서 제공된 함수로 풀리지 않을 것을 알았지만, 단순히 그 함수를 타뷸레이션에서 하향식으로 변경해서 풀려 하다보니 고정관념에 휩싸인거 같다.

동적 프로그래밍의 핵심 개념이 메모이제이션도 있지만, 좀더 디테일하게 보자면 큰 문제를 작은 단위의 문제로 분해 하여 패턴을 파악해야하는 점을 관가했다. 평소에 dp 문제를 보면 항상 피보나치 함수 문제처럼 풀릴 거라는 안일한 생각에 빠져 패턴파악을 못해서 이 동적 계획법 문제가 나오면 새로운 패턴을 적용할 생각을 못했는데, 이 문제를 풀면서 동적계획법을 조금 더 이해할 수 있게 됐다.