[kotlin] 코틀린에서 람다식과 고차 함수를 사용하여 메모이제이션(memoization)을 구현하는 방법

15 Dec 2023

kotlin

메모이제이션(memoization)은 이전에 계산한 결과를 저장해서 재계산을 방지하여 성능을 향상시키는 기법입니다.

코틀린에서는 람다식과 고차 함수를 사용하여 간단하게 메모이제이션을 구현할 수 있습니다.

람다식을 사용한 메모이제이션 구현

val fibonacci: (Int) -> Long = { n ->
    val memo = mutableMapOf<Int, Long>()
    fun fib(k: Int): Long {
        return memo.computeIfAbsent(k) {
            if (it < 2) it.toLong()
            else fib(it - 1) + fib(it - 2)
        }
    }
    fib(n)
}

fun main() {
    println(fibonacci(10))  // 예상 출력: 55
    println(fibonacci(45))  // 예상 출력: 1134903170
}

위 예제에서 fibonacci 변수는 Int를 입력받아 Long을 반환하는 람다식으로 정의되어 있습니다. 내부에서는 memo라는 mutableMap을 사용하여 이전에 계산한 값을 저장합니다. 이를 통해 중복 계산을 피하고 성능을 향상시킬 수 있습니다.

고차 함수를 사용한 메모이제이션 구현

fun <T, R> memoize(function: (T) -> R): (T) -> R {
    val memo = mutableMapOf<T, R>()
    return { input ->
        memo.computeIfAbsent(input) { function(input) }
    }
}

fun main() {
    val fibonacci: (Int) -> Long = memoize { n: Int ->
        if (n < 2) n.toLong()
        else fibonacci(n - 1) + fibonacci(n - 2)
    }

    println(fibonacci(10))  // 예상 출력: 55
    println(fibonacci(45))  // 예상 출력: 1134903170
}

위 코드에서 memoize 함수는 고차 함수로 정의되어 있습니다. 이 함수는 주어진 입력값에 대해 이전에 계산한 결과를 저장하고, 입력값이 이미 계산되어 있는 경우에는 저장된 결과를 반환합니다.

이렇게 람다식과 고차 함수를 사용하여 메모이제이션을 구현하면 반복되는 계산을 효율적으로 처리할 수 있습니다.

참조: