[Algorithm/Kotlin] 백준 1003번 피보나치 함수: DP를 활용한 풀이법

문제 설명

주어진 문제는 재귀적으로 정의된 피보나치 함수에서 0과 1이 출력되는 횟수를 구하는 것입니다.

C++의 재귀 구현을 보면, fibonacci(n)을 호출할 때 fibonacci(n-1)과 fibonacci(n-2)를 호출하는 방식으로 동작합니다.

이 과정에서 동일한 fibonacci 함수가 여러 번 호출되며 중복 계산이 발생합니다.

예를 들어, fibonacci(3)을 호출하면 아래와 같은 과정이 발생합니다:

1. fibonacci(3) -> fibonacci(2) + fibonacci(1)을 호출합니다.
2. fibonacci(2) -> fibonacci(1) + fibonacci(0)을 호출합니다.
3. fibonacci(1)이 1을 출력하고 반환합니다.
4. fibonacci(0)이 0을 출력하고 반환합니다.
5. fibonacci(2)의 결과를 이용해 fibonacci(3)을 계산합니다.

이런 방식은 중복 호출이 많아 비효율적이므로, DP(동적 계획법)를 활용하여 최적화할 필요가 있습니다.

---

문제 해결 아이디어

이 문제를 해결하기 위해 DP(동적 계획법, Dynamic Programming)를 사용합니다.

핵심 아이디어는 이미 계산한 값을 저장하고, 필요할 때 재사용하는 것입니다.

구현 코드 (Bottom-Up 방식)

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()
    val numbers = List(n) { br.readLine().toInt() }

    val fiboZero = IntArray(41)
    val fiboOne = IntArray(41)

    // 초기값을 설정합니다.
    fiboZero[0] = 1  // f(0)에서 0이 출력되는 횟수입니다.
    fiboOne[0] = 0   // f(0)에서 1이 출력되는 횟수입니다.

    fiboZero[1] = 0  // f(1)에서 0이 출력되는 횟수입니다.
    fiboOne[1] = 1   // f(1)에서 1이 출력되는 횟수입니다.

    // DP 점화식을 적용합니다.
    for (i in 2..40) {
        fiboZero[i] = fiboZero[i - 1] + fiboZero[i - 2]
        fiboOne[i] = fiboOne[i - 1] + fiboOne[i - 2]
    }

    val results = numbers.map { n -> "${fiboZero[n]} ${fiboOne[n]}" }

    bw.write(results.joinToString("\n"))
    bw.flush()
    bw.close()
}

---

시간 복잡도 분석

• 기본적인 피보나치 수열의 재귀 구현은 O(2^n)의 시간 복잡도를 가집니다. 이는 매우 비효율적입니다.
• DP를 활용한 해결법은 반복문을 한 번만 수행하므로 O(n)의 시간 복잡도를 가집니다.
• 따라서, 이 방식은 최대 입력값 40에 대해 매우 효율적으로 동작할 수 있습니다.

---

사용한 자료구조 및 알고리즘

사용한 자료구조

• IntArray(41):
  • 처음에는 mutableMapOf<Int, Pair<Int, Int>>를 사용하여 값을 저장했으나, 메모리 초과 문제가 발생했습니다.
  • 이를 해결하기 위해 최대 입력값 40까지만 저장하도록 IntArray(41)을 사용하여 제한을 두었습니다.
  • 배열을 사용하면 메모리 사용량이 줄어들고 빠른 조회가 가능하여 최적의 성능을 보장합니다.

사용한 알고리즘 (DP - 동적 계획법)

DP에는 여러 방식이 있으며, 대표적으로 다음과 같은 유형이 있습니다.

1. Top-Down 방식 (Memoization): 재귀를 이용하여 문제를 해결하면서, 중복 계산을 방지하기 위해 이미 계산된 값을 저장합니다.
2. Bottom-Up 방식 (Tabulation): 반복문을 사용하여 작은 문제부터 차근차근 해결하며 결과를 저장합니다.
3. 공간 최적화 DP: 저장할 배열을 줄여서 O(1)의 공간 복잡도로 최적화하는 방식입니다.

이 문제에서는 Bottom-Up 방식(반복문 DP)을 사용하여 해결하였습니다.

• 동적 계획법(DP, Dynamic Programming)은 이전에 계산한 값을 저장하고 재사용하는 기법입니다.
• 처음에는 재귀 방식으로 구현했지만, 메모리 초과 문제가 발생하여 반복문을 활용한 DP 방식으로 변경했습니다.
• fibonacci(n)을 재귀적으로 계산하는 대신, 배열을 사용하여 한 번만 계산하고, 이후에는 저장된 값을 바로 가져다 사용합니다.
• 이를 통해 중복 계산을 피하고, 실행 속도를 획기적으로 줄일 수 있습니다.

---

재귀를 사용하지 않는 이유

1. 중복 계산이 발생합니다.
2. 스택 오버플로우 가능성이 있습니다.
3. 반복문을 활용한 DP 방식이 훨씬 빠르고 안전합니다.

---

결론

이 문제는 DP를 활용하여 최적화할 수 있는 전형적인 피보나치 문제입니다. 처음에는 재귀 방식을 사용했지만, 메모리 초과 문제가 발생하여 반복문을 활용한 DP 방식으로 수정하였습니다. 배열을 활용하여 미리 계산하면 O(n)의 시간 복잡도로 빠르게 해결할 수 있습니다.

 

---

문제링크: https://www.acmicpc.net/problem/1003