백준 1003번: 피보나치 함수 - 상세 풀이
🔍 1. 문제 소개
백준 1003번 "피보나치 함수" 문제는 재귀적으로 피보나치 수열을 구현하는 함수에서 0과 1이 각각 몇 번 출력되는지 계산하는 문제입니다. 피보나치 수열은 첫 두 항이 0과 1이며, 그 이후의 항은 바로 앞의 두 항의 합으로 정의됩니다 (F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for n >= 2). 입력으로는 테스트 케이스의 개수 T와 각 테스트 케이스마다 피보나치 수열의 인덱스 N(0 ≤ N ≤ 40)이 주어지며, 출력으로는 fibonacci(N)을 호출했을 때 0과 1이 각각 몇 번 출력되는지를 공백으로 구분하여 출력해야 합니다.
💡 2. 문제 해석
문제의 핵심은 재귀적인 피보나치 함수 호출 과정에서 0과 1이 출력되는 횟수를 직접 세는 것이 아니라, N이 주어졌을 때 fibonacci(N)을 계산하는 과정에서 0과 1이 몇 번 호출되는지를 효율적으로 계산하는 것입니다. 단순히 재귀 함수를 실행하여 0과 1의 출력 횟수를 세는 방법은 시간 복잡도가 매우 높아 N이 커질수록 비효율적입니다(지수 시간 복잡도). 따라서, 동적 계획법(Dynamic Programming)을 사용하여 효율적인 해결책을 찾아야 합니다. N의 최대값이 40으로 제한되어 있으므로, 메모이제이션을 통해 효율적인 계산이 가능합니다.
🧠 3. 접근 방법
문제를 해결하기 위한 최적의 방법은 동적 계획법(DP)입니다. zeroCount[i] 배열에 피보나치 수열의 i번째 항을 계산하는 과정에서 0이 출력되는 횟수를, oneCount[i] 배열에 1이 출력되는 횟수를 저장합니다. zeroCount[0] = 1, oneCount[1] = 1로 초기화하고, 점화식 zeroCount[i] = zeroCount[i-1] + zeroCount[i-2], oneCount[i] = oneCount[i-1] + oneCount[i-2]을 이용하여 N까지 반복적으로 계산합니다. 이를 통해 N번째 피보나치 수를 계산하는 과정에서 0과 1이 각각 몇 번 출력되는지 효율적으로 구할 수 있습니다.
⚙️ 4. 구현 과정
- `zeroCount`와 `oneCount` 배열을 크기 41의 정수형 배열로 선언하고 초기값을 설정합니다.
2. 반복문을 이용하여 i = 2부터 N까지 점화식을 적용하여 zeroCount와 oneCount 배열을 채웁니다. 3. 입력으로 주어진 테스트 케이스의 수만큼 반복하여 각 테스트 케이스에 대해 입력받은 N을 이용하여 zeroCount[N]과 oneCount[N]을 출력합니다.
💻 5. 코드 설명
import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val zeroCount = IntArray(41) { 0 }
val oneCount = IntArray(41) { 0 }
for (i in 0..40) {
if (i == 0) zeroCount[i] = 1
else if (i == 1) oneCount[i] = 1
else {
zeroCount[i] = zeroCount[i - 1] + zeroCount[i - 2]
oneCount[i] = oneCount[i - 1] + oneCount[i - 2]
}
}
repeat(readLine().toInt()) {
val n = readLine().toInt()
println("${zeroCount[n]} ${oneCount[n]}")
}
}
- `IntArray(41) { 0 }`: 크기가 41이고 모든 원소가 0으로 초기화된 정수형 배열을 생성합니다.
⏱️ 6. 시간 복잡도와 공간 복잡도 분석
- **시간 복잡도:** O(N). N까지 반복문을 한 번 수행하므로 시간 복잡도는 N에 선형적으로 비례합니다.
🎯 7. 결론
이 문제는 동적 계획법을 이용하여 효율적으로 해결할 수 있습니다. 단순한 재귀적 접근은 시간 초과가 발생하지만, 동적 계획법을 사용하면 O(N)의 시간 복잡도로 문제를 해결할 수 있습니다. N의 크기가 제한되어 있기 때문에 메모이제이션을 사용하는 동적 계획법이 매우 효과적이며, 코드 또한 간결하고 이해하기 쉽습니다. 이 문제를 통해 동적 계획법의 중요성과 효율성을 다시 한번 확인할 수 있었습니다. 추가적인 개선으로는 입력/출력 최적화를 위해 Scanner 대신 BufferedReader를 사용하는 등의 미세한 최적화가 있을 수 있지만, 성능 향상에는 큰 차이가 없을 것입니다.