다이나믹 프로그래밍 ( Dynamic Programming )
( 참고 출저 : https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98 )
: 다이나믹 프로그래밍 ( 동적 계획법 )
메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법.
이미 계산된 결과 ( 작은 문제 ) 는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
일반적으로 탑 다운, 보텀 업 두 가지 방식으로 구현한다.
이름을 보고 제일 먼저 공부해보고 싶은 영역이라 여기까지 오는데 안달났었다.
드디어 이 멋진 이름의 프로그래밍이 어떤건지 알아보자.
일반적인 프로그래밍 분야에서의 동적 ( Dynamic )이란
자료구조에서 동적 할당 ( Dynamic Allocation ) 은 프로그램이 실행되는 도중에 실행에 필요한
메모리를 할당하는 기법을 의미한다.
하지만. 다이나믹 프로그래밍에서 Dynamic은 별다른 의미 없이 사용되는 단어라 한다.
내 기대가 처참이 부서지는 기분이지만 좀 더 알아보자.
: 다이나믹 프로그래밍은
1. 최적 부분 구조 ( Opimal Substructure )
2. 중복되는 부분 문제 ( Overlapping Subproblem )
의 조건을 만족할 때 사용할 수 있다.
1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다.
현재까지만 봐서는 고등학교 당시 수학문제를 풀 때 개념적인 내용과 유사한 것 같다.
사실 잊고있던 내용인데 문제를 풀 때에는 큰 덩어리를 보고 해결하려하면 복잡하고 손을 대기 어려워질 수 있다.
이를 얼마나 잘 분리하고 쉽게 만들어내는지 역시 중요하다.
: 예시
피보나치 수열
: 1,1,2,3,5,8,13,21,34,55,89, ...
이를 점화식 ( 인접한 항들 사이의 관계식 ) 으로 나타내면 다음과 같다.
A1 = 1, A2 = 1, An+2 = An + An+1
이때 재귀함수를 이용해 피보나치 수를 구하면,
O(2^n)의 시간복잡도를 갖게 된다.
굉장히 높은 시간복잡도를 갖고있지만,
점화식을 구현한 코딩인 만큼, 최적 부분 구조, 중복되는 부분의 조건을 충족하기 때문에
다이나믹 프로그래밍을 이용해보자.
재귀함수로 사용할 경우, 반복되어 연산되는 함수가 발생하게 된다.
f(3) = f(1) + f(2);
f(4) = f(3) + f(2);
만보아도 f(2)가 반복되는 것을 알 수 있다.
구현하는 상향식 하향식 방법중, 하향식 ( 탑 다운 )을 활용해보자.
활용 전 개념을 간단히 짚고가자.
탑다운 ( 하향식 )
보텀업 ( 상향식 )
다이나믹 프로그래밍의 전형적인 형태는 보텀 업 방식이다.
결과 저장용 리스트는 DP 테이블이라고 부른다.
메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 지칭한다.
메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아니다.
한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을수도 있다.
결국, 다이나믹 프로그래밍을 위해 메모이제이션을 사용할 수 있을 뿐 별개로 보는게 좋을 것 같다.
메모이제이션 ( Memoization )
: 한번 계산한 결과를 메모리 공간에 메모하는 기법.
같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
값을 기록해 놓는다는 점에서 캐싱( Caching )이라고도 한다.
메모이제이션이 어떤건가하고 기대했는데..
먼저 피보나치를 수열을 담아내고자 했던 코드가 메모이제이션이였다.
먼저 작성한 코드가 재귀함수로 구현하는 경우보다 속도가 더 빠르길래 이게 최선일까 생각했는데
연산을 반복할 필요없이 그 값을 갖도록 배열로 구현한게 다이나믹 프로그래밍이였던 것 같다.
이름이 멋져서 기대했는데 뭔가 실망이 커져가는 기분이다.
두 방식의 코드, 소요 시간을 계산한 코드를 보려면 참고하길 바란다.
( 깃 : https://github.com/kucnea/CodingTestPractice/blob/master/src/com/algorithm/dynamicProgramming/Fibonacci.java )
이 경우 0 인덱스부터 메모이제이션을 하기때문에 보텀업 방식인 것 같다. 이 부분에 자세한 설명은 없지만 그런 것 같다.
: 다이나믹 프로그래밍 vs 분할 정복
둘 모두 최적 부분 구조를 가질 때 사용할 수 있다.
: 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황
차이점으로는 부분 문제의 중복이다.
: 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.
분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.
첨언 : 아직 분할 정복이라는 개념을 알지 못하고 강의에서 제시된 것을 확인했지만
어릴때부터 공부할때를 보면, 사실 유형을 나누는 것이 강의하고 배우고 하는 데에는
여러가지 시각에서 볼 수 있기때문에 좋다고 생각하지만
그 과정을 넘어 훈련하고 수행하는데에는 유형을 구분하기보다 상황에 맞게 유연하게 대처할 수 있는 감각이 더 중요하다고 생각한다.
고로, 어떤 공통점이 있는지 어떤 차이점이 있고 해결방법에는 어떤 이유로 인해서 해결방법의 차이가 발생하는지 등을
이해하고나면 이 차이라는 것을 따로 외우거나 이 부분만 훈련할 필요는 없어진다고 생각한다.
더불어 헷갈릴 필요도 사라지지 않나 생각한다.
코딩쪽에는 완전 문외한 쪼렙이지만 문제를 바라보는 시각에 대한 개인적인 견해이므로 참고만 하시라.
분할 정복에 대한 설명이 이 이후 나왔다.
분할 정복의 대표적인 예시는 퀵 정렬이라고 한다. 분할하여 구간을 해결해 나가는 방식을 지칭하는 듯 하다.
그 구간을 클리어하고나면, 이후에 옇양을 주지 않고, 다시 호출하지도 않는데 완전히 이전 단계는 종결되는 것이다.
이러한 차이가 있어 메모이제이션같은 전 단계의 결과를 저장해놓더라도 활용할 이유가 없는 것이다.
즉, 부분 문제의 중복이 있지 않기떄문에 다이나믹 프로그래밍을 분할 정복에는 사용하지 않는다. 할 필요가 없다.
: 해당 영상의 강의를 보고 문제를 꼭 풀어보길 바란다.
본인에게는 새로운 접근의 개념이었기에 문제를 푸는데 정말 긴 시간이 걸렸다..
답을 보면 정말 간단한 코드인데 4시간을 붙들고 있기도 했고..
다이나믹 프로그래밍의 설명은 간단했지만, 그 문제풀이는 임펙트가 있었다.
와중에도 접근의 시점이 다른 경우가 절반정도 있었는데 테스트케이스가 충분하지 않아 확인해보지 못한 아쉬움이 있다.