[알각코] 백준 1003번 - 피보나치 함수

백준 1003번

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

inputN = int(input())

def fibonacci(N):
  print(N)
  global zero
  global one
  if (N == 0):
    zero += 1
  elif (N == 1):
    one += 1
  else:
    return fibonacci(N - 1) + fibonacci(N - 2)

while inputN > 0:
  zero = 0
  one = 0
  fibonacci(int(input()))
  print(zero, one)
  inputN -= 1

일단 이렇게 작성해보았는데, 자꾸 타입에러가 났당

그래서 타입에러를 고쳐보려고 시도하는데, 그것도 잘 안돼서;; 해답을 찾아보았는데, 해답은 전혀 다른거보니…

다른 방식으로 풀어야하는 것 같당

다이나믹 프로그래밍

해당 문제를 서칭해보니 이 문제는 다이나믹 프로그래밍을 활용하여 문제를 풀어야하는 것 같다.

그렇다면 다이나믹 프로그래밍은 무엇일까???

다이나믹 프로그래밍은 우리나라 말로 동적계획법 이라고 한다. 이 아이는 메모리 공간을 조금 더 사용해서 연산 속도를 크게 늘리는 것을 의미한다.

다이나믹 프로그래밍을 적용하는 조건으로는 두 가지가 있다.

큰 문제를 작은 문제로 나눌 수 있다.
작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

즉, 특정 점화식이 적용되는 경우를 얘기하는 것 같다. 피보나치 수열처럼!

다이나믹 프로그래밍으로 문제를 푼다는 것은, 결과를 수행한 것을 메모리에 저장해놔서 그 다음에 같은 결과가 나오는 경우 또 수행하지 않고 메모리에서 바로 갖고와서 연산을 절약할 수 있도록 하는 것이다.

이것을 메모이제이션(캐싱) 기법이라고도 한다.

inputN = int(input())

def fibonacci(N):
  global zero
  global one
  if (N == 0):
    zero += 1
  elif (N == 1):
    one += 1
  else:
    return fibonacci(N - 1) + fibonacci(N - 2)

while inputN > 0:
  zero = 0
  one = 0
  fibonacci(int(input()))
  print(zero, one)
  inputN -= 1

  #... 비록 틀린 풀이이지만 ㅠㅠ

이런식으로 메모이제이션을 활용해서 재귀함수를 구현하여 문제를 푸는 방식을 Top-down 방식이라고 한다.

inputN = int(input())
zero = [1, 0, 1]
one = [0, 1, 1]

while inputN > 0:
  num = int(input())
  if num >= len(zero):
    for i in range(len(zero), num+1):
      zero.append(zero[i-1] + zero[i-2])
      one.append(one[i-1] + one[i-2])
  print(zero[num], one[num])
  inputN -= 1

반면, 위처럼 재귀함수를 사용하지 않고 단순 반복문을 사용하여 다이나믹 프로그래밍을 구현할 수 있는데, 이것을 Bottom-up 방식이라고 한다.

내가 참고한 사이트에서는 웬만하면 Bottom-up 방식으로 다이나믹 프로그래밍 유형의 문제를 풀으라고 권장한다.

나도 그게 훨신 깔끔하다고 느끼는 듯!

백준 1003번

다이나믹 프로그래밍

Reference