다이내믹 프로그래밍 완전 정복 리뷰
나는 다이내믹 프로그래밍이 정확히 무엇을 의미하는지 전혀 알지 못하는 상태였기 때문에 약간의 부담감을 안고 책을 읽기 시작했는데, 그런 나에게 이 책은 다이내믹 프로그래밍이 무엇인지에 대해서 맛볼 수 있는 중요한 기회를 선사해주었다.
일단 책의 처음은 재귀에 대한 내용으로 시작한다. 재귀의 경우 꽤나 자주 접했기에 비교적 쉽게 이해할 수 있었다. 책의 내용 중에서 재귀를 사용할 때 주의해야할 것에 대해서 아래와 같이 나와있었다.
- 재귀에는 항상 종료 조건이 있어야 한다. 종료 조건이 없으면 재귀 호출이 무한히 반복된다.
- 재귀 함수는 전체 작업의 일부만 수행하고 나머지는 재귀 호출에 위임한다.
어찌보면 너무나 당연한 이야기였지만, 너무나 당연하기 때문에 간과할 수 있는 부분에 대해서 명확하게 짚어주고 있었다.
또한 재귀에 대해 설명하면서 아래와 같은 말도 덧붙이고 있었다.
쉬운 코드와 복잡한 코드 중에 선택해야 한다면, 성능이나 메모리의 이점이 있지 않은 한 쉬운 코드가 좋습니다.
같은 문제를 비슷한 노력으로 해결할 수 있다면 재귀 호출을 사용하지 않는 쪽으로 구현하는 것이 바람직합니다. 만들어진 프로그램을 실행하보면 재귀 호출을 사용하지 않는 경우가 실행도 빠르고 필요한 메모리의 양도 작습니다.
깊이 공감한다. 정말 명확한 이유가 있지 않은 한 재귀 호출을 남발하는 것은 좋지 않다고 생각한다. 물론 재귀 호출로 문제를 푸는 것이 우아하고 세련된 방법처럼 보일 수 있지만, 재귀 호출은 이를 사용하지 않는 경우에 비해 일반적으로 더 많은 비용이 들기 때문이다.
이어서 선행 재귀와 후행 재귀에 대해서도 설명해주고 있는데, 연결 리스트의 탐색 예제를 통해 설명해주는 부분이 나름 직관적으로 와닿았다.
그리고 재귀 호출과 메모리에 대한 내용이 있었는데, 특히 프로세스 주소 공간에 대한 설명은 꽤나 유용했다. 코드 영역, 데이터 영역, 스택 영역, 힙 영역 각각에 대해 간략하지만 핵심적인 설명이 있었으며 특히나 프로그램의 로딩부터 함수의 호출로 인한 메모리의 변화가 어떻게 일어나는지에 대해 설명하는 부분이 유용하다고 느껴졌다.
재귀를 사용할 때와 사용하지 않을 때 메모리의 상태 비교를 통해 책에서는 아래와 같이 이야기한다.
재귀 호출을 사용하면 메모리와 실행 시간 양 측면에서 비용이 증가합니다.
이에 이어 다음으로는 재귀 접근 방식이 가지는 두 가지 특징에 대해서 언급하는데 그 첫번째는 최적의 하위 구조로, 아래와 같이 설명하고 있다.
어떤 문제의 풀이법을 같은 문제의 더 작은 문제로 정의하는 게 최적의 풀이법이라면 이 문제는 최적의 하위 구조를 가졌다고 합니다. 최적의 하위 구조를 가진 문제는 다이내믹 프로그래밍 방법을 적용하기 좋은 문제입니다.
그리고 두번째 특징으로는 하위 문제의 반복 계산에 대해서 언급하는데, 책의 본문에서는 피보나치 수열 계산 문제에서의 하위 문제의 반복 계산을 예로 들고 있다. 그리고 이어서 하위 문제의 반복 계산이 발생하여 수행 시간이 증가하는 문제를 해결하기 위한 방법으로 메모 전략(메모이제이션)을 소개하는데, 이를 쉽게 말하면 어떤 하위 문제를 계산했을 때 그 결과를 일종의 캐시에 저장하여 같은 하위 문제를 다시 풀 때 이미 저장된 결과를 사용하는 방식을 의미한다. 또한 메모 전략에 대해서 아래와 같이 언급하고 있다.
메모 전략도 재귀 접근 방법에 속합니다.
메모 전략 = 재귀 호출 + 캐시 - 하위 문제의 반복 계산.
이어서 드디어 주인공인 다이내믹 프로그래밍에 대한 내용이 본격적으로 등장하는데, 가장 처음 알게된 것은 문제 해결의 방향이 재귀 호출, 또는 메모 전략은 하향식인 반면 다이내믹 프로그래밍은 상향식이라는 사실이었다.
앞에서 재귀 호출 또는 메모 전략을 통해 풀었던 예제들을 보여주면서 이를 다이내믹 프로그래밍으로 해결할 수 있음을 보여주는데, 이와 함께 직접 깃헙에 재귀 호출, 메모 전략, 다이내믹 프로그래밍의 실행 시간을 비교해볼 수 있는 예제 코드를 올려놨다는 점이 좋았다.
동일한 문제를 각각 하향식 접근 방법과 상향식 접근 방법로 풀어내는 예제 코드들로 하여금 그 둘이 어떤 차이점을 가지는지를 비교해볼 수 있었다.
그리고 결론적으로 다이내믹 프로그래밍은 재귀 호출 자체로부터 발생하는 부하를 피하기 위해 상향식으로 문제를 해결할 수 있다, 라는 내용을 전달하고 있었다.
더 나아가 그렇다고 다이내믹 프로그래밍이 은탄환은 아니라는 것에 대해서 설명해주는데, 하향식 접근 방법에서는 모든 하위 문제를 풀지 않고 전체 문제의 해답을 얻을 때 필요한 하위 문제만 풀었으나 상향식인 다이내믹 프로그래밍에서는 모든 하위 문제에 대해 계산을 수행하여 드물게 실제 필요한 것보다 훨씬 더 많은 하위 문제를 풀어야 하는 부작용이 발생하기도 한다는 점에 대해서 설명해주고 있다.
이에 이어 다이내믹 프로그래밍이 어떤 것이다, 라는 설명에서 그치지 않고 실제로 어떻게 적용할 수 있는지를 알려주는데, 다이내믹 프로그래밍을 사용해서 문제를 푸는 기본적인 순서는 아래와 같이 알려주고 있다.
- 재귀 호출을 사용한 풀이법 작성.
- 다이내믹 프로그래밍이나 메모 전략을 사용해 풀이법 개선.
그리고 어떤 문제가 다이내믹 프로그래밍 적용 가능 여부를 확인할 수 있는 체크리스트도 아래와 같이 알려주고 있다.
- 문제가 최적의 하위 구조를 가지고 있는지.
- 하위 문제를 반복 계산하는지.
- 최적화, 최대화 또는 최소화나 어떤 작업의 경우의 수를 구하는 유형의 문제인지.
더불어 다이내믹 프로그래밍을 적용하기 위한 단계식 접근법도 친절하게 알려주고 있다.
- 다이내믹 프로그래밍 적용 가능한 경우인지 확인.
- 점화식 또는 재귀 과정 정의.
- 문제를 하위 문제를 사용해 하향식으로 정의.
- 맨 아래에 해당하는 기본 경우에 대한 답을 정의.
- 종료 조건 추가.
- (선택적) 메모 전략 시도.
- 상향식으로 문제 풀이 도전.
위와 같이 실제로 적용할 수 있는 방법에 대해서도 설명해주고 있는 점이 상당히 유용하다고 느껴졌는데, 다이내믹 프로그래밍이 무엇인지 알았다고 해서 어디에 어떻게 사용해야 하는지 단번에 알 수 있는 건 아니라고 느꼈기 때문이다. 그리고 이러한 단계식 접근법을 여러 예제 문제들에 적용하는 과정을 보여주고 있다는 점에서 상당히 마음에 들었다.
이 책의 전체적인 소감은 이론적인 부분의 설명은 적당하게, 최대한 부담되지 않는 선에서 하면서 실제로 적용해볼 수 있는 여러 문제를 소개해주고 풀어내는 과정을 통해 재귀 호출과 메모 전략, 다이내믹 프로그래밍에 대해서 알려주는 실용적인 책, 이라는 것이었다. 본문 자체에도 꽤나 많은 예제들이 수록되어 있으며, 마지막 장인 5장은 아예 통째로 다양한 실전 문제들을 수록하여 위에서 안내해주는 단계식 접근법을 통해 풀어내는 과정을 보여주면서 연습문제를 통해 독자들 스스로도 한껏 두뇌를 사용할 수 있는 기회를 제공해주고 있다.
재귀 호출과 메모 전략, 다이내믹 프로그래밍에 대해서 관심이 있으나 아직 입문하지 못한 분들에게 추천하기 좋은 책이라는 생각이 든다.
위 글은 출판사 한빛미디어의 “나는 리뷰어다” 11월 미션 서적으로 제공받은 “다이내믹 프로그래밍 완전 정복(미나크시, 카말 라와트 지음, 박상은 옮김)”의 리뷰입니다.