[Unity] 알고리즘 - 동적 계획법

1. 동적 계획법의 정의

C# 문법 수업 중 동적 계획법(Dynamic Programming)이라는 개념을 접했다.

설명에 따르면, 동적 계획법은

 

"큰 문제를 작은 하위 문제들로 나누고, 그 결과를 저장해두어
중복 계산 없이 효율적으로 문제를 해결하는 알고리즘 설계 기법" 이라고 한다.

 

내용인 즉, 중간 계산값을 저장하여 시간 복잡도를 줄일 수 있는 방식이라는 것이다.

이 정의를 보고 두 가지 의문이 생겼다.

1.  왜 '이전에 계산한 값을 저장'하면 중복을 피할 수 있을까?
2.  중간 값을 저장하는 게 어떻게 시간 복잡도를 줄이는 걸까?

이 궁금증은 예시를 통해 어느 정도 해결되었다.

 

2.동적 계획법의 예시 - 피보나치 수열

 

예를 들어 아래와 같이 피보나치 수열을 구하는 코드가 있다고 해보자.

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

 

이 코드에서 Fib(5)를 구하려면 Fib(4)와 Fib(3)을 구해야 한다.
하지만 Fib(4)는 또다시 Fib(3)과 Fib(2)를 호출하고, Fib(3) 역시 재귀 호출된다.
즉, 동일한 값에 대해 여러 번 계산이 반복되는 것이다.
숫자가 커질수록 재귀 호출 횟수는 기하급수적으로 늘어나고, 시간 복잡도도 급격히 증가한다.

그래서 계산식을 저장할 수 있게 코드를 아래와 같이 수정하면,

int[] memo = new int[100];

int Fib(int n)
{
    if (n <= 1) 
    {
    	return n;
    }
    
    if (memo[n] != 0) 
    {
    	return memo[n];
    }
    else
    {
    	return memo[n] = Fib(n-1) + Fib(n-2);
    }
}

 

memo에 저장된 값을 바로 가져오면 재귀함수의 호출 없이 빠르게 값을 가져올 수 있게 된다.
계산한 값을 한 번 저장해 주는것만으로 재귀함수 사용을 줄이고 시간 복잡도 역시 크게 줄일 수 있게 된다.

 

3.내가 느낀 '동적'의 의미

 

피보나치 수열을 통해 동적 계획법이 어떤식으로 사용하는가에 대한 이해는 했다.
그런데 왜 동적(Dynamic) 이라고 부를까. 동적이라는건 움직임이 있는건데 어떤 부분 때문에 동적이라고 할까?
정답은 모르겠지만 개인적 생각으로는 동적 계획법으로 저장한 데이터를 다양하게 활용할 수 있기 때문이 아닐까?

피보나치 수열의 계산값을 통해 또다른 피보나치를 만들어 볼 수도 있고, 게임의 다음 레벨 경험치를 설정하는 등으로 사용할 수도 있고 말이다.

즉, 계산 결과가 고정된 것이 아니라, 다른 용도로 계속해서 활용할 수 구조라는 점에서 동적이라는 표현을 붙인거 같기도 하다.
움직이지 못하는것 보단 움직일 수있는게 더 효율적이니 동적 계획법이 효율적이라는 느낌으로 마무리 했다.