[알고리즘] 백준. 2748, 1003 피보나치(동적 계획법)

Dynamic programming 파트 중 피보나치 수열에 관한 두 문제이다. 

 

피보나치 수열에 대해 간단히 설명하자면, n번째 피보나치 수는 n-1번째 피보나치 수와 n-2번째 피보나치 수의 합이다. 

여기서 n은 2이상의 자연수이고, 초깃값이 n=0, n=1일 때 각각 0, 1로 주어진다. 

 

다음은 n과 이에 대응되는 피보나치 수이다.

n	0	1	2	3	4	5	...
피보나치 수	0	1	1	2	3	5

 

파이썬으로 구현했는데, 재귀함수 형태로 구현했을 때, pypy3으로 채점을 했는데도 속도가 느렸다. 

따라서 다른 방식을 써보기로 했다. 

 

먼저 2748번이다. 

입력을 받는데, 90이하의 자연수를 입력값으로 받고 해당 수에 해당하는 피보나치 수를 출력해주면 된다. 

필자는 재귀 함수 대신 파이썬의 리스트를 이용해 풀었다. 

 

초깃값으로 0, 1을 주었고, 다음 값을 구하여 리스트에 추가하면서 n번째 값에 도달할 때까지 반복한 후 리스트의 최종 추가된 값을 출력해주었다. 

index	0	1
fibo_ls	0	1

fibo_ls = [0, 1]

fibo_ls[0] + fibo_ls[1]을 fibo_ls에 추가.

index	0	1	2
fibo_ls	0	1	1

 

n = int(input())

def fibo2(n):
    fibo_ls = [0,1]
    if n == 1 or n == 0:
        return fibo_ls[n]
    else:
        while len(fibo_ls)-1 != n:
            fibo_ls.append(fibo_ls[-1] + fibo_ls[-2])
        return fibo_ls[-1]
print(fibo(n))

 

 

그 다음은 1003번 문제이다. 

이 문제는 동적 계획법의 특징을 잘 보여주고 있는 것 같다. 동적 계획법은 여러 문제를 간단한 문제로 나누어 풀고 이를 저장하여 복잡한 문제를 푸는 데 이용하는 기법이다. 풀어 낸 내용을 저장 한다는 점에서 분할정복 기법과는 차이를 보인다. 

 

1003번 문제는 피보나치 수를 구하는 함수를 먼저 제공한다. 여기선 fibo()라 하겠다. 

간단한 문제로 나누어 푸는 과정에서 가장 간단한 형태는 fibo(0) 또는 fibo(1)이다. 특정 n에 대한 fibo(n)에 대해 fibo(0)과 fibo(1)이 몇번 사용되었는지를 출력한다.

 

풀이는 우선 0과 1의 개수를 저장할 리스트를 잡고, 이 리스트에 값이 없다면, 값을 업데이트 해주고, 있다면 그 값을 불러와서 쓴다. 피보나치 수열처럼 n번째 값을 구할 때 n-1과 n-2번째 값을 이용해 구한다. 

 

n_zero_one: n번쩨 피보나치 수에서 fibo(0)과 fibo(1)이 call된 횟수, 

n	0	1	2	3	4	5	...
n_zero_one	(1, 0)	(0, 1)	(1, 1)	(1,2)	(2,3)	(3,5)	...

cnt = int(input())
for i in range(cnt):
    n = int(input())

    n_zero_one = [(-1,-1)]*(n+1)


    def fibo(n):
        global n_zero_one
        if n == 0:
            n_zero_one[n] = (1, 0)
            return n_zero_one[n]
        if n==1:
            n_zero_one[n] = (0, 1)
            return n_zero_one[n]

        if sum(n_zero_one[n]) >= 0:
            return n_zero_one[n]
        else:
            n_zero_one[n] = (fibo(n-1)[0]+fibo(n-2)[0], fibo(n-1)[1]+fibo(n-2)[1])
            return n_zero_one[n]

    res = fibo3(n)
    print(res[0], res[1])