문제
한 쌍의 토끼들은 한 달이 될 때에 한 쌍의 토끼를 낳고 두달이 될 때에 또 다른 한 쌍의 토끼를 낳는다.
내가 방금 한 쌍의 새로 태어난 토기들을 샀다면 지금부터 n번째 달에 몇 쌍의 토끼들이 태어날까?
주 : n이 주어지면 토끼 쌍들의 수를 구해야 한다. n은 매개 변수이다.
f(n)을 지금부터 i 번째달에 태어난 토끼 쌍들의 수라고 하자.
n 0 1 2 3 4 5 6 ...
f(n) 1 1 2 3 5 8 13 ... > f(n) = f(n-1) + f(n-2) / f(0) = f(1) = 1 / n >= 2
(수학적 풀이) 점화식을 풀어서 "수학적"으로 해결
(알고리즘) f(n)을 구하는 알고리즘
설계 : 매개 변수 : n // 출력값 : f(n)
ⓐ n이 0이면, f(n) = 1
ⓑ n이 1이면, f(n) = 1
ⓒ n이 2보다 크거나 같으면, f(n) = f(n-1) + f(n-2)
>> 일반적으로 알려진 재귀적 방법을 이용
int Fib(int n){
//n은 0을 포함한 양의 자연수이다.
if ( n == 0 ) return 1;
else if ( n == 1 ) return 1;
else return Fib(n-1) + Fib(n-2);
}
복잡도 분석 : 복잡도에 요인을 주는 것 ( 더하기를 하는 횟수 / 함수 호출 하는 횟수)
ⓐ FC(n) : f(n)을 구하기 위해 필요한 함수 호출 횟수
ⓑ ADD(n) : f(n)을 구하기 위해 필요한 덧셈의 횟수
함수 호출 트리(tree)를 이용하여 알아보도록 하자.
다음 트리는 f(5)를 호출 했을 때를 나타내며
각각의 트리의 값은 매개변수(n) 값을 나타낸다.
즉, f(5)를 호출하기 위해서는 f(4)와 f(3)을 호출한다는 것이다.
이것을 일반화 시켜민 n>=2 일 경우에는
n 노드에 대해서
왼쪽 자식은 n-1에 대한 트리를
오른쪽 자식은 n-2에 대한 트리를 확장해 간다.
여기서 복잡도에 영향을 주는 함수 호출 횟수와
더하기를 하는 횟수는 다음과 같다.
함수 호출이 이뤄지는 경우는 각 노드의 개수와 같다.
FC(n) = FC(n-1) + FC(n-2) + 1 n >= 2
FC(0) = FC(1) = 1
더하기를 하는 횟수는 자식 노드를 가지고 있는 노드의 수와 같다. (자식 노드를 합쳐서 자신이 탄생하기 때문)
ADD(n) = ADD(n-1) + ADD(n-2) + 1
ADD(0) = ADD(1) = 1
FC(n) = 2f(n) - 1 , ADD(n) = f(n) - 1
f(n)의 복잡도를 알기 위해서 점화식(f(n) = f(n-1) + f(n-2)를 풀면 다음과 같은 해를 얻는다.
> 재귀적 방법으로 위의 문제를 해결할 시 프로그램이 깔끔해 보일지라도, 실행 속도가 매우 느려진다
> 시간적으로 매우 비효율 적이다.
> 이 문제를 해결할 수 있는 가능성을 가진 다른 알고리즘을 생각해본다.
(알고리즘) f(n)을 구하는 2번째 알고리즘
이번엔 동적프로그래밍(Dynamic programming) 기법을 사용한다. 동적 프로그래밍이란 알고리즘이 부분 문제 반복과 최적 기본 구조라는 특징을 가지고 있을 때 이 알고리즘의 실행시간을 줄이는 방법이다.(wiki백과)
주 아이디어 : 문제를 해결하기 위해 두 개의 더 작은 문제를 해결 하면 되는 것을 알 수 있다. 따라서 본 문제 보다
더 간단한 두개의 작은 문제를 해결하여 원하는 문제를 해결한다.
한 문제가 부분 문제 반복를 가지는 특징을 가지고 있다면, 더 작은 문제들에 대한 해(답)들의 표를 만든다. 이 표는 가장 작은 문제부터 시작해서 가장 큰 문제로 나아간다.
>>프로그램 개발
int Fib(int n){
int f[0, 1, 2, ... , n]; // 구하고자 하는 n 값을 넣는다.
f[0] = 1;
f[1] = 1;
for( int i = 2 ; i <= n ; i++ ){
한 쌍의 토끼들은 한 달이 될 때에 한 쌍의 토끼를 낳고 두달이 될 때에 또 다른 한 쌍의 토끼를 낳는다.
내가 방금 한 쌍의 새로 태어난 토기들을 샀다면 지금부터 n번째 달에 몇 쌍의 토끼들이 태어날까?
주 : n이 주어지면 토끼 쌍들의 수를 구해야 한다. n은 매개 변수이다.
f(n)을 지금부터 i 번째달에 태어난 토끼 쌍들의 수라고 하자.
n 0 1 2 3 4 5 6 ...
f(n) 1 1 2 3 5 8 13 ... > f(n) = f(n-1) + f(n-2) / f(0) = f(1) = 1 / n >= 2
(수학적 풀이) 점화식을 풀어서 "수학적"으로 해결
(알고리즘) f(n)을 구하는 알고리즘
설계 : 매개 변수 : n // 출력값 : f(n)
ⓐ n이 0이면, f(n) = 1
ⓑ n이 1이면, f(n) = 1
ⓒ n이 2보다 크거나 같으면, f(n) = f(n-1) + f(n-2)
>> 일반적으로 알려진 재귀적 방법을 이용
int Fib(int n){
//n은 0을 포함한 양의 자연수이다.
if ( n == 0 ) return 1;
else if ( n == 1 ) return 1;
else return Fib(n-1) + Fib(n-2);
}
복잡도 분석 : 복잡도에 요인을 주는 것 ( 더하기를 하는 횟수 / 함수 호출 하는 횟수)
ⓐ FC(n) : f(n)을 구하기 위해 필요한 함수 호출 횟수
ⓑ ADD(n) : f(n)을 구하기 위해 필요한 덧셈의 횟수
함수 호출 트리(tree)를 이용하여 알아보도록 하자.
각각의 트리의 값은 매개변수(n) 값을 나타낸다.
즉, f(5)를 호출하기 위해서는 f(4)와 f(3)을 호출한다는 것이다.
이것을 일반화 시켜민 n>=2 일 경우에는
n 노드에 대해서
왼쪽 자식은 n-1에 대한 트리를
오른쪽 자식은 n-2에 대한 트리를 확장해 간다.
여기서 복잡도에 영향을 주는 함수 호출 횟수와
더하기를 하는 횟수는 다음과 같다.
함수 호출이 이뤄지는 경우는 각 노드의 개수와 같다.
FC(n) = FC(n-1) + FC(n-2) + 1 n >= 2
FC(0) = FC(1) = 1
더하기를 하는 횟수는 자식 노드를 가지고 있는 노드의 수와 같다. (자식 노드를 합쳐서 자신이 탄생하기 때문)
ADD(n) = ADD(n-1) + ADD(n-2) + 1
ADD(0) = ADD(1) = 1
FC(n) = 2f(n) - 1 , ADD(n) = f(n) - 1
f(n)의 복잡도를 알기 위해서 점화식(f(n) = f(n-1) + f(n-2)를 풀면 다음과 같은 해를 얻는다.
> 재귀적 방법으로 위의 문제를 해결할 시 프로그램이 깔끔해 보일지라도, 실행 속도가 매우 느려진다
> 시간적으로 매우 비효율 적이다.
> 이 문제를 해결할 수 있는 가능성을 가진 다른 알고리즘을 생각해본다.
(알고리즘) f(n)을 구하는 2번째 알고리즘
이번엔 동적프로그래밍(Dynamic programming) 기법을 사용한다. 동적 프로그래밍이란 알고리즘이 부분 문제 반복과 최적 기본 구조라는 특징을 가지고 있을 때 이 알고리즘의 실행시간을 줄이는 방법이다.(wiki백과)
주 아이디어 : 문제를 해결하기 위해 두 개의 더 작은 문제를 해결 하면 되는 것을 알 수 있다. 따라서 본 문제 보다
더 간단한 두개의 작은 문제를 해결하여 원하는 문제를 해결한다.
한 문제가 부분 문제 반복를 가지는 특징을 가지고 있다면, 더 작은 문제들에 대한 해(답)들의 표를 만든다. 이 표는 가장 작은 문제부터 시작해서 가장 큰 문제로 나아간다.
>>프로그램 개발
int Fib(int n){
int f[0, 1, 2, ... , n]; // 구하고자 하는 n 값을 넣는다.
f[0] = 1;
f[1] = 1;
for( int i = 2 ; i <= n ; i++ ){
f[n] = f[n-1] + f[n-2]; // f[n] is answer
}
}
분석 : 이번 알고리즘에서 복잡도를 구성하는 것은 수행하는 더하기의 수이다.
ADD(n) = n - 1
> 이번 알고리즘은 시간의 효율이 높지만, 저장 메모리를 많이 사용한다.
> 이보다 더 나은 알고리즘을 탐색할 수 있지만, 이 과정에서 더 심화해서 다루지는 않겠다.