한빛미디어

‘다이내믹 프로그래밍’이라고 하면 프로그래밍하는 방법이나 이와 관련된어떤 것을 떠올리기 쉽다. 또는 ‘다이내믹’이라고 하는 언어가 있나? 하는 생각을 할 수 도 있다. 하지만 다이내믹 프로그래밍은 ‘동적 계획법’으로 알려진 문제 풀이 방식을 뜻한다. C, Java 와 같은 프로그래밍언어를 이용해서 코드를 작성하는 것은 주어진 문제를 푸는 과정에서 풀이 방법을 컴퓨터가 알아 들을 수 있도록 형식화하는 일이다. 이 책이 인도 사람(?)인 미나크시와 카말 라와트에 의해 영어로작성되었고, 그 책을 박상은 님이 우리말로 옮겼다. 다이내믹프로그래밍에 대한 내용을 전하고자 하는 같은 목적을 영어와 우리말이라는 서로 다른 형태로 나타낸 것과 같다. 책이어떤 언어로 쓰였느냐 보다 어떤 내용의 책이냐가 더 중요한 것처럼, 어떤 언어를 사용했느냐 보다 어떤방식으로 문제를 푸느냐에 집중할 필요가 있다.

 이책은 문제를 푸는 방법에 대한 이야기를 다루고 있다. 특히 보다 효율적으로 문제를 푸는 방법에 대한것이다. 단순히 정답을 얻는 것에 그치지 않고, 어떻게 하면더 빠르게, 더 적은 메모리로 문제를 풀 수 있을 지 고민하고 있다.예를 들어 역 사이 최소 요금 문제의 경우, 15개의 역에 대해 일반적인 재귀 방식으로문제를 풀면 535 msec이 걸리는 반면, 메모 전략을이용하면 1 msec 이 채 걸리지 않는다. 또한 250개의 역에 대해 메모 전략이 1492 msec 이 걸리지만, 다이내믹 프로그래밍을 적용하면 4 msec 만 소요됨을 나타내고있다. 그렇다고 언제나 다이내믹 프로그래밍이 최선의 결과를 가져오는 것은 아님을 이 책은 분명히 하고있다. 250개 중에서 10개를 추출하는 방법의 수를 나타내는조합(Combination)의 경우, 메모 전략의 경우 2msec이 걸린 반면, 다이내믹 프로그래밍은 9msec의 시간이 필요했다. 상향식 다이내믹 프로그래밍에서는 전체문제의 풀이에 도달하기 전 모든 하위 문제에 대해서 계산을 수행하게 되고, 따라서 드물게는 실제 필요한것보다 훨씬 더 많은 하위 문제를 풀어야 하는 경우가 생길 수 있는 것이다.

 이책은 크게 4개의 파트로 구성되어 있다. 첫번째 파트에서는재귀 호출에 대한 전반적인 이해를 돕고, 두번째 파트에서 다이내믹 프로그래밍에 대해 소개하며 적용 전략을다룬다. 세번째 파트는 실전 문제를 기반으로 재귀 호출로 푸는 방법과 다이내믹 프로그래밍을 이용한 방법에대해 이야기한다. 끝으로 네번째 파트는 원서에는 없지만 책의 내용을 보다 쉽게 이해할 수 있도록 하는시간, 공간 복잡도에 대한 기본 내용과 더불어 온라인 코딩 테스트 환경을 체험해 볼 수 있는 코딜리티사이트에 대한 간략한 소개로 마무리하고 있다.

 ‘좋은개발자가 되려면 프로그래밍 언어를 배우는 것보다 문제 해결의 기술을 습득하는 것이 중요합니다.’ 책의서문에 있는 말이다. 좋은 개발자를 꿈꾼다면 곁에 두고 자주 꺼내어 보길 추천한다.