[리뷰] 다이내믹 프로그래밍 완전정복

개요

본 리뷰는 한빛미디어 출판사 "다이내믹 프로그래밍 완전정복(미나크시, 카말 라와트 저)"을 읽고 얻은 지식을 정리한 글입니다.

무서운 `재귀`, 더 무서운 `Dynamic Programming(DP)`

프로그래머 혹은 컴퓨터 공학도라면 누구나 이 무서운 단어들을 들어봤을 것이다. 대부분의 프로그래머는 이런 용어가 세상에 존재하는구나 하는 정도로 넘어가고 잊어버린다. 이 단어들은 프로그래머에게 왜 무서운 단어가 되었을까? 먼저, 본 도서의 장점을 전달하기 위해 필자가 겪었던 다이내믹 프로그래밍 경험을 말씀드리고자 한다.

이름부터가 직관적이지 않다.
본 도서 서문 “옮긴이의 말”에서 역자는 Dynamic Programming을 “동적계획법”이 아닌 “다이내믹 프로그래밍”으로 음차하겠다고 소개한다. 자칫 독자가 프로그래밍 방법론으로 혼동할 수 있기 때문이다. 역자가 우려하듯 우리말 번역과정에서 진의가 꽤 소실된다.
리처드 벨만은 그의 자서전, “태풍의 눈”에서 Dynamic Programming의 어원을 다음과 같이 설명한다.
‘의사 결정 프로세스’라는 이름을 사용했지만, 여기에서 ‘프로세스(Process)’라는 단어를 사용하는데 여러가지 차질이 생겨버리고 만 것이다. 그래서 나는 사람들이 알지 못하게 ‘계획법(Programming)’이라는 단어를 붙였다. 또한 나는 이 프로세스가 다단계로 이루어져 있으며, 시가변적(time-varing)이며, ‘동적(Dynamic)’이다라는 개념(idea)이 전달되길 원했다. 이 단어야말로 내가 연구하는 알고리즘의 성질을 정확하게 짚어내었고, 게다가 윌슨에게도 피해를 입히지 않으며 공군도 이 단어에선 꼬투리를 잡지 못했으니 그야말로 일석이조의 효과를 누린 것이다.
벨만이 처한 상황에는 당시 모종의 정치적인(?) 이유가(상급자, 연구비 등) 개입되며 직관성이 흐려진 듯 하다. 그래서 필자는 대다수의 해석에 따라 다음과 같은 뉘앙스로 이해한다.
- 다이나믹(Dynamic) : 동적 메모리(시간에 따라 변하는 메모리)
- 프로그래밍(Programming) : 다단계(큰 문제 안에 작은 문제들이 중첩된)로 이루어진 문제 풀이계획
- 결론 : 시간에 따라 변하는 데이터를 고려하여, 큰 문제를 작은 문제로 쪼개서 푸는 방식
실무에서 좀처럼 쓰이지 않는다.
```
여러분은 지금까지 재귀 혹은 다이내믹 프로그래밍을 몇번이나 활용하셨는지? 
```
필자 역시 대학원 혹은 취업 면접이 있을때만 책으로 접했고, 실무에서 사용한 경험은 많지 않다. 가장 쉬운 경험을 예로 들자면 즐겨찾기 관리를 위한 App을 개발하면서 즐겨찾기 폴더를 순회하여 폴더별 저장된 URL을 가져오는 용도로 활용한 적이 있다.
시간복잡도와 찰떡궁합이다.
위에서 언급한 즐겨찾기 관리 App의 경우를 보자. 테스트를 진행하며 폴더 Depth를 100으로 늘렸더니 생각외로 꽤 오랜 수행시간이 소모되었다. 재귀함수를 이용하여 매우 소량의 코드로 문제를 해결한데다 기억이 가물가물한 재귀를 제법 빠르게 구현했기에 나름 속으로 ‘아직 살아있구만!’라고 자화자찬하던 와중에 약간 충격을 받았다.
다른 관련코드들 역시 시간을 잡아먹을만한 부분이 보이지 않아서 결국 알고리즘 책을 간만에 펼쳤다. 문제는 의외로 간단했다. 재귀 함수의 시간복잡도가 지수시간을 잡아먹고 있었던 것이다. 알고리즘의 기초 내공의 중요함을 다시금 깨닫게 된 순간이었다.
메모리 구조와 밀접한 관련이 있다.(공간복잡도)
경력 2년차 초보때 벌어진 일이라 혼자만의 추측이 시작되었다. “결국 재귀를 버려야 하나..? 이래서 사람들이 재귀를 안쓰는 거구만..!”등등…결국 Loop를 이용해서 다시 구현할까 생각했는데 왠지 지는 느낌이 들어 싫었다. 결국 다시 알고리즘 책을 펴보았다. 역시나 선배들이 해결해 온 역사를 통해 힌트를 얻을 수 있었는데 메모이제이션(Memoization)라는 캐시 기능을 활용하여 재귀 함수가 호출될 때 시간복잡도를 O(N)으로 줄일 수 있었다. 배열 하나 썼을뿐인데 이렇게 속도가 빨라지다니! 조금 더 흥미가 생기기 시작했다.
메모리 구조를 분석하며 얻은 또 하나의 수확은 Stack 시각화를 통한 개념 명확화였다. 메모리 및 스택을 그림으로 그리고 활성레코드 함수 변화를 정리해보니 어렴풋했던 재귀 호출의 동작방식이 명확하게 이해되는 것이었다. 당시 정립한 개념 덕분에 지금도 DP를 활용하여 개발할 때 머리 속 스택그림의 도움을 많이 받는다.
일상속의 직관과 거리가 멀어 전략이 필요하다.
꼬리에 꼬리를 끝없이 물어가는 재귀 호출을 구현 시 명확한 기준이 없다면 재귀적 사고의 악순환(?)이라는 주화입마에 빠지고 만다. 머리가 복잡해지면서 뇌는 본능적으로 재귀를 피하려고 한다. 따라서 가장 중요한 것은 뇌에게 탈출구를 안내할 수 있는 종료조건과 작은 문제에 대한 명확한 정의이다.
재귀가 보통 Top-Down 방식을 이용하는 것과 달리(Top-Down 방식은 이름에서 유추할 수 있듯이 보다 큰 인자에서 작은 인자로의 재귀 호출을 반복한다. 따라서 동일한 인자를 가지는 함수가 매번 수행되어 성능상 치명적인 약점을 가지게 된다. 대신 코드의 가독성이 높다.) DP에서는 Bottom-Up방식을 이용한다.
재귀에 비해 크게 어려울 것이 없는것이 함수대신 변수(배열 등)의 이미 연산된 작은 값들을 활용하여 큰 값들을 반복적으로 채워나가는 방식이다. 덕분에 동일값에 대한 연산을 피하여 성능을 높일 수 있는 장점이 있다. 재귀와 마찬가지로 DP를 적용할 수 있는 문제인지 어떻게 세부적으로 구현할 지 등에 대한 전략이 존재한다.
면접과 실무를 넘어서서…
DP 자체를 명확히 이해하는 것도 중요하지만 공학분야에 있어서만큼은 언제, 어디에 적용할 수 있는지를 아는 것이 더 중요하다. (참고 : WHAT « WHEN & WHERE) DP는 언제 어디에 적용할 수 있을까?
- 부분적으로는 O(n^3) 등 다항식 수준의 시간복잡도를 O(n*logn) 등의 로그 수준으로 줄여 성능을 높일경우 DP를 활용할 수 있을지 판단해야 한다.
- 더불어 한단계 수준을 넘어선 전혀 다른 영역에의 응용이 가능하다. 예를들면 강화학습이 있다.
  강화학습은 각 Step별 Action을 취하는 문제를 모델이 없는(Model-free)상태에서 MDP(Markov Decision Process)를 활용하여 풀어나가는 방법이다. 때문에 Model의 Environment에 해당하는 Reward, State Transition Probability등을 최적화하기 위해 Learning(학습)을 해 나간다.
- DP와의 접점이 느껴지시지 않는지?
  DP는 Model을 완벽히 안다는 전제하에(Model-based) Bellman Equation을 풀어 Environment를 구하는 방식이다. 그래서 Planning이라고 부르며 이를 보완하여 Learning을 통해 Environment를 최적의 상태로 찾아가는 것 즉, 강화학습 알고리즘을 만들게 된 것이다. 때문에 DP의 개념 및 활용방안을 정확히 모른다면 강화학습에 대한 이해는 물론이고 보다 나은 방법을 찾기가 거의 불가능할 것이다.
- 더불어 문자열 연산을 다루는 NLP에 있어서도 DP의 문제 해결방식은 큰 도움을 준다.

DP에 대해 더 설명하고 싶지만 필자의 짧은 지식으로는 여기까지다. 하지만 경제학 등 DP의 활용도는 무궁무진할 것이고 어떻게 다른 지식과 융합, 보완하느냐에 따라 멋진 걸작이 나올지도 모른다. 필자가 경험한 이 일련의 과정에 비추어 본 도서가 어떤 장점을 갖는지 다음장에서 간단히 다뤄보고자 한다.

다이내믹 프로그래밍을 위한 본 도서의 장점

앞장에서 다이내믹 프로그래밍 경험 및 스스로 학습해왔던 과정을 간략하게 설명하였지만, 사실 그 간략함이 몇 년간 다이내믹 프로그래밍과 관련하여 학습한 지식의 거의 전부이다.

본 도서를 읽으며 놀라웠던 점은 필자가 겪었던 시행착오나 전략이 고스란히 담겨있다는 것이다. 필자의 지식이 고수들에 비할바 못하는것을 알면서도 꼭 이런 양서를 만나면 나만알고 있었을 듯한 밑천이 외부에 다 털린 느낌이 들어 배가 아프다. 하수라서 그런것일까?

다이내믹 프로그래밍 자체를 적용하기 위해 몇일간 고민했던 흔적은 아이러니하게도 자연어로 정리하면 고작 한줄 정도 담긴다. 즉, 다이내믹 프로그래밍을 자연어로 정리하면 설명력이 크게 떨어진다. 미묘한 기법과 뉘앙스를 전달하기 위한 사고과정에 대한 뚜렷한 설명이 거의 불가능하다는 것이다.

때문에 본 도서 또한 전략과 이론에 관련된 내용이 매우 짧다. 거의 대부분의 페이지는 예제와 예제의 설명, 시각적 설명이 차지하고 있다. 많은 예제를 바탕으로 사고과정을 공유하는 것이 거의 유일한 해결책이라는 생각이 드는데 본 도서가 그런 접근법을 통해 다이내믹 프로그래밍 예제를 같이 풀어보고 알기쉽게 설명해줌으로써 주화입마에 빠질 우려를 줄여준다.

명쾌한 전략제시
앞서 설명한 바와 같이 자연어로 다이내믹 프로그래밍이라는 문제풀이 접근방식을 설명하긴 보통 어려운 일이 아니다. 대신 기억하기 쉬운 핵심 전략을 머리속에 두고 접근하는 것과 대책없이 프로그래밍을 시작하는 것은 큰 차이가 있다. 아래 그림은 다이내믹 프로그래밍과 메모이제이션 그리고 재귀 호출에 대한 핵심 전략을 기술한 페이지이다.
사고과정의 이해를 돕는 시각화
다이내믹 프로그래밍은 예제와 실전을 통한 사고과정의 고민의 깊이가 어느 정도인지에 따라 그 활용 능력이 갈린다. 사고과정이 일상의 직관과는 동떨어져있어 쉽게 포기하기 쉬운데 절대 포기하지 않도록 저자, 역자의 고민의 흔적이 설명에 녹아있다. 더불어 아래 그림과 같이 직관적인 이해를 돕는 시각화를 통해 이해도를 크게 높여준다.
원리를 바탕으로 한 전달력, 중간중간 깨알같은 선수지식의 소개
기저에 숨어있는 원리를 설명하지 않고 소스코드의 주석과 결과만으로는 다이내믹의 정수를 얻기 힘들다. 기본 원리를 절대 놓치지 않으려는 시도가 이 서적의 또 다른 매력이다.
예를들면 다이내믹 프로그래밍이 가지는 장점을 소개하기 위해, 또 이해도를 높이기 위해 메모리 구조를 설명한다. 이를 통해 공간복잡도의 계산이 훨씬 쉬워지고 다이내믹 프로그래밍이 얻게되는 시간, 공간복잡도 성능향상이 어느정도인지 개념적으로 와 닿도록 도와준다.
아래 그림은 메모리 구조 및 스택영역에서의 재귀함수의 활성레코드를 보여줌으로써 머리속에 스택의 동작방식을 이해하고 있는것이 얼마나 다이내믹 프로그래밍에 대한 이해도를 높여주는지 알 수 있게 해준다.
다이내믹 프로그래밍과 관련된 거의 모든 예제
본 도서에 소개된 재귀 및 다이내믹 프로그래밍의 관련 예제는 무려 20개가 넘는다. 그 정도면 거의 왠만한 실무를 커버할 수 있는 수준이 아닌가 싶다. 제대로 이해를 못했다면 예제의 감각이라도 충분히 잡아 반드시 활용할 수 있게 해주려는 저자의 의지가 돋보인다.
아래 그림은 필자가 재미있게 풀어본 예제인 “문자열 인터리빙 확인” 문제인데 사고과정을 명확하게 시각화하여 이해를 돕는다.
더불어 아래 “거스름돈 최적화” 문제와 같이 DP와 유사한 탐욕 알고리즘과의 비교도 시도한다. 탐욕 알고리즘이 반드시 최적해가 아닌 케이스를 설명하며 비교 과정을 통해 DP 특성에 대한 이해를 더욱 높여준다.

본 도서의 모든 소스코드는 C와 Python 두종류의 언어로 제공된다. 두 언어를 모두 활용한다면 보다 이해도를 높일 수 있다.
기타
끝으로 본 도서를 학습하며 도움이 될만한 유용한 참고자료를 아래 링크로 남긴다.

누가 읽어야 하는가?

프로그래머 누구나(특히 면접시험을 앞둔 프로그래머)
재귀호출과 다이내믹 프로그래밍에 정면 도전하고 싶은 분
AI분야의 프로그래머(특히 강화학습, NLP에 많은 도움이 됨)

책의 구성 및 요약

이 책은 크게 세부분으로 구성되며, 각 파트에서 다루는 내용을 아래와 같이 요약해 보았다.

1. 재귀호출과 메모리, 활용전략(Part1)
- 재귀 접근전략, 재귀 호출과 메모리
- 최적의 하위구조, 하위 문제의 반복 계산, 메모이제이션(메모전략)
- 예제 : sum(n), 점화식, 하노이탑, 피보나치, 역사이 최소 비용 등
2. 다이내믹 프로그래밍(Part2)
- Top-Down 및 Bottom-Up 접근방식의 차이
- 다이내믹 프로그래밍의 적용을 위한 전략
- 예제 : 부분 문자열, 계승함수, 이진트리, 행렬 최소이동비용, 타일공터 채우기, 경우의수, 연속부분 배열의 최댓값 등
3. 실전연습(Part3)
- 최소교정비용문제, 직사각형의 총 경로수, 문자열 인터리빙, 부분집합의 합
- 최장공통부분수열, 거스름돈 최적화, 철근자르기, 0 -1 배낭, 최장회문부분수열, 달결낙하퍼즐 등
- 부록 : 시간 및 공간복잡도, 코딜리티(온라인 코딩 테스트) 활용법

요약하며…

다이내믹 프로그래밍이 어려운 가장 큰 이유는 일반적인 직관과는 다른 사고방식을 필요로 한다는 점이다. 특히 사고과정을 면대면이 아닌 책으로 기술한다는 것은 더욱 어려운 일일 것이다.

이런 어려움을 해결하고자 본 도서는 명확한 전략, 사고과정에 대한 깊은 설명, 시각화를 이용한 사고과정의 보조, 원리를 중시한 핵심 개념 설명을 활용하여 DP에 대한 이해도를 극대화 시켜준다. 왜 이 책이 실리콘밸리의 우수한 IT인력을 공급하는 인도 그리고 해외 시장에서 베스트 셀러에 올랐는지 알 수 있는 부분이다.

아쉬운 점이 하나 있다면 독자로 하여금 DP에 대한 이해를 포기하지 않도록 책 중간중간에 선수 지식이 종종 소개되는데 어느정도 내공이 찬 프로그래머라면 재귀 및 DP에만 집중하기에 약간 산만한 느낌을 받을 수 있겠다는 생각이 들었다. 하지만 초중급자를 위해서는 이만큼 친절할 수가 없다.

아울러 C, Python 두가지 언어로 예제를 작성한 바 포인터의 유무, 객체지향의 유무 등 언어 특성에 따라 가려지기 쉬운 DP의 개념을 두 언어로 구현, 비교해봄으로써 이해를 명확하게 할 수 있다는 장점이 있다. 더불어 두 언어 자체에 대한 이해도가 높아지는 것은 보너스다.

예쁜 색상으로 디자인되고 무겁지 않아 들고 다니면 왠지 뿌듯한 감성이 충만된다. 강화학습 또는 NLP를 학습하며 DP의 명확한 개념을 잡고 싶은 분, 알고리즘 코딩 테스트를 앞둔 분, DP를 뽀개 완전히 두려움을 없애고 싶은 분께 꼭 일독을 권한다.

<한빛미디어 출판사>
믿고보는 “한빛미디어 출판사”. IT분야에서 독보적인 양질의 도서를 출판하는 회사입니다. “나는 프로그래머다” 팟캐스트 후원, DevGround2019 행사, 리뷰어 모집, 다양한 학습 지원 등 다양한 분야에서 사회에 공헌하는 개발자와 공생하는 업체입니다. IT분야에 관심 있으시다면 한빛미디어의 책으로 후회없는 출발을 하실 수 있습니다.

한빛미디어 바로가기