동적 계획법(DP) 파트를 읽어보면서 아쉬운 점이 있습니다.
일관성있게 top-down 방식으로 DP를 설명하고 코드 또한 top-down 방식으로 적혀 있다는 점입니다.
때문에 알고스팟 문제들을 구글에 검색해도 대부분 종만북의 독자라고 추측이 가능할만큼 책의 소스코드와 거의 흡사하고 전부라고 하기엔 조심스럽지만 대부분 top-down 방식으로 코드가 작성되어 있습니다.
삼성SW 역량테스트와 같이 스택 메모리가 1MB로 작게 제한되어 있는 경우 top-down dp처럼 함수 call이 깊어질 수 있는 알고리즘의 경우 stack overflow 가능성이 높습니다.
책 후반부 bottom-up dp에 대해서 잠깐 다루긴 하지만, 대부분의 설명이 top-down 방식으로 알고리즘을 설계하는 과정을 다루고 있습니다.
물론 직관적으로 이해가 가능한 방식으로 top-down dp의 장점이 많고 알고리즘을 설계하는 논리의 흐름을 전개하기에도 top-down이 적합해보여 이해가 가지만, 개인적으로는 앞서 설명한 stack memory 문제로 bottom-up을 선호하고 일관성있게 bottom-up으로 밀고 있어서 다소 아쉽습니다. 책의 구성과 설명은 굉장히 좋습니다.
우선은 bottom-up dp로 책의 문제들을 전부 해결하는 것을 목표로 가지고 있고, 이후 저자가 알고리즘을 설계하는 흐름을 따라가볼 생각입니다.
'기록' 카테고리의 다른 글
| 근황 (0) | 2023.04.04 |
|---|---|
| [삼성SDS] 2023년 상반기 알고리즘 특강 및 SW검정 Professional 합격 후기 (0) | 2023.03.04 |