동적 표를 이용하자.

동적표란 우리가 계산하면서 나온 결과값을들 저장해두는 표를 말한다.

이러한 행위를 왜 하는가?

관계기반 설계를 설명할 때, 탐색기반을 함께 설명했었다.

그때 탐색기반의 단점을 해소 하기 위해 '배제'를 한다고 했었는데 동적 표를 이용하여

비슷한 개념의 행위로 똑같은 효과를 낼 수 있다.

무슨 뜻이냐면, 이미 계산한 결과를 저장해두고, 중복되는 일이 있을때 그값을 꺼내 오기만 하면 된다.

이로써 중복된 연산을 피할 수 있고, 결론적으로 더 빠르고 효율적인 프로그램이 되는 것이다.

또한, 이전 값을 이용해서 다음 값들을 채워 나갈 수 있다.

이전 값이 반드시 필요한데 이건 관계 기반 설계에서 f(1)을 미리 구한 것과 같다.

ex) 피보나치 수열

1) 동적 표를 사용하지 않은 방식

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

2)사용한 방식

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

1번과 2번을 비교해 보겠다.

1번의 경우

5를 입력했다고 가정하면, f(4) + f(3) = f(3) + f(2) + f(2) + f(1) = f(1)+ f(2) + f(2) + f(2) + f(1) = 2f(1) + 3f(2)

3이 여러번 중복된다. 때문에 n이 클수록 연산 횟수가 기하급수적으로 쭉쭉 높아진다.

2번의 경우.

f(4) + f(3) 을 계산하면서 dp[3] 에 f(3)의 값을 저장하고, f(3)이 호출됬을때 return 함으로써, 중복된 연산을 피하게 되었다.

이처럼 동적표를 사용하면 중복된 연산을 줄일 수 있고, 재귀 호출이 많아질 때 Stack Overflow 가 나는 것도 방지할 수 있다.