추석맞이 코딩 문제 챌린지 LV.1 피보나치수

 

[추석맞이 코딩챌린지①] 피보나치수

 

 

문제

피보나치수열은 수학에서 아래의 점화식으로 정의되는 수열이다.

피보나치 수는 0번째 숫자인 0과 첫 번째 숫자인 1로 시작하며,

두 번째 숫자는 0번째 수와 첫 번째 수의 합인 0 + 1 = 1,

세 번째 숫자는 첫 번째 수와 두 번째 수의 합인 1 + 1 = 2 의 값을 가진다.

 

숫자 n을 입력받아 피보나치수열의 n번째 숫자를 출력하는 프로그램을 작성해보세요.

 

조건

• 입력받는 숫자 n은 2 이상의 자연수입니다.
• n > 1인 피보나치 수에서, n번째 수 = (n - 2) 번째 수 + (n - 1) 번째 수입니다.
• 피보나치수열을 나열하면 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 입니다.

 

입출력 예시

예제 입력 1

10

예제 출력 1

55

 

예제 입력 2

15

예제 출력 2

610

 

 

---

힌트

반복문을 사용하여 쉽게 풀이할 수 있는 문제다.

 

---

정답 코드

- C언어

#include <stdio.h>

int main()
{
    /*
    피보나치 수
    a에는 n - 1번째 수, b에는 n번째 수를 저장
    */
    int a = 0, b = 1, n;

    // 숫자 n을 입력
    scanf("%d", &n);

    if(n == 0 || n == 1) printf("%d", n);       // 0번째와 1번째 피보나치 수는 n을 그대로 출력
    else{
        for(int i = 2; i < n + 1; i++){         // n이 2 이상일 경우에는 반복문으로 n번째 피보나치 수를 구함
            int next = a + b;
            a = b;
            b = next;
        }

        printf("%d", b);
    }
    return 0;
}

- Python

# 피보나치 수
# a에는 n - 1번째 수, b에는 n번째 수를 저장
a, b = 0, 1

# 숫자 n을 입력
n = int(input())

if n < 2: print(n)      # n이 2보다 작을 때는 그대로 출력
else:
    for _ in range(n - 1):      # n이 2 이상일 경우에는 반복문으로 n번째 피보나치 수를 구함
        a, b = b, a + b
    
    print(b)

 

---

풀이

번째 피보나치 수는 0, 1번째 피보나치 수는 1이므로 0과 1일 때는 n을 그대로 출력하면 된다.

n이 2 이상일 때에는 반복문을 n - 1 회 반복함으로써 결과를 얻을 수 있으며 이때 n번째 피보나치 수를 구하기 위해 n - 1번째와 n - 2번째 수는 반드시 기억하고 있어야 한다.

---

심화

재귀 함수

재귀 함수는 함수 안에서 자신의 함수를 또 호출하는 함수를 말한다.

n번째 피보나치 수를 구하는 함수를 F(n)이라고 한다면 F(n)을 구하기 위해서는 F(n - 2)와 F(n - 1)이 필요하다.

그리고 이 함수들은 모두 동일하게 피보나치 수를 구하는 함수이기 때문에 재귀 함수를 활용하여 풀 수 있다.

 

- C언어

#include <stdio.h>

// 피보나치 수를 구하는 함수
int fibo(int n){
    if(n == 0 || n == 1){       // n이 0 또는 1일때는 n을 그대로 반환
        return n;
    }
    else{
        return fibo(n - 2) + fibo(n - 1);       // n이 2 이상일 때는 재귀 함수 호출
    }
}

int main()
{
    int n;

    // 숫자 n을 입력
    scanf("%d", &n);

    // n번째 피보나치 수를 출력
    printf("%d", fibo(n));
    return 0;
}

 

- Python

# n번째 피보나치 수를 구하는 함수
def fibo(n):
    if n < 2:       # n이 2보다 작을 때는 n을 반환
        return n
    
    else:           # n이 2이상이면 재귀함수 호출
        return fibo(n - 2) + fibo(n - 1)


n = int(input())
print(fibo(n))

 

※ fibo 함수 내의 n과 main에서의 n은 서로 다른 변수임을 꼭 기억하자.

 

 

재귀 함수의 한계

사실 피보나치 수를 구할 때 이렇게 재귀 함수로 풀이하는 것은 굉장히 비효율적이다.

 

 

위 그림을 보면 재귀 함수를 통해 10번째 피보나치 수를 구할 때 7번째 피보나치 수를 3번, 6번째 피보나치 수를 4번 구해야 하는 것을 볼 수 있다. 물론 재귀의 깊이가 더 깊어지면 0번째 피보나치 수와 1번째 피보나치 수는 훨씬 더 많은 횟수로 호출될 것이다.

이 수들을 여러 번 호출할 필요 없이 한 번에 구할 수 있기 때문에 피보나치 수를 재귀 함수로 불필요한 연산을 할 필요가 없는 것이다.

 

메모이제이션, DP (Dynamic Programming)

피보나치 수를 구할 때 재귀 함수의 문제점을 해소해줄 수 있는 방법 중 대표적인 방법이다.

 

메모이제이션이란 반복적인 수행을 할 때 이전에 수행했던 결과를 동일한 메모리에 저장함으로써 반복 횟수를 최대한 줄이는 방식을 말한다. 즉 이전에 계산했던 결과를 어떤 변수에 기억해놓는다는 것이다. 이를 통해 중복 연산을 줄일 수 있고 프로그램 수행 속도를 빠르게 할 수 있으며 메모리 접근 또한 줄일 수 있다.

 

동적 계획법 (DP, Dynamic Programming)은 주로 메모이제이션을 이용한 알고리즘 기법이며 어떤 문제가 주어졌을 때 해당 문제를 잘게 나누어서 처리한다는 것이 특징이다. 즉 이번 피보나치 문제처럼 이전에 처리했던 결과를 기억해야 할 때 이것을 동적 계획법이라 부르며 물론 메모이제이션 이외에도 다양한 방식으로 동적 계획법을 구현할 수 있다.

 

여기까지 눈치 채신 분들이 계실지 모르겠지만 정답 코드에서의 풀이가 이 방식을 이용한 것이다.