C# 메모화(Memoization)

메모화란 무엇인가?

코드 최적화를 위해 메모화(memoization) 기법을 적용할 수 있다. 메모화는 특정 입력 값에 대한 함수의 처리 결과를 기억하는 과정이라고 할 수 있다. 즉, 특정 함수에 입력 값을 전달할 때마다 프로그래밍이 결과를 기억해 두고 이후 입력 값이 같다면 함수를 다시 실행하지 않고 저장된 곳에서 결과를 얻는다.

 

기존 GetFactorial()

using System;

public partial class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine(GetFactorial(5));
    }

    static int GetFactorial(int n)
    {
        if (n == 0) 
        {
            return 1;
        }

        return n * GetFactorial(n - 1);
    }
}

 

GetFactorial() 함수에 메모화를 적용하려면 GetFactorial()이 결괏값을 반환할 때마다 이 값을 저장해야 한다. 그에 따라 수정한 모습은 다음과 같다.

 

메모화를 적용한 GetFactorial()

using System;
using System.Collections.Generic;

public partial class Program
{
    private static Dictionary<int, int> memoizeDic = new Dictionary<int, int>();

    static void Main(string[] args)
    {
        Console.WriteLine(GetFactorial(5));
    }

    static int GetFactorial(int n)
    {
        if (n == 0) 
        {
            return 1;
        }

        if (memoizeDic.ContainsKey(n)) 
        {
            return memoizeDic[n];
        }

        int i = n * GetFactorial(n - 1);
        memoizeDic.Add(n, i);

        return i;
    }
}

 

GetFactorialMemoization()이 갖는 차이점은 이전에 호출한 적이 있는 인수에 대해서는 결과를 이미 가지고 있다는 것이다. 

 

코드를 보면, 먼저 처리한 적이 있는 인수인지를 확인한다. 만약 그렇다면 함수를 호출할 필요 없이 딕셔너리에서 결과를 찾아 반환한다. 새로운 값이 전달됐다면 함수를 호출하고 결과를 딕셔너리에 저장한다. 메모화를 이용하면 이처럼 같은 인수로 반복적으로 호출이 발생하는 것을 방지함으로써 코드 최적화를 꾀할 수 있다. 예를 들어 10을 인수로 GetFactorialMemoization()을 호출하고, 이후에 10을 인수로 다시 호출하는 경우 처리 시간을 대폭 절약할 수 있다. 이 예의 경우, 재귀 함수이므로 10을 전달하면 1부터 9도 호출이 일어난다. 따라서 10개의 인수에 대한 결과 값이 딕셔너리에 저장되며, 이들을 이용한 이후의 호출에서 효과를 볼 수 있다.

 

그럼 GetFactorial()과 GetFactorialMemoization()의 성능을 비교해 보자. 9216을 인수로 5회씩 호출하겠다.

 

using System;
using System.Collections.Generic;
using System.Diagnostics;

public partial class Program
{
    private static Dictionary<int, int> memoizeDic = new Dictionary<int, int>();

    private static void RunFactorial()
    {
        Stopwatch sw = new Stopwatch();
        int factorialResult = 0;

        Console.WriteLine("RunFactorial() function is called");
        Console.WriteLine("Get Factorial of 9216");

        for (int i = 0; i <= 5; i++) 
        {
            sw.Restart();
            factorialResult = GetFactorial(9216);
            sw.Stop();

            Console.WriteLine($"Time elapse ({i}):{sw.ElapsedTicks * 1000000000 / Stopwatch.Frequency} ns");
        }
    }

    static void Main(string[] args)
    {
        RunFactorial();
    }

    static int GetFactorial(int n)
    {
        if (n == 0)
        {
            return 1;
        }

        return n * GetFactorial(n - 1);
    }
}

 

일반 Factorial 함수 호출시

 

다음으로 GetFactorialMemoization()을 사용해서 함수를 호출해 보자.

 

using System;
using System.Collections.Generic;
using System.Diagnostics;

public partial class Program
{
    private static Dictionary<int, int> memoizeDic = new Dictionary<int, int>();

    private static void RunFactorial()
    {
        Stopwatch sw = new Stopwatch();
        int factorialResult = 0;

        Console.WriteLine("RunFactorial() function is called");
        Console.WriteLine("Get Factorial of 9216");

        for (int i = 0; i <= 5; i++) 
        {
            sw.Restart();
            factorialResult = GetFactorialMemoization(9216);
            sw.Stop();

            Console.WriteLine($"Time elapse ({i}):{sw.ElapsedTicks * 1000000000 / Stopwatch.Frequency} ns");
        }
    }

    static void Main(string[] args)
    {
        RunFactorial();
    }

    static int GetFactorialMemoization(int n)
    {
        if (n == 0) 
        {
            return 1;
        }

        if (memoizeDic.ContainsKey(n)) 
        {
            return memoizeDic[n];
        }

        int i = n * GetFactorial(n - 1);
        memoizeDic.Add(n, i);

        return i;
    }
}

 

메모화된 Factorial 함수를 호출한 경우

 

최초 호출 시에 추가 시간이 필요하지만 이후의 호출에서 엄청난 성능 향상을 확인할 수 있다.

 

함께 보면 좋은 글

C# [백준 BAEKJOON] 2407번 조합