24416번: 알고리즘 수업 - 피보나치 수 1 (acmicpc.net)
24416번: 알고리즘 수업 - 피보나치 수 1
오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍
www.acmicpc.net
<내 풀이>
d=[0]*41
d[1]=1
d[2]=1
n=int(input())
for i in range(3,n+1):
d[i]=d[i-1]+d[i-2]
print(d[n], n-2)
0.
문제가 처음에 이해가 잘 되지 않았는데, 코드 1은
then return 1;
, 코드 2는
f[i] <- f[i - 1] + f[i - 2];
이것만을 말한다.
1.
첫번째는 피보나치 수를 재귀호출 함수로 표현한 의사코드이다.
return 1; 이 부분은
n번째 피보나치 수를 구할 때, 첫번째나 두번째 값을 몇번이나 다시 참조해서 계산을 하게 되냐는 거다.
먼저 n이 1 또는 2이면 함수가 바로 종료되기 때문에 한 번 코드 1은 한번 실행된다.
한편, n이 3이상이면 fib(n-1)과 fib(n-2)를 계산하기 위해서 두 개의 재귀 호출을 수행하는데, 그 재귀호출 안에서도 n이 1이나 2가 될 때까지 계속 재귀호출을 해서 내려가야 하므로~...
ex) 예를 들어, fib(5)를 계산하려면 다음과 같이 호출이 발생한다.
- fib(5) 안에서 fib(4)와 fib(3)을 호출
- fib(4) 안에서 fib(3)과 fib(2)를 호출
- fib(3) 안에서 fib(2)와 fib(1)을 호출
- fib(3) 안에서 fib(2)와 fib(1)을 호출
- n = 1: 코드 1 실행 횟수 = 1
- n = 2: 코드 1 실행 횟수 = 1
- n = 3: 코드 1 실행 횟수 = fib(2) + fib(1) = 1 + 1 = 2
- n = 4: 코드 1 실행 횟수 = fib(3) + fib(2) = 2 + 1 = 3
- n = 5: 코드 1 실행 횟수 = fib(4) + fib(3) = 3 + 2 = 5
- n = 6: 코드 1 실행 횟수 = fib(5) + fib(4) = 5 + 3 = 8
이와 같이 n의 값이 증가함에 따라 코드 1이 실행되는 횟수는 피보나치 수열의 값과 동일하게 증가한다.
2.
두번째 코드는 피보나치 수 동적 프로그래밍 의사코드이다.
f[i] <- f[i - 1] + f[i - 2]; 이 부분은.. 3번째부터 n번째까지 딱 한번씩 실행되므로 n-2번 실행된다.
다이나믹 프로그래밍= '하나의 문제는 한 번만 푼다'
"주어진 코드에서 fibonacci(n) 함수는 피보나치 수열을 계산하는 반복문을 사용하여 작성되었습니다. for 루프가 i 값을 3부터 n까지 증가시키면서 f[i] 값을 계산하고 저장합니다. 따라서 코드 2가 실행되는 횟수는 for 루프의 반복 횟수와 동일합니다."
<풀이 후>
-피보나치 수열을 만드는 더 쉬운 방법은 virus outbreak문제와 마찬가지로,
초기 배열 설정할 때 최소한 짧게 시작을 하고, 배열 안 원소의 값을 변경하는 게 아니라 추가하는 것이다.
처리 시간도 더 적게 소요된다.
예시)
d = [0, 1, 1]
for i in range(3, n+1):
d.append(d[-1] + d[-2])
