[BOJ/백준] 1003. 피보나치 함수 - 재귀, 메모이제이션, DP (Python)

 

문제 링크: https://www.acmicpc.net/problem/1003

피보나치 수열에서 원하는 수 n을 호출했을 때, 0과 1이 총 몇 번 호출되는지 묻는 문제

 

접근 1. 재귀

문제에 나온 그대로 피보나치 함수를 구현했다.

def fibo(n):
	if n == 0:
    	return 0
    elif n == 1:
    	return 1
    else:
    	return fibo(n-1) + fibo(n-2)

0이 카운트되는 횟수, 1이 카운트되는 횟수를 따로 변수에 저장해서 풀었지만

결과는 시간초과!

 

 

접근 2. 메모이제이션

피보나치 수열은 fibo(n) = fibo(n-1) + fibo(n-2).

fibo(5)를 예시로 들어보자,

 

fibo(5)

= fibo(4) + fibo(3)

= fibo(3) + fibo(2) + fibo(2) + fibo(1)

= fibo(2) + fibo(1) + fibo(1) + fibo(0) + fibo(1) + fibo(0) + fibo(1)

= fibo(1) + fibo(0) + fibo(1) + fibo(1) + fibo(0) + fibo(1) + fibo(0) + fibo(1)

= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 = 5

불필요하게 앞서 구했던 값을 또또,, 구하는 것을 볼 수 있다.

 

앞서 구현한 fibo(n)의 결과를 따로 저장해두고, 저장해둔 값을 활용하여 계산해본다면?

fibo(5)

= fibo(4) + fibo(3)

fibo(4)와 fibo(3)을 미리 계산해서 저장해둔다면 가져와서 바로 사용할 수 있겠지.

 

fibo함수의 결과값을 memo 리스트에 저장해서 풀어보았다.

import sys; input = sys.stdin.readline

memo = [0 for i in range(41)]

def fibo(n):
    if n == 0:      return 0
    elif n == 1:    return 1
    elif memo[n]:   return memo[n]
    else:           
        memo[n] = fibo(n-1) + fibo(n-2)
        return memo[n]

T = int(input())
for _ in range(T):
    n = int(input())
    if n == 0:
        print(1, 0)
    else:
        print(fibo(n-1), fibo(n))

그런데 풀이하면서 왜 0카운트가 fibo(n-1)이고, 1카운트가 fibo(n)인 것인지 잘 이해되지 않았다.

 

 

접근 3. DP

다시금 피보나치 수열의 규칙성에 대해 생각해보자.

fibo(n) = fibo(n-1) + fibo(n-2)

 

n = 0이라면 각각 0과 1의 호출 횟수는 1 / 0

n = 1이라면 각각 0과 1의 호출 횟수는 0 / 1

n = 2이라면 f(2) = f(1) + f(0) -> 각각 1 / 1

n = 3이라면 f(3) = f(2) + f(1) -> 각각 1 / 2

n = 4이라면 f(4) = f(3) + f(2) -> 각각 2 / 3

n = 5이라면 f(5) = f(4) + f(3) -> 각각 3 / 5

n = 6이라면 f(6) = f(5) + f(4) -> 각각 5 / 8 

 

규칙성을 찾았다.

n = 3일 때의 각각 0과 1의 호출 횟수는, n = 2일 때의 각각의 호출 횟수에서 f(1)을 더한 것!, 즉 n = 2일 때와 1일 때의 호출 횟수 더한 값

n = 4일 때의 각각 0과 1의 호출 횟수는, n = 3일 때의 각각의 호출 횟수에서 f(2)를 더한 것!, 즉 n = 3일 때와 2일 때의 호출 횟수 더한 값

...

 

n일 때의 0 호출 횟수 = n-1일 때의 1 호출 횟수

n일 때의 1 호출 횟수 = n-1일 때의 0과 1 호출 횟수 합

 

임을 알 수 있다.

따라서 이 문제에서 요구하는 것은 0과 1의 호출 횟수이므로, 피보나치 수열을 구현할 필요 없이 아래 코드로 풀이할 수 있다.

import sys; input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    a, b = 1, 0 # 0과 1이 호출된 횟수
    for i in range(n):
        a, b = b, a+b # 0은 n-1에서 1이 호출된 횟수, 1은 n-1에서 0과 1의 호출 횟수 합
    print(a, b)

 

 

느낀점

이런 수학적인 문제는 손으로 그 과정을 처음부터 써보면서 규칙성을 발견하는 것이 중요하구나 깨달았다.

DP 기본적인 문제지만 아직 익숙하지 않아서 어려웠다.

이런 유형을 많이 연습해보자!!!