[백준] 1003번: 피보나치 함수

최근에 백준에 출제된 문제들을 풀기 시작했다.  백준에서 두 번째로 푼 문제는 피보나치 함수였는데, 해당 문제를 푸는 과정에서 배운 점들이 몇 가지 있어 기록차 남겨두고자 한다. 

 

문제의 지문은 다음과 같았다. 

---

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

 

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);
    }
}

 

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

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

---

풀이 # 1 : 

 

피보나치 함수는 난생 처음 접했지만 지문을 천천히 읽으니 코드 구조는 금방 이해가 갔다. (문제를 푼 이후 찾아보니 알고리즘의 기초 격이라 모두가 한 번씩은 다 풀어보는 것 같다) 

 

처음에 떠올린 방법은 0과 1의 횟수를 변수에 저장해 함수가 실행될수록 증가하도록 하는 구조를 만드는 것이었다.  fibonacci(0)이 실행될 때마다 zero 변수의 값을 1씩 증가시키고, fibonacci(1)이 실행될 때마다 one 변수의 값을 1씩 증가시키면 마지막에 누적된 총계를 반환하도록 했다. 

 

예를 들어 fibonacci(3) 일 경우 fibonacci(2) + fibonacci(1) == fibonacci(1) + fibonacci(0) + fibonacci(1) 이 되기 때문에, one = 2, zero = 1  이 되어, (1, 2) 가 반환되는 구조이다. 

 

def find_zero_one(num, zero=0, one=0):

    if num == 0:
        zero += 1
    elif num == 1:
        one += 1
    else:
        a, b = find_zero_one(num-1)
        c, d = find_zero_one(num-2)
        zero = zero + a + c
        one = one + b + d
    return zero, one

첫 번째 풀이 코드를 테스트했을 때는 실행이 잘 되었지만, 이 코드의 문제점은 함수에 입력되는 n의 크기가 증가할수록 연산량도 함께 증가하여, 연산 속도가 터무니없이 느려진다는 점이었다. timeit 모듈을 통해 함수의 속도를 구해본 결과, 30을 입력했을 때 약 0.53초가 걸린다는 사실을 알아냈다.

 

해당 문제에는 0.25s의 시간 제한이 걸려 있었기 때문에, 첫 번째 풀이는 버리고 시간 복잡도 문제를 해결할 다른 방법을 생각해보기로 했다.

---

풀이 # 2 : 

 

피보나치 함수의 구조를 살펴보니 함수 내에서 여러 차례 중복 실행되는 함수가 있다는 사실을 발견했다. 

 

가령, 앞서 얘기한 fibonacci(3)의 경우, fibonacci(1) 함수가 2번 실행되게 되는데, input이 커질수록 당연히 중복 실행으로 인한 속도 저하 현상이 발생할 것이다. 자연스레 '한 번 실행한 함수의 결과값을 저장해두었다가 중복 실행될 경우에는 저장된 값을 불러오기만 하면 되지 않을까?' 하는 생각이 들었다.  이 생각을 직접 구현하기 위해 나는 자료형 중 dict 를 활용했다. Key(함수의 input) 에 따라 Value (함수의 결과값)을 출력하기에 용이할 것이라고 판단했기 때문이다. 

 

def find_zero_one(num):
    if num == 0:           # fib(0)일 경우 0은 1회, 1은 0회 반환
        return 1, 0
    elif num == 1:         # fib(1)일 경우 0은 0회, 1은 1회 반환
        return 0, 1
    else:                  # fib(n), n>=2일 경우
        fib = {0:0, 1:1}
        for n in range(2, num+1):    
            fib[n] = fib[n-1] + fib[n-2]
        return fib[num-1], fib[num]

 

보시다시피 input 이 2보다 같거나 클 경우, dict 를 활용하여 입력받는 수가 증가할 때마다 결과값도 저장하도록 했다.  줄글로 풀어쓰기 어렵지만 코드 내부 구조를 조금 더 구체적으로 풀어보면 이런 형식이다.

반복문의 내부구조

수정된 함수로 아까와 같이 input 을 30으로 했을 때, 연산 속도가 1.0931000000002217e-05 로 줄어들었다. 

 

이렇게 코드를 완성해 제출했다! 

 

# 코드 완성본

num = int(input())

def find_zero_one(num):
    if num == 0:
        return 1, 0
    elif num == 1:
        return 0, 1
    else:
        fib = {0:0, 1:1}
        for n in range(2, num+1):
            fib[n] = fib[n-1] + fib[n-2]
        return fib[num-1], fib[num]

for i in range(num):

    n = int(input())
    result = find_zero_one(n)
    print(result[0], result[1])

---

주의할 점 : 

 

알고리즘을 풀며 코드를 짤 때 주의해야 하는 점 몇 가지를 체득할 수 있었는데, 잘 기억해두면 나중에 직접 개발을 할 때도 도움이 될 것 같아 적어본다. 

 

1. 전제조건을 잘 확인하자.

• 시간 제한이 있는 줄 모르고 완성한 코드는 결국 '조건을 충족하지 않는' 코드였다. 무조건 결과가 잘 나온다고 좋아할 것이 아니라 목적에 맞는, 요구사항에 맞는 코드를 짜야 한다.
• 값이 어떤 식으로 입력되는지 잘 살펴보자. input() 부분을 잘못 이해하는 바람에 시간을 낭비했다.

2. 시간 복잡도 (Time complexity)를 늘 고려하자.

• 전제 조건에 포함된 사항이 아니더라도, 시간 복잡도를 줄이는 것은 개발 실력을 키울 수 있는 중요한 방법이다. 늘 '더 나은 방법'을 고민하며 코드를 짜야 한다.