dynamic programming(dp)와 메모이제이션(memoization) - C#

오랜만에 유니티가 아닌 C# 글을 남긴다. 요즘 순수 C# 공부를 시작해서 얻게 되는 게
은근히 많은 것 같다. 한 문제 한 문제 풀 때마다 얻는 게 생겨 신기하다.
아무튼, 이 글에서는 동적 프로그래밍과 메모이제이션에 대해서 설명하겠다.

---

1. 동적 계획법 - dynamic programming(dp)

우선 동적 계획법 자체의 정의는 한 문제를 더 작은 두 문제로 나누어 해결하는 기법이다.
이때 "분할 정복"이라는 개념의 정의와 매우 유사해지는데, 동적 계획법은 중복이 존재하는
경우에 사용하는 기법이다. 중복이 존재한다고 하면 조금 애매해 보일 수도 있는데,
작은 부분의 값이 항상 같은 경우라고 정의하고 싶다.
분할 정복은 작은 여러 개의 부분으로 나눴을 때 중복이 없는 경우이다.
 
동적 계획법을 구글에다가 검색해 보면 메모이제이션이라는 개념이 많이 따라올 것이다.
메모이제이션이 중복되는 계산량을 획기적으로 줄여주는 최적화 방법이기 때문이다.
이 경우 많은 사람들이 피보나치수열을 통해서 설명하게 된다.
 

2. 메모이제이션

앞서 설명했듯이, 중복되는 연산을 줄이는 알고리즘 기법이다.
일반적인 경우에 배열이나 리스트, 딕셔너리 같은 저장공간을 만들어놓고
값을 연산하여 저장해 놓은 다음, 나중에 꺼내 쓰는 방식이다.
이렇게 말하면 나 또한 이해가 안 될 것 같다. 조금 보기 싫더라도 코드로 이해해 보자.
 

void fibonacci(int n) {
	if(n <= 2) {
    	return 1;
    } else {
    	return fibonacci(n-1) + fibonacci(n-2);
    }
 }

먼저 이 코드를 보자. 피보나치수열의 특징을 잘 가지고 있다. 하지만 직접 연산을 해보면 어떨까?
n에 3부터 4까지 넣는다고 가정해 보자.
 
fibonacci(3)은 fibonacci(2)와 fibonacci(1)을 호출한다.
fibonacci(4)는 fibonacci(3)과 fibonacci(2)를 호출한다.
그리고 fibonacci(4)에서 호출한 fibonacci(3) 또한 fibonacci(1)과 fibonacci(2)를 호출한다.
 
벌써 중복된 계산이 정말 많다. 값을 미리 저장했다면 연산이 필요 없었을 텐데..
이건 3과 4를 넣은 실험이지만 코딩테스트 같은 곳은 엄청 많이 연산하기에
시간 초과가 뜰 수밖에 없다. 논리가 맞음에도 시간 초과로 실패하는 모습을 볼 수 있다.
이걸 어떻게 해결할 수 있을까?
 

int[] series = new int[100];

int fibonacci(int n)
{
    if (n <= 2)
    {
        series[n - 1] = 1; 
        return 1;
    }
    else
    {
        if (series[n - 1] == 0)
        {
            series[n - 1] = fibonacci(n - 1) + fibonacci(n - 2);
        }
        return series[n-1];
    }
}

 

series라는 배열을 만들었다.

아니면 크기를 적지 않아도 되는 리스트를 사용해도 좋다.

 

아무튼, 이렇게 함수에 어떠한 값을 넣었을 때, 그걸 연산한 다음 기록한다.

그 이후, 다음번에 그 값을 찾을 때는 그저 저장된 값을 배열에서 꺼내주면 된다.

이렇게 해서 시간복잡도를 엄청나게 줄일 수 있다.

 

재귀함수를 이용할 때 특히 이런 경우가 많다고 한다.

피보나치 함수가 너무 유명한 메모이제이션 활용의 예시라서

비슷한 문제가 나왔을 때 기억해서 쓸 수 있을지 모르겠으나 최적화 기법을

하나 더 알았다는 사실 자체는 굉장히 긍정적으로 보인다.

---

요즘 서브 블로그를 만들어서 코딩 테스트를 하고 있는데,

거기에는 백준 문제 풀이를 올리고 있고, 해보다가 꽤 쓸만한 지식들을 얻으면

이렇게 메인 블로그에 업로드해보려 하고 있다. 유니티가 아닌 순수 C#은 별로

안 해봐서 어색하긴 하지만 새롭게 얻는 점이 많아서 만족하고 있다.

더욱 발전할 수 있기를 바란다.

---

이상으로 도움이 되었길 바라며,

끝.