[java] 함수형 인터페이스를 사용하여 다이나믹 프로그래밍을 구현하는 방법은 어떻게 되나요?

04 Dec 2023

java

다이나믹 프로그래밍(Dynamic Programming)은 여러 하위 문제들을 푸는 방식으로 큰 문제를 해결하는 알고리즘 기법입니다. 자바에서 함수형 프로그래밍을 지원하기 위해 JDK 8부터 함수형 인터페이스가 도입되었습니다. 함수형 인터페이스를 사용하여 다이나믹 프로그래밍 알고리즘을 구현할 수 있습니다. 아래는 함수형 인터페이스를 사용한 다이나믹 프로그래밍의 예시 코드입니다.

import java.util.HashMap;
import java.util.Map;
import java.util.function.Function;

public class DynamicProgrammingExample {
    private static final Map<Integer, Integer> cache = new HashMap<>();

    public static void main(String[] args) {
        int n = 5;
        int result = fibonacci(n);
        System.out.println("Fibonacci(" + n + ") = " + result);
    }

    public static int fibonacci(int n) {
        Function<Integer, Integer> fibonacciFunc = memoize(DynamicProgrammingExample::fibonacciInternal);
        return fibonacciFunc.apply(n);
    }

    private static int fibonacciInternal(int n) {
        if (n <= 1) {
            return n;
        }

        if (cache.containsKey(n)) {
            return cache.get(n);
        }

        int result = fibonacciInternal(n - 1) + fibonacciInternal(n - 2);
        cache.put(n, result);
        
        return result;
    }

    public static <T, R> Function<T, R> memoize(Function<T, R> function) {
        Map<T, R> cache = new HashMap<>();
        return input -> cache.computeIfAbsent(input, function);
    }
}

위의 코드는 피보나치 수열을 구하는 다이나믹 프로그래밍 예시입니다. fibonacci() 메소드는 Function<Integer, Integer> 타입의 함수형 인터페이스 fibonacciFunc를 사용하여 fibonacciInternal() 메소드를 호출합니다. fibonacciInternal() 메소드는 재귀적으로 자신을 호출하며, 이전에 계산한 결과를 cache에 저장하여 중복 계산을 피합니다. memoize() 메소드는 일반적인 함수를 메모이제이션하는 기능을 제공합니다.

함수형 인터페이스를 사용하여 다이나믹 프로그래밍을 구현하면 코드의 가독성과 유지 보수성을 향상시킬 수 있습니다. 함수형 프로그래밍의 특징을 활용하여 코드를 간결하고 효율적으로 작성할 수 있습니다.