Dynamic Programming
fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하는 문제
예제 입력
3
0
1
3
예제 출력
1 0
0 1
1 2
문제풀이
재귀함수로 풀려고 했는데 시간초과가 나서 다른 분들은 어떻게 코드를 작성했는지 참고하였다. 읽어 본 사이트
이 문제는 피보나치의 값이 아닌 fibonaaci(0)과 fibonacci(1)의 호출 횟수를 구하는 것이다.
원래의 fibonacci(n)을 구하기 위해서는 fibonacci(n-1)와 fibonacci(n-2)을 더해야 조건이 성립된다.
이 때 fibonacci(n)
을 호출한다면, 실행되는 fibonacci(0)
과 fibonacci(1)
은
'fibonacci(n-1)의 0과 1 호출 횟수' + 'fibonacci(n-2)의 0과 1 호출 횟수'
와 동일하다는 뜻이다!
zero = [1, 0, 1]
one = [0, 1, 1]
이 개념을 적용해서 문제를 풀어본다면, 숫자마다 0과 1의 호출 횟수를 저장할 리스트 zero, one을 생성해준다.
fibonacci(2) = fibonacci(1) + fibonacci(0)이기 때문
이렇게 0부터 2까지는 미리 배열을 만들어서 이보다 큰 숫자에서의 0과 1의 호출 횟수를 추가로 저장하면 된다.
배열을 만들어서 값을 저장하는 이유는 '다이나믹 프로그래밍'을 통해 이미 구한 숫자를 또다시 구하는 일이 없도록 하여 시간을 단축시키기 위함이다.
def fibonacci(num):
length = len(zero)
if num >= length:
for i in range(length, num+1):
zero.append(zero[i-1] + zero[i-2])
one.append(one[i-1] + one[i-2])
print('{} {}'.format(zero[num], one[num]))
코드를 보면 배열의 길이를 구해서, 배열의 길이보다 입력받은 숫자의 값이 크거나 같으면 반복문을 시작한다.
(그렇지 않으면 이미 배열에 저장되어 있는 값을 출력하면 되기 때문이다.)
위에서 알아본 피보나치를 구하는
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
개념을 적용하여,
'피보나치 n에서 0, 1의 호출횟수 = (피보나치 n - 1에서 0, 1 호출횟수) + (피보나치 n - 2에서 0, 1 호출횟수)'
을 계산해서 새로운 값을 배열에 추가한다.
이처럼 배열에 추가하여 동일한 작업을 없애면 시간을 단축시킬 수 있다.
T = int(input())
for _ in range(T):
fibonacci(int(input()))
그러고 나서 몇 번 반복할지를 변수 T에 입력받고 T번 만큼 피보나치 함수를 실행시킨다.
그럼 문제를 성공적으로 풀었음을 확인할 수 있다!
전체 코드
zero = [1, 0, 1]
one = [0, 1, 1]
def fibonacci(num):
length = len(zero)
if num >= length:
for i in range(length, num+1):
zero.append(zero[i-1] + zero[i-2])
one.append(one[i-1] + one[i-2])
print('{} {}'.format(zero[num], one[num]))
T = int(input())
for _ in range(T):
fibonacci(int(input()))