WEEK04 - 컴퓨팅사고로의 전환4
이번주에는 알고리즘 마지막 주차로 동적프로그래밍과 그리디 알고리즘을 공부했다.
동적 프로그래밍 (DP. Dynamic Programming)
동적 프로그래밍(이하 DP)이란 '한번 계산한 과정은 다시 계산하지 않는다'는 컨셉이 적용된 알고리즘이다.
재귀 알고리즘 또는 분할 정복법에서 특정한 경우에 동일한 호출이 여러번 발생하게 되는데 이는 경우의 수가 많아질 경우 걸리는 시간이 지수적으로 증가하게 된다. 이러한 경우 DP를 적용할 수 있다.
여기서 특정한 경우란 두가지 조건이 만족하는 경우이다. 먼저 최적부분구조여야 하는데 이는 분할정복이 가능한가 (큰 문제를 작은 문제로 나눌 수 있는가)를 의미한다. 그리고 작은 문제들이 동일한 문제들로써 반복적으로 해결할 수 있는 경우여야 한다. 이를 중복되는 부분문제 라고 한다.
DP는 한번 계산이 진행된 경우 결과값을 배열에 저장했다가 동일한 호출 발생시에 배열의 값을 return 함으로써 구현할 수 있다.
DP를 구현하는 방법에는 두가지가 있다. 첫번째는 하향식으로, 재귀를 이용한 방법이다. 이 경우 계산되지 않은 경우에는 계산을 진행하고, 이미 저장된 값이 있는 경우 그 값을 바로 반환해준다. 이때 계산한 값을 저장해두는 것을 memoization이라고 한다. (memoization은 DP와 별개의 개념이지만, DP를 하향식으로 구현할 경우 사용되는 방법이다.) 두번째는 상향식이며 반복문을 이용한 방법이다. 이는 작은 문제부터 차곡차곡 계산하여 DP table에 저장하는 방식이다.
그리디 알고리즘 (Greedy Algorithm)
그리디 알고리즘은 탐욕 알고리즘이라고도 하며 항상 최선의 선택을 하여 최적해를 구하는 방식이다.
그리디 알고리즘은 반드시 최선의 선택만으로도 최적해를 구할 수 있다는 근거가 있는 경우에만 사용가능하다. 따라서 그리디 알고리즘을 고려할때에는 최선의 선택만으로 최적해를 구할 수 있는지부터 고민해야 한다.
회고 및 정리
DP 알고리즘 관련 문제를 해결하는 과정에서 반복적으로 어려움을 겪었다. 진행하다가 막혀서 돌아보면 계속 DP table에 무엇을 저장할 것인지 명확히 정의를 내리지 않고 있었다. 하여 DP를 적용할 경우 DP table을 어떠한 목적으로 사용할 것인지 정의를 명확히 해야겠다고 느꼈다.
이번주차까지해서 4주간의 컴퓨팅사고로의 전환이 마무리되었다. 4주간 진행하면서 느꼈던 점은 해결해야할 문제에 부딪혔을 때 먼저 문제가 어떤 문제인지 잘 정의해야 한다는 점, 어떤 알고리즘을 적용해야할지 아이디어를 생각하고 구체적인 과정을 고민한 후에 차근차근 진행해야 한다는 점이었다.
WEEK05부터는 OS프로젝트에 들어가기 전 3주간 RB트리, malloc, Proxy서버 구현을 진행한다. 두려움보다는 기대감으로 계속 화이팅 해나가야겠다.
