Day 42 (23.09.13)
자료구조와 알고리즘 기초 마지막날이다.
어제 마지막에 진행한 Graph - DFS, BFS 문제에 대한 리뷰로 시작하였다.
강사님의 설명대로 3일 안에 자료구조와 알고리즘 커리큘럼을 해내는 것은 아주 빡센 경험이었다.
관련 문제에 대한 리뷰를 마치고 동적 계획법(Dynamic Programming; DP) 파트가 진행이 되었는데 거의 오늘 강의 시간의 대부분을 사용하게 되었다. 코딩 문제에 접근 및 해결할 때 진행하게 되는 방법론 느낌으로 이해했다.
크게 Top-Down방식과 Bottom-Up으로 나누어져 있는데 이에 따른 재귀를 이용한 혹은 기초 반복문을 이용해서 솔루션을 구성하고, 시간복잡도 문제를 해결하기 위해 각각 memo를 이용한 memoization과 tabulation를 진행한다.
실제 적용하는 문제 진행 시 해당 문제에 대한 솔루션과 시간복잡도 해결법 적용을 함께 생각하기가 굉장히 어려웠다. 물론 단기간에 급하게 풀려하다보니 당연한 결과라고 생각한다.
이후 좀 더 꾸준한 연습이 필요할 것 같다. 체계적으로 계획을 세워 부트캠프가 끝날 때까지 꾸준히 진행해야 할 것 같다.
마지막으로 Heap과 다익스트라(Dijkstra)에 대해서 개관을 진행한 후 마무리하게 되었다.
TIL
< 자료구조와 알고리즘 기초 >
- 동적 계획법(Dynamic Programming; DP)
- Top-Down(with memoization)
- Bottom-Up(with tabulation)
- Heap
- Dijkstra
:)