[코틀린/Kotlin] 메모이제이션(Memoization)

메모이제이션

• 한번 계산한 결과를 저장하고 같은 계산을 반복할 때 저장된 값을 재사용하는 기법
• 계산 결과를 매모(배열, Map 등)에 저장하여 사용
• 중복 계산을 피해서 속도를 빠르게 개선
• 동적 계획법(DP, Dynamic Programming)에서 자주 사용

사용 이유

재귀를 사용한 피보나치

fun fib(n: Int): Int {
    if (n <= 1) return n
    return fib(n - 1) + fib(n - 2)
}

→ fib(5)를 사용한 예시

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) = 1
│   │   │   └── fib(0) = 0
│   │   └── fib(1) = 1
│   └── fib(2) ← 중복!
│       ├── fib(1)
│       └── fib(0)
└── fib(3) ← 중복!

fib(2), fib(3) 등 같은 값이 중복하여 계산

재귀와 메모이제이션: Top-down 방식

val memo = IntArray(100) { -1 }

fun fib(n: Int): Int {
    if (n <= 1) return n
    if (memo[n] != -1) return memo[n]     // 이미 계산된 값이 있다면 리턴

    memo[n] = fib(n - 1) + fib(n - 2)      // 계산 후 저장
    return memo[n]
}

• memo[n] ≠ -1 → 이미 구한 값으로 바로 리턴
• 구한적 없을 경우 계산 후 IntArray에 저장하고 리턴
• O(n)시간 복잡도로 빠른 계산 가능
• Top-Down: 문제를 쪼개어 해결
  큰 문제를 해결하기 위하여 더 작은 문제로 재귀 호출 → 이미 계산한 결과를 저장하여 재활용

반복문과 메모이제이션: Bottom-up 방식

fun fib(n: Int): Int {
    val dp = IntArray(n + 1)
    dp[0] = 0
    if (n > 0) dp[1] = 1

    for (i in 2..n) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }

    return dp[n]
}

• 재귀 없이 반복문과 메모이제이션을 사용
• Bottom-up: 작은 문제부터 차례대로 답을 구하면서 해결
  반복문을 이용하여 작은 문제부터 계산

문제

1. 한 번에 계단을 1칸 또는 2칸을 오를 수 있을 때, n개의 계단을 오르는 방법의 수는 몇 가지일까요?

[조건]

• 함수의 이름은 climbStairs으로 한다.
• 입력값은 n이며, 자료형은 Int이다.
• 반환값도 Int이다.
• 재귀와 메모이제이션을 사용한 Top-down방식과 반복문과 메모이제이션을 사용한 Bottom-up방식 두가지로 구현한다.

[예시]

• n = 1 → 1가지 (1)
• n = 2 → 2가지 (1+1, 2)
• n = 3 → 3가지 (1+1+1, 1+2, 2+1)
• n = 4 → 5가지

 

답:

[Top-down]

val memo = IntArray(100) { -1 }

fun climStairs(n: Int): Int {
    if (n <= 1) return 1
    if (memo[n] != -1) return memo[n]

    memo[n] = climStairs(n - 1) + climStairs(n - 2)
    return memo[n]
}

[Bottom-up]

fun climStairs(n: Int): Int {
    val memo = IntArray(n + 1)
    memo[0] = 0
    if (n > 0) memo[1] = 1

    for (i in 2..n) {
        memo[i] = memo[i - 1] + memo[i - 2]
    }

    return memo[n]
}

 

 

[보충]

1. 메모이제이션 배열을 기본 파라미터로 받기

fun climbStairs(n: Int, memo: IntArray = IntArray(n + 1) { -1 }): Int {
    if (n <= 1) return 1
    if (memo[n] != -1) return memo[n]
    
    memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo)
    return memo[n]
}

• 기본 파라미터로 memo: IntArray = IntArray(n + 1) { -1 }를 지정하여 함수를 처음 호출할 때만 배열이 생성, 재귀 호출 시에는 같은 배열을 재사용 → 재귀 깊이가 깊어져도 새로운 배열이 생성되는 불필요한 비용 막음
• 배열의 크기가 n+1로 생성되어 크기를 설정하지 않아도 됨
  • 기본값을 설정한 경우이므로 사용자가 직접 memo를 지정하여 사용 가능

• 재귀가 깊게 중첩되어 여러번 호출되면 기본 값으로 배열이 계속 새로 만들어지는 위험이 있음
  → 해당 함수는 사용자가 한 번만 호출 → 이미 생성된 memo 배열을 넘겨 받으면서 재사용

 

2. 공간 최적화: Bottom-up

• 배열 전체를 저장하지 않고 필요한 이전 두 값만 저장하여 메모리를 절약

fun climbStairsOptimized(n: Int): Int {
    if (n == 0 || n == 1) return 1

    var prev2 = 1  // f(0)
    var prev1 = 1  // f(1)
    var current = 0

    for (i in 2..n) {
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    }

    return current
}

O(n)시간 복잡도는 유지되면서 공간복잡도를 O(1)로 해결 가능

 

3. 계단 오르기가 피보나치 수열 로직과 같은 이유

• n칸을 오르는 방법의 수를 f(n)이라고 했을때
• 마지막에 1칸을 오르려면 이전 단계에는 n-1칸을 올라왔어야함
• 마지막에 2칸을 오르려면 이전 단계에는 n-2칸을 올라왔어야함

→ n단계에 도달하는 방법은 n-1단계에서 한 칸 올라오는 방법 + n-2단계에서 2칸 올라오는 방법

→ 재귀함수와 같은 f(n) = f(n-1) + f(n-2) 구조를 가지게 됨