Memoization

Memoization(메모이제이션)은 동적 계획법(Dynamic Programming)의 일종으로, 함수의 실행 결과를 저장해놓고 나중에 다시 그 함수를 호출하면 저장된 결과를 반환하여 중복 계산을 피하는 기법입니다. 즉, 한 번 계산한 값을 저장해두고 다음에 같은 입력값으로 함수가 호출될 때 저장된 값을 반환하는 방식입니다.

 

메모이제이션을 사용하면 같은 입력값으로 함수를 여러 번 호출할 때, 함수 내부의 연산을 다시 수행하지 않고 이미 계산된 결과를 반환하여 중복 계산을 피할 수 있습니다. 이를 통해 함수의 실행 속도를 향상시킬 수 있습니다.

메모이제이션은 보통 재귀 함수와 함께 사용됩니다. 재귀 함수에서 중복 계산이 많이 일어날 때, 메모이제이션을 활용하여 중복 계산을 피할 수 있습니다.

 

예를 들어, 피보나치 수열을 구하는 함수를 재귀적으로 구현할 때, 메모이제이션을 사용하면 함수 호출의 반복을 줄일 수 있습니다. 피보나치 수열에서 n번째 수를 구하는 함수에서 이미 구한 n번째 수의 결과를 배열에 저장해두고, 다음 번에 같은 n값으로 함수가 호출될 때는 배열에서 결과를 반환하면 됩니다. 이를 통해 함수 호출의 반복을 줄일 수 있습니다.

 

예시코드)

public class FibonacciMemoization {
    private static int[] memo = new int[100];

    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }

        if (memo[n] > 0) {
            return memo[n];
        }

        memo[n] = fibonacci(n - 1) + fibonacci(n - 2);

        return memo[n];
    }

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

위 코드에서 memo 배열은 이전에 계산한 결과를 저장해두는 용도로 사용됩니다. fibonacci 함수에서 n번째 피보나치 수를 구할 때, 먼저 memo 배열에서 n번째 수의 결과를 확인하고, 이미 구한 값이라면 계산을 수행하지 않고 바로 결과를 반환합니다. 만약 memo 배열에서 n번째 수의 결과를 찾지 못하면, 계산을 수행하고 결과를 memo 배열에 저장합니다.

 

이렇게 메모이제이션을 사용하면, 같은 입력값으로 함수를 여러 번 호출해도 계산을 반복하지 않고 이미 계산된 결과를 바로 반환하므로, 함수의 실행 속도가 향상됩니다.