섹션 2. Array - 4. 피보나치 수열

📌 문제 설명

피보나치 수열이란 앞의 두 개의 수를 합하여 다음 숫자가 되는 수열입니다.

예를 들어, 7개의 항을 출력하면 1 1 2 3 5 8 13과 같이 출력됩니다.

---

📝 입력 & 출력

입력

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

출력

• 첫 줄에 피보나치 수열을 출력합니다.

---

🔸 예제 입력 & 출력

예제 입력 1

10

예제 출력 1

1 1 2 3 5 8 13 21 34 55

---

💡 해결 방법

1. 처음 두 항을 미리 리스트에 추가합니다 (1, 1).
2. 세 번째 항부터는 바로 앞 두 항의 합을 리스트에 추가합니다.
3. 리스트에 저장된 수열을 출력합니다.

---

💻 코드 구현 (Java)

package partArray;

import java.util.*;

public class Problem4 {
	public ArrayList<Integer> solution(int n){
		ArrayList<Integer> result = new ArrayList<Integer>();
		result.add(1);
		result.add(1);
		for(int i=2; i<n; i++) {
			result.add(result.get(i-2)+result.get(i-1));
		}
		return result;
	}

	public static void main(String[] args) {
		Problem4 T = new Problem4();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		for(int x: T.solution(n)) {
			System.out.print(x + " ");	
		}	
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 처음 두 항 초기화

result.add(1);
result.add(1);

• 첫 번째와 두 번째 항을 미리 리스트에 저장합니다.

2️⃣ 피보나치 수열 계산

for(int i=2; i<n; i++) {
	result.add(result.get(i-2)+result.get(i-1));
}

• 현재 항은 앞의 두 항을 더한 값입니다.

---

⏳ 시간 복잡도 분석

• 시간 복잡도: O(N)
• 배열을 한 번만 순회하여 간단한 계산을 수행합니다.

---

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

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