[BaekJoon] 1003 피보나치 함수 - Python 풀이

문제 

 

다음 소스는 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이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

난이도

Silver 3

입력 조건

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

 

출력 조건

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

입력 예시 

3
0
1
3

 

출력 예시 

1 0
0 1
1 2

처음 짠 코드

import sys

t = int(input())

for _ in range(t):
    n = int(sys.stdin.readline())
    d = [[0,0]] * (n+1) # index까지의 0과 1의 개수를 담고 있는 DP 테이블
    d[0] = [1,0]
    if n >=1:
        d[1] = [0,1]
    if n >=2:
        for i in range(2,n+1):
            d[i][0] = d[i-1][0] + d[i-2][0]
            d[i][1] = d[i-1][1] + d[i-2][1]
    print(d[n][0],d[n][1])

수정 한 코드

import sys

t = int(input())

for _ in range(t):
    n = int(sys.stdin.readline())
    d = [[0 for j in range(2)] for _ in range(n+1)]  # index까지의 0과 1의 개수를 담고 있는 DP 테이블
    d[0] = [1,0]
    if n >=1:
        d[1] = [0,1]
    if n >=2:
        for i in range(2,n+1):
            d[i][0] = d[i-1][0] + d[i-2][0]
            d[i][1] = d[i-1][1] + d[i-2][1]
    print(d[n][0],d[n][1])

 

느낀 점

이 문제에서 처음 짠 코드는 틀렸다. 분명히 점화식을 알맞게 세운 것 같았는데 어디서 틀린 건지 도저히 모르겠어서 결국 질문을 남겨보았다.

처음 짠 코드에서의 문제점은 다음과 같다.

d 리스트를 보면, d[0], d[1]을 제외한 나머지 리스트의 값들이 전부 한 번에 갱신되고 있다.

이는 [[0,0]]을 n+1번 복제해서 생기는 문제로, 치환된 d[0]와 d[1]을 제외한 나머지의 원소가 똑같은 객체를 참조하고 있기 때문에 일어나는 현상이다.

6까지 다음 함수를 돌렸을 때, id와 d리스트를 뽑아보면 다음과 같다.

1
6
i=2
d[2]의 id : 1397019750976
d=[[1, 0], [0, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1]]
i=3
d[3]의 id : 1397019750976
d=[[1, 0], [0, 1], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2]]
i=4
d[4]의 id : 1397019750976
d=[[1, 0], [0, 1], [2, 4], [2, 4], [2, 4], [2, 4], [2, 4]]
i=5
d[5]의 id : 1397019750976
d=[[1, 0], [0, 1], [4, 8], [4, 8], [4, 8], [4, 8], [4, 8]]
i=6
d[6]의 id : 1397019750976
d=[[1, 0], [0, 1], [8, 16], [8, 16], [8, 16], [8, 16], [8, 16]]
8 16

따라서, d를 list comprehension을 이용해 [[0 for j in range(2)] for i in range(n+1)]과 같은 식으로 하거나, d[i]를 즉석에서 추가해 가는 방법이 있다.

list comprehension 방식으로 d를 선언하면 해결이 되는 이유는 다음과 같다.

일단 숫자의 경우 기본적으로 불변이기 때문에, 계산을 진행하게 되면 새로운 객체로 참조를 전환하게 된다.

정수형으로 새롭게 만들게 되면, 계산 자체를 하면서 새로운 객체로 참조를 전환하기 때문에, id가 각각 다 다르게 변하게 된다.

또한, [[0, 0] for i in range(n + 1)] 같은 식으로 하더라도, list 자체를 새롭게 만들게 되므로, 각각의 원소가 모두 다른 id를 가지게 된다.

i=2
d[2]의 id : 1565258128896
d=[[1, 0], [0, 1], [1, 1], [0, 0], [0, 0], [0, 0], [0, 0]]
i=3
d[3]의 id : 1565258129152
d=[[1, 0], [0, 1], [1, 1], [1, 2], [0, 0], [0, 0], [0, 0]]
i=4
d[4]의 id : 1565258129216
d=[[1, 0], [0, 1], [1, 1], [1, 2], [2, 3], [0, 0], [0, 0]]
i=5
d[5]의 id : 1565258129344
d=[[1, 0], [0, 1], [1, 1], [1, 2], [2, 3], [3, 5], [0, 0]]
i=6
d[6]의 id : 1565258121664
d=[[1, 0], [0, 1], [1, 1], [1, 2], [2, 3], [3, 5], [5, 8]]
5 8

결국 객체 참조에 대한 지식이 없기 때문에 발생한 문제였다. 

앞으로는 코드를 짤 때 이러한 점들을 더욱 생각하면서 짜도록 해야겠다.