Fibonacci Numbers - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:20:45Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:20 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[Dynamic Programming]]		상위 문서: [[Dynamic Programming]]

2025년 11월 15일 (토) 03:32에 Pinkgo님의 편집

2025-11-15T03:32:41Z

← 이전 판		2025년 11월 15일 (토) 03:32 판
6번째 줄:		6번째 줄:
	피보나치 수열(Fibonacci Numbers)은 [[Dynamic Programming\|동적 프로그래밍(Dynamic Programming)]]의 대표적인 구현 예시 중 하나이다. 해당 문서에서는 피보나치 수열을 통한 동적 프로그래밍의 구현에 대해 설명한다.		피보나치 수열(Fibonacci Numbers)은 [[Dynamic Programming\|동적 프로그래밍(Dynamic Programming)]]의 대표적인 구현 예시 중 하나이다. 해당 문서에서는 피보나치 수열을 통한 동적 프로그래밍의 구현에 대해 설명한다.

	===Intuitive Version===		==Intuitive Version==
	피보나치 수열의 점화식 정의는 아래와 같다:		피보나치 수열의 점화식 정의는 아래와 같다:
	<math>F_n=F_{n-1}+F_{n-2}, F_0=0, F_1=1</math>		<math>F_n=F_{n-1}+F_{n-2}, F_0=0, F_1=1</math>
19번째 줄:		19번째 줄:
	이는 직관적으로 구현된 동적 프로그래밍이지만, 동일한 값을 반복해서 계산하는 비효율이 있다. Figure 1에서 보이는 바와 같이 fib(6)를 계산하려면 fib(5)와 fib(4)이 필요한데, fib(5) 안에서도 다시 fib(4)을 계산한다. 피보나치 수의 성장 비율은 황금비(<math>\phi</math>)로 수렴하며, 이에 따라 입력이 n일 때 재귀 호출은 <math>n^{1.6}</math>번 정도 발생한다. 즉, 단순 재귀는 계산이 폭발적으로 늘어나 너무 느리다는 결론을 얻을 수 있다.		이는 직관적으로 구현된 동적 프로그래밍이지만, 동일한 값을 반복해서 계산하는 비효율이 있다. Figure 1에서 보이는 바와 같이 fib(6)를 계산하려면 fib(5)와 fib(4)이 필요한데, fib(5) 안에서도 다시 fib(4)을 계산한다. 피보나치 수의 성장 비율은 황금비(<math>\phi</math>)로 수렴하며, 이에 따라 입력이 n일 때 재귀 호출은 <math>n^{1.6}</math>번 정도 발생한다. 즉, 단순 재귀는 계산이 폭발적으로 늘어나 너무 느리다는 결론을 얻을 수 있다.

	===Memoization(Top-Down)===		==Memoization(Top-Down)==
	Memoization은 계산한 결과를 저장(cache) 해서 다시 계산하지 않게 만드는 기법이다. 이는 아래와 같이 구현된다:		Memoization은 계산한 결과를 저장(cache) 해서 다시 계산하지 않게 만드는 기법이다. 이는 아래와 같이 구현된다:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
47번째 줄:		47번째 줄:
	이는 O(n)의 시간 복잡도를 가지므로, 효율적으로 구현되었다고 할 수 있다.		이는 O(n)의 시간 복잡도를 가지므로, 효율적으로 구현되었다고 할 수 있다.

	===Down-Top Dynamic Programming===		==Down-Top Dynamic Programming==
	Down-Top 동적 프로그래밍은 가장 작은 하위 문제부터 차근차근 해결하면서, 그 결과를 테이블(table)에 저장하고 큰 문제의 답을 점진적으로 만들어가는 방식이다. 이 방식은 메모리를 더 사용하는 대신, 반복문을 사용하여 속도를 더욱 획기적으로 개선할 수 있다는 장점이 있다. 이는 아래와 같이 구현된다:		Down-Top 동적 프로그래밍은 가장 작은 하위 문제부터 차근차근 해결하면서, 그 결과를 테이블(table)에 저장하고 큰 문제의 답을 점진적으로 만들어가는 방식이다. 이 방식은 메모리를 더 사용하는 대신, 반복문을 사용하여 속도를 더욱 획기적으로 개선할 수 있다는 장점이 있다. 이는 아래와 같이 구현된다:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">

2025년 11월 15일 (토) 03:27에 Pinkgo님의 편집

2025-11-15T03:27:06Z

← 이전 판		2025년 11월 15일 (토) 03:27 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
	상위 문서: [[~~알고리즘 설계와 분석#문제\|알고리즘 설계와 분석~~]]		상위 문서: [[Dynamic Programming]]

	==개요==		==개요==

2025년 11월 15일 (토) 03:26에 Pinkgo님의 편집

2025-11-15T03:26:16Z

← 이전 판		2025년 11월 15일 (토) 03:26 판
4번째 줄:		4번째 줄:

	==개요==		==개요==
	~~해당 문단에서는~~ 동적 프로그래밍 ~~활용의~~ 대표적인 ~~예시들 중의 하나인~~ 피보나치 수열을 ~~통해서~~ 동적 프로그래밍의 ~~구현 방법에~~ 대해 ~~알아보는 것을 목표로 한다~~.		피보나치 수열(Fibonacci Numbers)은 [[Dynamic Programming\|동적 프로그래밍(Dynamic Programming)]]의 대표적인 구현 예시 중 하나이다. 해당 문서에서는 피보나치 수열을 통한 동적 프로그래밍의 구현에 대해 설명한다.

	===Intuitive Version===		===Intuitive Version===

Pinkgo: 새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요== 해당 문단에서는 동적 프로그래밍 활용의 대표적인 예시들 중의 하나인 피보나치 수열을 통해서 동적 프로그래밍의 구현 방법에 대해 알아보는 것을 목표로 한다. ===Intuitive Version=== 피보나치 수열의 점화식 정의는 아래와 같다: $F_n=F...$

2025-11-15T03:23:27Z

새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요== 해당 문단에서는 동적 프로그래밍 활용의 대표적인 예시들 중의 하나인 피보나치 수열을 통해서 동적 프로그래밍의 구현 방법에 대해 알아보는 것을 목표로 한다. ===Intuitive Version=== 피보나치 수열의 점화식 정의는 아래와 같다: <math>F_n=F...

새 문서

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[알고리즘 설계와 분석#문제|알고리즘 설계와 분석]]

==개요==
해당 문단에서는 동적 프로그래밍 활용의 대표적인 예시들 중의 하나인 피보나치 수열을 통해서 동적 프로그래밍의 구현 방법에 대해 알아보는 것을 목표로 한다.

===Intuitive Version===
피보나치 수열의 점화식 정의는 아래와 같다:
<math>F_n=F_{n-1}+F_{n-2}, F_0=0, F_1=1</math>
이를 구현하기 위한 기본적인 방법은 아래와 같다:
<syntaxhighlight lang="c">
long fib_r(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib_r(n-1) + fib_r(n-2);
}
</syntaxhighlight>
이는 직관적으로 구현된 동적 프로그래밍이지만, 동일한 값을 반복해서 계산하는 비효율이 있다. Figure 1에서 보이는 바와 같이 fib(6)를 계산하려면 fib(5)와 fib(4)이 필요한데, fib(5) 안에서도 다시 fib(4)을 계산한다. 피보나치 수의 성장 비율은 황금비(<math>\phi</math>)로 수렴하며, 이에 따라 입력이 n일 때 재귀 호출은 <math>n^{1.6}</math>번 정도 발생한다. 즉, 단순 재귀는 계산이 폭발적으로 늘어나 너무 느리다는 결론을 얻을 수 있다.

===Memoization(Top-Down)===
Memoization은 계산한 결과를 저장(cache) 해서 다시 계산하지 않게 만드는 기법이다. 이는 아래와 같이 구현된다:
<syntaxhighlight lang="c">
#define MAXN 92
#define UNKNOWN -1
long f[MAXN+1];

long fib_c(int n) {
if (f[n] == UNKNOWN) {
f[n] = fib_c(n-1) + fib_c(n-2);
}
return f[n];
}
</syntaxhighlight>
위 코드에서 f[n] 배열은 캐시 기능을 하며, UNKNOWN 값(-1)은 아직 계산되지 않은 상태를 의미한다. 이를 통해서 한 번 계산한 피보나치 수는 저장하여 중복 계산을 방지한다. 재귀 구조에 저장소를 추가한 형태를 top-down 방식의 동적 프로그래밍이라고 한다. 아래는 위의 코드를 실행하기 위해서 f 배열을 초기화한 뒤 fib_c()를 호출하는 드라이버 함수이다:
<syntaxhighlight lang="c">
long fib_c_driver(int n) {
int i;
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++) {
f[i] = UNKNOWN;
}
return fib_c(n);
}
</syntaxhighlight>
이는 O(n)의 시간 복잡도를 가지므로, 효율적으로 구현되었다고 할 수 있다.

===Down-Top Dynamic Programming===
Down-Top 동적 프로그래밍은 가장 작은 하위 문제부터 차근차근 해결하면서, 그 결과를 테이블(table)에 저장하고 큰 문제의 답을 점진적으로 만들어가는 방식이다. 이 방식은 메모리를 더 사용하는 대신, 반복문을 사용하여 속도를 더욱 획기적으로 개선할 수 있다는 장점이 있다. 이는 아래와 같이 구현된다:
<syntaxhighlight lang="c">
long fib_dp(int n) {
int i;
long f[MAXN+1];
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++) {
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
</syntaxhighlight>
이는 시간 복잡도와 공간 복잡도가 모두 O(n)으로, 매우 효율적으로 구현되었다.

==각주==