한빛미디어

 책의 리뷰에 앞서. 이 책은 어려운 책이다 @_@.. 기본적인 미적분과 선형대수 그리고 데이터 구조와 알고리즘의 유도식 및 점화식 등에 대한 지식 없이 이 책을 접한다면, 상당한 피로를 호소할 수 있다.

따라서 앞서 말한 지식들에 대해서 본인이 충분히 알고 있고, 이를 통해 보다 심화된 지식을 얻고자 하는 의지가 있는 독자 혹은 충분한 인내심을 가지고 반복하여 학습을 할 마음이 있는 독자들에게 권하는 책이다.

이 책은 세상의 현상들을 수학적으로 해석한 책이다. 솔직히 우리가 살고 있는 세상은 수학으로 이뤄진 세상이며, 다만 우리는 이를 가시적으로 보고 이해하기에 세상을 이루는 것은 수학이 아닌 물질 그 자체라고 생각하는 것이리라 생각된다.

딥러닝도 그렇고 우리가 생각하는 뇌의 역치도 그렇고 각 신경들 전달 물질, 나아가 원자와 핵 모두가 물리, 즉 논리로 이루어져 있다. 어느 하나 논리(수학)이 빠지지 않은 것이 없다. 아마도 논리가 없다는 것은 진정한 무일 것이다. 즉 void(null)이 되는 것이다.

아.. 책에 들어가기 전에 사문이 길었다. 이 책은 앞서 말한 것과 같이 세상의 문제들을 수학적으로 표현하여 이를 지해롭게 해결하기 위한 접근법과 해석하는 방법에 대해서 설명하고 있다.

【책의 구성】 '제대로 배우는 수학적 최적화'의 책의 구성은 어떠한가.

 이 책은 CONTENTS를 제외한다면 총 4개의 챕터로 구성되어 있으며 연속 최적화 문제, 이산 최적화 문제 두 개의 그룹으로 나누어 책의 내용이 구성되어 있다.

솔직히 연속 최적화 문제는 블로거에게 큰 흥미가 없어서 이산 최적화 문제의 챕터들만 몇 가지 추려 중점적으로 리뷰해 보았다. (그렇다고 연속 최적화 문제가 중요하지 않다는 것은 아니므로 반드시 읽어보시길 권장한다.)

각 챕터의 구성은 소쳅터를 중심으로 해당 알고리즘의 배경을 설명하고, 이에 대한 시간 복잡도와 점화식을 단계?라는 형태로 표현하고 있다. (각 챕터마다 구성이 조금씩 상이하기에 정확히 이러하다고 단정 짓긴 어려운 구조이다.) 또한 수리적 식이 자주 등장하는데 이해하고 보면 그리 어려운 수준은 아니다.(앞서 말한 지식들에 대해서 충분히 알고 있다면 말이다.!) 그렇기에 시간을 들여 차근차근 읽어보면 충분히 이해하고 지식을 얻어 갈수 있는 책이다.

4챕터 : 탐욕 알고리즘

 탐욕 알고리즘에 관한 수리적 접근을 설명하고 있다. 일반적으로 전산 학부에서 배우는 탐욕 알고리즘이란. 바로 앞에 있는 최대치를 취하여 최종적으로 가장 높은 이익을 취하는 알고리즘을 의미한다.

하지만 보편적으로는 위의 알고리즘을 이용한 접근이 설루션이 될 수 있지만, 냅색(knapsack) 알고리즘처럼 탐욕 접근법으로 해결을 시도했다간 낭패를 보는 경우도 있다는 것을 명심하도록 하자.

간략하게 여기서 정리한 탐욕 알고리즘의 수리적 조건은 하기와 같다.

초기 설루션의 조건은 하기와 같다. (순수 우리 표현에 따르면 솔루션이 아닌 설루션이 맞다.[책에는 설루션으로 쓰여있음])

- 초기 설루션 x = (0,0,0) t로 한다. (초깃값을 의미. 0으로 배열을 초기화함을 의미한다.)

- 시그마 xi = B를 만족하면 종료한다. ( 즉 사용할 수 있는 최댓값에 달하면 그리드 탐색은 더 이상 수행하지 않음을 의미한다.)

- di(xi)-max dk(xk)를 만족하는 사업 j를 구한다. xj = xj +1로 하고 단계 2로 돌아간다. (즉, 변화량 최대 치의 값을 만족하는 각 값들의 합을 의미함)

이를 통해 해당 알고리즘의 대략적인 수리적 점화/접근 식을 얻을 수 있으며, 이를 수학적으로 추론함으로써 시간 복잡도 역시 어느 정도 예측이 가능해진다.

복잡해 보이지만 알맹이를 이해하면 그리 어렵지? 않은 흐름이다.

 ​

4챕터 : 동적 계획법 // 최소 비용 탄성 매칭 문제

 앞서 탐욕 알고리즘에 대해서 간략하게 살펴보았다. 그렇다면 당연히 동적 계획법에 대해서도 살펴봐야 하는 것이 알고리즘의 스텝이라면 스텝이라 할 수 있다.

점화식과 수식을 세우는 것도 모든 상황에 따라 다양할 수 있다. 따라서 아래의 예시는 하나의 예시일 뿐임을 사전에 말씀드린다.

- f(1,1) = c11로 정의하며, f(i, 1) = f(i-1,1) + c_{i1} ( i = 2, .., m)으로 정의한다. (초기 DP Table을 설정하는 단계이다.)

- j = n 이면 종료한다. 그렇지 않으면 j = j+1로 한다. (종료 조건과 다음 스텝으로 넘어갈 조건에 대해서 명시한다.)

- f(1, j) = f(1, j-1) + cj로 한다. f(i, j)=min{f(i-1, j-1), f(i-1, j), f(i, j-1)} +cij(i=2, .., m)으로 하고 단계 2로 돌아간다. (실제로 DP Table을 이용한 값을 도출하는 부분이다. 이전 수행했던 값들을 기반으로 현재 최상의 값을 구하는 스텝이라고 생각하면 된다.)

우리가 일반적으로 프로그래밍 대회나 혹은 알고리즘 스터디를 하다 보면 배우는 내용을 수리 식으로 정리한 내용들이다. 보기엔 어려워 보이나 앞서 언급한 것처럼 내용을 알고 보면 이해하기에 그리 어렵지 않음을 알 수 있다.

【 "제대로 배우는 수학적 최적화"를 읽고서…….】

 이 책은 수리학에서 사용하는 용어가 많이 등장한다. 굉장히 나에겐 생소했던 부분이기도 하다. 가령 하강 방향이라던가 수렴비라던가 국소 수렴성이라던가 라그랑주 제곱수라는 표현이라든가 굉장히 생소한 용어들이다. 이제껏 전산학을 나름 오래 해 왔으나 한 번도 들어보진 용어들이다. 아마도 수리학 분야에서 사용하는 용어들이나 공식 혹은 정리들이지 않을까 싶다.

전산학도 어찌 보면 수리학에서 시작한 학문이라 할 수 있다. 다만 전산학의 경우 이산수학에 그 기틀을 다지고 있다고 봐도 과언이 아닐 것이다. 그만큼 수학과 전산학은 때려야 땔 수 없는 관계에 있는 것이다.

이번 리뷰에서는 내가 잘 아는 부분을 중심으로 챕터 내용을 요약해 보았다. 다른 부분들도 위와 크게 다르지 않다. 가정을 세우고 가정을 검증하고 가정대로 수행하고 최종적으로 가정을 입증(증명) 하는 과정으로 책의 구성이 이루어져 있다.

다만 확실한 것은 이 책은 한번 읽고 덮는 그런 책은 아니라는 것이다. 내용이 무겁다. 한번 읽어서는 확실히 내 것으로 만들 수 없다. 필자도 서문에서 언급하였듯, 책을 여러 번 숙독하고 회독해야 최종적으로 내 것으로 만들 수 있는 그런 책이다.

그렇기에 꾸준한 마음으로, 한결같은 호기심으로 전산학전 난제와 접근법을 수리적으로 표현하고 해석하여 풀이할 준비가 되어있는 사람들이 이 책으로 공부한다면 틀림없이 많은 것을 얻어 갈 수 있을 것이라 생각된다.

#본 도서는 "한빛미디어 <나는 리뷰어다> 활동을 위해서 책을 제공받아 작성된 서평입니다.

###### 감사합니다 ######