백준 1003번: 피보나치함수

이 문제는 N번째 피보나치 수를 구하는 c++로 이루어진 함수의 동작을 이해하여, 0과 1이 몇번 출력되는지 구하는 프로그램을 작성해야하는 문제이다.

위 C++함수는 재귀적으로 0과 1을 반환하며 피보나치 함수의 답을 구하기 때문에 0과 1이 나올때마다 카운트 해주면 된다고 생각했다.

처음에는

lst=[]
def fibonacci(n):
    i=0
    if n == 0: 
        i=0
        lst.append(i)
    elif n == 1: 
        i=1
        lst.append(i)
    else:
        i=fibonacci(n-1)+fibonacci(n-2)
        lst.append(i)
    return lst
def count(Lst):
    s1=0
    s2=0
    for x in range(len(Lst)):
        if Lst[x]==0:
            s1+=1
        elif Lst[x]==1:
            s2+=1
    print(s1,s2)
num=int(input())
lst1=[]
for x in range(num):
    N=int(input())
    lst1.append(N)
for y in range(num):
    lst2=fibonacci(lst1[y])
    count(lst2)
    lst2.clear()

피보나치 함수에서 0이 나올때마다 lst에 0을, 1이 나올때마다 1을 넣어준다음 카운트함수에서 lst를 반복문으로 돌려,

0이 나올때마다 s1+=1, 1이 나올때마다 s2+=1을 하여 각 횟수를 세주었다. 그런데 이렇게 하면 메모리 초과가 났다.

확실히 이런 문제는 다이나믹프로그램을 이용해야한다고 느꼈고, 어떻게 활용을 할지 더 생각했다.

t = int(input())
res_lst = []

for i in range(t):
    c0 = 0
    c1 = 0
    n = int(input())
    i = 0
    while True:
        if i == 0:
            c1 = 0
            c0 = 1
        elif i == 1:
            c0 = 0
            c1 = 1
        elif i == 2:
            c0 = 1
            c1 = 1
        else:
            a = c0 + c1
            c0 = c1
            c1 = a
        i = i + 1
        if i == n + 1:
            print(c0, c1)
            break

동적 프로그래밍은 중복 계산을 피하기 위해 이전 계산 결과를 저장하고 재사용하는 방식이다. 이 경우, 각 n에 대해 F(n)을 호출했을 때의 0과 1의 출력 횟수를 저장하고 이를 재사용한다.

우선 c0은 n이 0일 때 0을 출력하는 횟수를, c1은 n이 1일 때 1을 출력하는 횟수를 저장한다.

1. • i == 0일 때, c1은 0으로 설정되고, c0은 1이 된다. 이는 F(0)이 호출될 때 0이 한 번 출력되기 때문이다.
   • i == 1일 때, c0은 0으로 설정되고, c1은 1이 됩니다. 이는 F(1)이 호출될 때 1이 한 번 출력되기 때문이다.
   • i == 2일 때, 이전 단계에서 계산된 c0과 c1의 값을 이용해 c0은 1, c1은 1이 된다. F(2)는 F(1)과 F(0)의 결과를 합산하여 계산되므로, 각각 한 번씩 출력된다.i가 3 이상인 경우: 코드는 c0과 c1을 갱신하여, 각 n에 대해 F(n) 호출 시 0과 1이 출력되는 횟수를 계산합니다.
   • a = c0 + c1: 이전 두 단계의 출력 횟수를 합산하여 새로운 출력 횟수를 계산한다.
   • c0 = c1: c0을 이전 단계의 c1 값으로 업데이트한다.
   • c1 = a: 새로 계산된 출력 횟수를 c1에 할당한다.
   • if i == n + 1: n+1이 되면, 현재 n에 대한 0과 1의 출력 횟수가 각각 c0과 c1에 저장되어 있다. 이 값을 출력한다.

이 방식은 매번 재귀적 호출을 사용하지 않고도, n이 매우 큰 경우에도 피보나치 수를 효과적으로 계산할 수 있게 해준다. 출력 결과는 n번째 피보나치 수를 계산할 때 각 숫자(0과 1)가 몇 번 출력되는지를 정확하게 반영한다.