문제
오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드1 코드2 실행 횟수를 출력하자.
피보나치 수 재귀호출 의사 코드는 다음과 같다.
fib(n) {
if (n = 1 or n = 2)
then return 1; # 코드1
else return (fib(n - 1) + fib(n - 2));
}피보나치 수 동적 프로그래밍 의사 코드는 다음과 같다.
fibonacci(n) {
f[1] <- f[2] <- 1;
for i <- 3 to n
f[i] <- f[i - 1] + f[i - 2]; # 코드2
return f[n];
}입력
첫째 줄에 n(5 ≤ n ≤ 40)이 주어진다.
출력
코드1 코드2 실행 횟수를 한 줄에 출력한다.
예제 입력 1
5예제 출력 1
5 3예제 입력 2
30예제 출력 2
832040 28일단 전혀 감이 안잡히므로 풀이를 보면서 익혀보겠다
피보나치 수열??
- 첫 번째 항과 두 번째 항은 각각 1임. 즉, F(1)=1, F(2)=1
- 세 번째 항부터 바로 앞의 두 항의 합. 즉, F(n)=F(n-1)+F(n-2) for n>2
실제 계산 값은 1, 1, 2, 3, 5, 8,,,,,
재귀 호출 방식
피보나치 수의 정의를 그대로 코드로 구현한 것
# 사용자로부터 n 값을 입력받습니다.
n = int(input())
# 전역 변수로 count를 선언합니다.
count = 0
# 재귀 호출 방식의 피보나치 함수입니다.
def fib(n):
global count # 전역 변수 count를 사용하겠다는 선언입니다.
if n <= 2:
count += 1 # 코드1: 조건을 만족할 때마다 count를 증가시킵니다.
return 1
else:
count += 1 # 코드1: 재귀 호출될 때마다 count를 증가시킵니다.
return fib(n - 1) + fib(n - 2)
fib(n)여기서 왠만한건 다 이해되는데 global은 처음 접함
global count : 전역 변수 count를 함수 내부에서 사용하기 위해 선언
여기서 아주 중요한 내용을 이해해버렸다
다른 수정 코드를 보면
count_recursive = 0 # 재귀 호출 횟수를 세기 위한 전역 변수
def fib(n):
global count_recursive
if n <= 2:
count_recursive += 1 # 기본 사례에서 실행 횟수 증가
return 1
else:
count_recursive += 1 # 재귀 호출마다 실행 횟수 증가
return fib(n - 1) + fib(n - 2)
n = int(input("Enter the value of n: ")) # 사용자로부터 n 값을 입력받습니다.
fib_result = fib(n)
print(f"재귀 호출 방식의 피보나치 수: {fib_result}")
print(f"재귀 호출 방식의 코드1 실행 횟수: {count_recursive}")return 1 에 다다르는 모든 과정을 실행횟수로 쳐서 피보나치 수보다 더 많은 실행횟수를 얻었는데, 그게 아니라
return 1에 다다르는 그 횟수 자체만 더해주는게 실행횟수라고 생각을 해야한다.
그게 고로 피보나치 수가 되는 셈이기도 하다.
근데 재귀함수를 쓰면 시간이 너무 오래 걸리게 되어서 문제 자체는 오답이 된다.
이걸 타파하기 위해선 즉, 중복 계산을 피하기 위해선
동적 프로그래밍, 반복문, 메모이제이션
을 통해 풀 수 있다고 한다.
<반복문>
n = int(input())
def fib(n):
a, b = 1, 1 # f(1), f(2)
for _ in range(3, n+1): # 1, 2는 이미 정의했으므로 3부터 n까지
a, b = b, a+b
return b- a, b를 각 각 초기값 1로 설정
이것은 피보나치 수열 첫 번째와 두 번째 수 f(1)과 f(2)와 같음- for _ in range(3, n+1)
1,2는 정의했으므로 3부터 시작해서 n까지 반복시켜줄 예정- a, b = b, a+b
a는 이전의 b값, 즉 현재 b는 피보나치 수열의 (i-1)번째 수
즉 맨 처음에 a, b 는 1 1이고
그 다음엔 f(3)이 2이므로 a,b는 1 2
그 다음엔 f(4)가 3이므로 a,b는 2 3
i-1번째가 현재 b(오른쪽 b)라고 말한 이유는 a위치에 b가 있어서 !
정리하자면
b는 a+b 즉 이전 두 수의 합(그렇게 구성된게 피보나치 수)
즉 현재 b는(왼쪽의 b) 수열의 i번째 수- return b
반복이 끝나면 b는 n번째 피보나치 수가 됨보고 풀면 이해되지만 그냥 보면 참 많은 과정이 생략된 고급적이면서 가독성 좋은 코드라 생각된다... ㄷㄷ
그치만 n이 1이거나 2일때 처리를 해주지 않았기에 그 부분까지 더해준다면
def fib(n):
if n == 1 or n == 2:
return 1
a, b = 1, 1 # f(1) = 1, f(2) = 1
for _ in range(3, n+1):
a, b = b, a + b
return b이렇게 해주고 백준을 돌려보면?
다행히 맞았다(대신 메모리와 시간은 늘어났음)
코드2분석
동적 프로그래밍을 이용한 피보나치 수 계산 방법
이 방법은 문제를 효율적으로 해결하기 위해 주어진 문제를 작은 하위 문제로 나누어 해결한 후, 결과 저장하고 재사용
fibonacci(n) {
f[1] <- f[2] <- 1;
for i <- 3 to n
f[i] <- f[i - 1] + f[i - 2]; # 코드2
return f[n];
}
코드 뜯어보기 전에 이런 양식의 코드를 처음보는데
의사코드
프로그래밍 언어의 문법에 구애받지 않고, 알고리즘을 간단하고 명확하게 표현하는 데 사용.
즉, 적당히 열린 마인드로 봐야 해석할 수 있다.. 라고 말할 수 있다...
문제에 있던 코드를 뜯어보면
1. 초기화
f[1] <- f[2] <- 1;- 배열 f의 인덱스 1과 2에 각각 1을 할당
- 피보나치 수열에서 f[1]과 f[2]는 1로 정의되어 있기 때문
- 반복문
for i <- 3 to n
f[i] <- f[i-1] + f[i -2];- i를 3부터 n까지 증가시키면서 각 i에 대해 f[i]를 계산
- f[i]는 f[i-1]과 f[i-2]의 합으로 계산
- 현재 인덱스 i의 피보나치 수는 바로 이전 두 인덱스의 피보나치 수의 합
- 코드2가 실행 -> 반복문 내에서 피보나치 수를 계산하는 부분
- 반환
return f[n];- 반복문이 끝난 후, 배열 f의 인덱스 n에 저장된 값을 반환
- 피보나치 수열의 n번째 항
동적 프로그래밍의 장점
-
효율성
재귀 호출 방식에 비해 훨씬 빠름.
재귀 호출 방식은 중복 계산이 많아 비효율적이지만, 동적 프로그래밍 방식은 각 피보나치 수를 한 번만 계산하고 그 결과를 배열에 저장하므로 훨씬 더 효율적 -
시간 복잡도
O(n), 반복문을 통해 각 항을 한 번씩 계산하므로 시간 복잡도가 선형(재귀함수는 계속 반복함)
-
공간 복잡도
배열 f를 사용하기 때문에 O(n)의 공간 복잡도를 가짐
최적화 방법 사용하면 공간 복잡도 줄일 수 있음
def fibonacci(n):
return n-2참 이걸보고 어이가 없다고 생각이 들었다...
이게 정답이라니...ㅋㅋㅋㅋㅋㅋㅋ
일단 단순한 코드는 단순한 코드고 왜 저게 정답이 되는지 아직
이해는 안간다
도대체 뭘 구하려는 것일까??
드디어 알아냈다
이거야 말로 진짜로 맨 처음 내가 생각했던 것에서 조금 벗어난
반복을 몇번 돌려서 실제 피보나치 수가 나오냐를 구하는거였다.
예를 들어
4가 n의 값이면
4는
4
3 2 ----1번 반복
2 1 2 -----1번 반복
즉, 2 와 1에만 1이라는 값을 할당했으므로, 해당 숫자로만 이뤄지기 위해선 총2번 반복을 시켜야되기 때문에 2번 반복이 정답
여기서 그럼 1과 2에 대한 예외 사항만 건들여준다면?
최종 코드
n = int(input())
def fib(n):
if n == 1 or n == 2:
return 1
a, b = 1, 1 # f(1), f(2)
for _ in range(3, n+1): # 1, 2는 이미 정의했으므로 3부터 n까지
a, b = b, a+b
return b
def fibonacci(n):
if n == 1 or n == 2:
return 1
return n-2
print(fib(n), fibonacci(n))하따 어렵다 어려워 ㅠㅠ
