섹션 7 Recursive, Tree, Graph - 4. 피보나치 수열

📌 문제 설명

피보나치 수열을 출력하는 프로그램을 작성한다.
피보나치 수열이란 앞의 두 수를 합하여 다음 수를 만드는 수열이다.
(예시: 1, 1, 2, 3, 5, 8, 13, ...)

---

📝 입력 & 출력

입력

• 첫 줄에 총 항수 N이 입력된다. (3 ≤ N ≤ 45)

출력

• 피보나치 수열의 첫 N개 항을 출력한다.

---

🔹 예제 입력 & 출력

예제 입력

 

10

 

예제 출력

 

1 1 2 3 5 8 13 21 34 55

---

💡 해결 방법

피보나치 수열을 구현하는 방법은 여러 가지가 있다:

• 재귀 호출 + 메모이제이션 사용
• 반복문(for문) 사용

재귀는 코드가 간결하지만 성능이 떨어질 수 있어서,
메모이제이션을 적용하거나 반복문을 사용하는 것이 더 안정적이다.

---

💻 코드 구현 (Java)

1️⃣ 재귀 + 메모이제이션 방식

package partRecursiveTreeGraph;

public class Problem4 {
	static int[] fibo;
	
	public int DFS(int n) {
		if (fibo[n] > 0) return fibo[n];
		if (n == 1) return fibo[n] = 1;
		else if (n == 2) return fibo[n] = 1;
		else return fibo[n] = DFS(n-2) + DFS(n-1);
	}
	
	public static void main(String[] args) {
		Problem4 T = new Problem4();
		int n = 45;
		fibo = new int[n+1];
		T.DFS(n);
		for (int i = 1; i <= n; i++) System.out.print(fibo[i] + " ");
	}
}

---

2️⃣ 반복문(for문) 방식

package partRecursiveTreeGraph;

public class Problem4Iterative {
	public static void main(String[] args) {
		int n = 45;
		int[] fibo = new int[n+1];
		fibo[1] = fibo[2] = 1;
		for (int i = 3; i <= n; i++) {
			fibo[i] = fibo[i-2] + fibo[i-1];
		}
		for (int i = 1; i <= n; i++) System.out.print(fibo[i] + " ");
	}
}

---

📖 코드 설명

재귀 + 메모이제이션 방식

• DFS(n-2) + DFS(n-1) 식으로 재귀 호출
• 이미 계산한 값은 배열 fibo[n]에 저장해서 다시 계산하지 않음
• 메모리를 추가로 사용하지만 성능이 크게 향상된다.

반복문(for문) 방식

• fibo[1] = 1, fibo[2] = 1로 초기화 후
• i=3부터 fibo[i] = fibo[i-2] + fibo[i-1]로 채워간다.
• 간결하고 효율적이며 성능이 좋다.

---

⏳ 시간 복잡도 분석

재귀 + 메모이제이션	O(N)	이미 계산한 값을 재사용해서 빠름
반복문(for문)	O(N)	루프 한 번만 돌기 때문에 가장 안정적

---

🧠 핵심 정리

• 단순 재귀만 쓰면 시간 복잡도 O(2^N)이라 느리다.
• 메모이제이션을 적용하면 O(N)으로 최적화된다.
• 반복문(for문) 방식은 구조가 간단하고, 실전 코딩 테스트에서는 가장 추천되는 방법이다.

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런