동적 프로그래밍(Dynamic Programming)에 대해 알아보자!

동적 프로그래밍이란?

• 큰 문제를 작은 단위로 쪼개서 반복 분할하여 푸는 접근 방식입니다.
  
  네 맞습니다. DFS와 같은 개념입니다.
  기본적으로 DFS문제는 재귀함수를 사용해서 풀어가는 방식이 일반적입니다. 그럼 동적프로그래밍은 DFS와 같은 것인가??
  
  결론부터 말씀드리면, 답은 No입니다. 동적 프로그래밍은 작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 이용하여 큰 문제의 해결 방법을 도출합니다.

---

DFS와 동적프로그래밍의 차이점!!

 

여기 숫자가 들어있는 정삼각형 구조가 있습니다. 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 리턴하는 문제입니다.

 

문제를 처음 접하게되면 기본적으로 DFS로 문제를 풀어야겠다는 생각이 들 것입니다.

 DFS로 접근하게 되면,

 7+3+8+2+4 = 24,
 7+3+8+2+5 = 25,
 7+3+8+7+5 = 30,
 7+3+8+7+2 = 27,
 .
 .
 .
 7+8+0+4+5 = 24.

 

이 5줄짜리 정삼각형의 모든 DFS경우의 수를 재귀함수를 통해서 구하고, 그 과정에서 최대 숫자를 계속 갱신해주면서 문제를 풀어갈 것이라고 예상됩니다.

 

 하지만 여기 함정이 있습니다.

 

삼각형이 최대 500줄이라는 것입니다. 위 대표 예제와 같이 5줄이라면 문제를 DFS로 푸는 것에 있어서 딱히 상관이 없겠지만 500줄이라면 엄청난 수의 연산을 해야합니다.

 

이 때 동적 프로그래밍을 사용하게 되면 연산의 수가 현저히 감소하게 됩니다. 다음 유튜브 영상은 10분짜리 영상인데 참고하시면 정말 이해가 빠르게 되실 겁니다.

<참고 영상: https://youtu.be/0bqfTzpWySY> >> 제꺼 아닙니다.

 

 

• 제가 이해한 동적 프로그래밍의 개념은 중복되는 연산을 저장하여 불필요한 연산을 줄이며 결과값을 도출해내는 방법입니다. 이 때 저장하고 필요할 때 꺼내쓰는 과정을 메모이제이션(Memoization)이라고 합니다.
  
  
• 다음은 재귀함수로만 피보나치 수열을 구현한 코드입니다.

    void Start()
    {
        //결과값 출력.
        Debug.Log(solution(10));
    }
    public int solution(int n)
    {
        //딕셔너리 초기화.
        dicFib = new Dictionary<int, long>();

        long answer = 0;

        //함수 호출.
        answer = Normal_Fibonacci(n);

        return (int)answer;
    }
    
	//재귀함수로만 구현한 피보나치 수열 함수.
    public long Normal_Fibonacci(int n)
    {
        if (n <= 1)
        {
            return n;
        }

        long num1 = Normal_Fibonacci(n - 2);
        Debug.Log("n : " + n + "num1 = " + num1);
        long num2 = Normal_Fibonacci(n - 1);
        Debug.Log("n : " + n + "num2 = " + num2);

        long result = (num1 + num2) % 1234567;
        Debug.Log("n : " + n + "result = " + result);

        return result;

    }

• 콘솔창에 265줄이 출력됐습니다.

 

• 다음은 Dictionary클래스를 사용하여 동적 프로그래밍을 통해 구현한 코드입니다.

    void Start()
    {
        //결과값 출력.
        Debug.Log(solution(10));
    }
    public int solution(int n)
    {
        //딕셔너리 초기화.
        dicFib = new Dictionary<int, long>();

        long answer = 0;

        //함수 호출.
        answer = Dynamic_Fibonacci(n);

        return (int)answer;
    }
    
	Dictionary<int, long> dicFib;
    
    //동적 프로그래밍을 사용한 피보나치 수열 함수.
    public long Dynamic_Fibonacci(int n)
    {
        if (dicFib.ContainsKey(n))
            return dicFib[n];

        if (n <= 1)
        {
            dicFib.Add(n, n);
            return n;
        }

        long num1 = Dynamic_Fibonacci(n - 2);
        Debug.Log("n : " + n + "num1 = " + num1);

        long num2 = Dynamic_Fibonacci(n - 1);
        Debug.Log("n : " + n + "num2 = " + num2);

        long result = (num1 + num2)%1234567;
        Debug.Log("n : " + n + "result = " + result);

        dicFib.Add(n, result);

        return result;
    }

• 콘솔창에 28줄이 출력됐습니다.
  
  

결론

: 이진트리 문제와 같이 DFS 등으로 해결하는 문제에서 경우의 수가 너무 많아진다면 동적 프로그래밍을 사용하여 중복 연산 줄이고 시간 효율을 올릴 수 있다.

---