30장 : 오토마타(Automata)와 XML 파서

강의의 마지막입니다.  마지막을 무엇으로 할까 고민하다가 "오토마타(Automata)"를 골랐습니다. 

오토마타는 상태(State) 집합과 상태간의 전이(Transition)를 모델링한 것으로 이들이 하나의 시스템을 이루면 "유한상태 기계(Finite-State Machine)"라고 합니다.

실로 현실의 많은 것들이 이 오토마타로 표현될 수 있습니다만 가장 대표적으로 쓰이는 분야가 논리적으로 구성된 프로그래밍 언어를 해석하는 파서(Parser) 분야입니다.  현재 개발할 때 사용하는 C++, Java 등의 언어들은 더 낮은 레벨의 언어로 변환되어야 하는데,  고레벨 언어를 해석하는 역할을 오토마타가 맡고 있습니다.

이 장에서는 오토마타의 기본적인 개념을 살펴 보고, 오토마타를 활용한 예로서 XML 문서를 해석하는 XML 파서를 만들어 보도록 하겠습니다.

29장 : 알고리즘 개발 방법론 2 (Greedy Method, Backtracking)


알고리즘 개발 방법론 두번째 장으로 욕심쟁이 기법(탐욕, Greedy Method)와 백트래킹(Backtracking)에 대해서 알아봅니다.

사실 이 두가지 기법은 모든 방법을 동원해서도 풀리지 않는 문제가 있을 때, 마지막으로 시도해볼 수 있는 방법입니다.  혹은 문제의 최적화된 해법을 구하기 전에 미리 그 해답을 찾는 방법이기도 합니다.

그런 의미에서 매우 중요하고 알아두어야 할 기법입니다. 그런데 그 내용을 들여다 보면 우리가 흔히 하는 작업들에 대해 체계적으로 정리해 놓은 것에 불과하다는 생각이 듭니다.

28장 : 알고리즘 개발 방법론 1 (Divide and Conquer, Dynamic Programming)


지금까지 살펴 본 알고리즘들은 주어진 문제를 최적으로 해결하는 것들이었습니다.  우리의 선조들이 힘든 연구와 통찰을 통해 찾아낸 아름답고도 멋진 해법들입니다.

하지만 이들은 처음 접한 문제들에 대해 어떻게 해법을 찾을 수 있었을까요? 또 우리가 새로운 문제를 접하게 될 때, 참조할 만한 비슷한 연구 결과가 없다면 어떻게 해결해야 할까요?

"알고리즘 개발 방법론"이라는 소제목으로 소개시켜드리고자 하는 네가지 접근법은 바로 이렇게 특별한 최적화된 해법이 없는 문제에 대해 어떻게 접근하여 최적화된 혹은 쓸만한 해법을 찾을 수 있는지에 대한 "방법론"을 살펴볼 것입니다.

27장 : 회귀와 스플라인 (Regression & Spline)


이번 장에서 배우는 회귀(Regression)과 스플라인(Spline)은 다른 큰 학문 분야의 맛보기로 제시한 것입니다.

회귀는 통계학의 기본이 되는 개념으로, 실제 측정된 데이터로부터 일반화된 수식을 얻어내는 기법을 의미합니다.  측정된 데이터가 많을 수록 더 정확한 수식을 얻어낼 수 있으며, 이 수식을 바탕으로 미래에 일어날 사건을 예측할 수 있다는 점에서 "통계 학습(Statistical Learning)"의 출발점이라 볼 수 있습니다.

통계 학습은 요즘 뜨고 있는 빅데이터 분석과도 밀접한 관계를 가지고 있습니다.

스플라인(Spline)은 몇몇 제어점을 이용하여 부드러운 곡선을 만들어내는 수학적 도구입니다.  회귀와 비슷한 개념을 기하학적으로 바라보는 관점입니다.

26장 : 수치 미적분

미분(Differential)과 적분(Integral)의 개념이 창안되고 나서 수학의 세계는 혁명적인 변화를 경험하게 됩니다.

현재 상태만을 주시하던 인간들은 상태의 변화를 볼 수 있게 되었고, 더 나아가 상태 변화의 변화까지 볼 수 있게 되었습니다.  비유하자면 심봉사가 눈을 뜬 것과도 같은 인식의 지평이 열린 대 사건입니다.

대학에 들어가서 배우게 되는 거의 모든 분야의 공학, 수학, 자연과학, 경제학 등에서 미분과 적분이 기본적인 도구로 사용됩니다.  이것의 이해를 하지 않고서는 한치도 앞으로 나갈 수 없습니다.

25장 : 방정식 근 찾기

학창시절 수학 공부하면서 지겹도록 방정식을 풀어 보았을 겁니다.

그런데 아십니까? 우리가 손으로 풀던 문제들은, 딱 손으로 풀 수 있는 정도의 계산량만 요구하는 "연습용" 문제일 뿐이라는 걸요.

실제 현실에서 부닥치는 여러가지 문제들을 방정식으로 모델링하고 이를 풀려고 하면 절대로 손으로 (혹은 대수적으로) 풀 수 없는 경우가 태반입니다.

객관식 문제라면 보기 몇개를 거꾸로 대입시켜 해결할 수 있을 것입니다만... 현실은 주관식이어서  대입해야 할 수는 거의 무한대에 가깝습니다.  이럴 때 필요한 것이 초당 몇백만 번을 계산할 수 있는 컴퓨터의 계산 능력입니다.

24장 : 행렬 (Matrix)


행렬(Matrix)는 행(Row)과 열(Column)로 구성되는 사각형의 격자(Array)에 숫자나 심볼을 배치한 것을 의미합니다.

행렬은 기하학(특히 컴퓨터 그래픽스)이나 통계학에서 시스템을 이루는 다차원의 독립 변수들을 한꺼번에 연산하기 위한 수학적 도구라 볼 수 있습니다.  간단히 말하면 여러 수치를 동일한 방법으로 연산하는 표현이자 도구입니다.

이런 이유로 행렬 또한 컴퓨터로 하는 수치해석의 주요 이슈이며, 매우 중요한 의미를 가집니다.  행렬에 대해서는 고등학교 수학 시간에 필요한 정도는 이미 배웁니다.  만일  기억이 잘 나지 않는다면 행렬에 대한 내용을 복습해 보는 것이 진행하는데 도움이 될 것입니다.

23장 : 다항식 (Polynomial)


이번장 부터는 수치해석(Numerical Analysis)의 기본적인 주제들을 살펴볼 겁니다.

수치해석은 컴퓨터가 가진 뛰어난 연산 능력을 활용하여 복잡한 수학적 문제들을 반복적인 방법으로 풀어내는 것입니다.  현실 세계에서 부닥치는 많은 수학적 문제들은 수치해석이 아니면 풀지 못하는 것들입니다.

그래서 수치해석은 공학, 기초 과학, 통계학 그리고 요즘 뜨고 있는 머신러닝, 빅 데이터 처리 등에 적극 활용되고 있습니다.  다소 수학적인 풀이가 있어 어렵게 느껴지지만, 증명하기 보다는 이해하고 활용하는데 촛점을 맞춘다면 넘지 못할 벽이 아닙니다.

22장 : 방향 그래프 (Directed Graph)

방향 그래프(Directed Graph)는 정점(Vertex)을 연결하는 간선(Edge)에 지금까지와는 달리 방향성을 부여한 것입니다.  그래서 간선을 화살표로 표시합니다.

이것의 의미는 정점 A에서 B로 갈 수는 있어도, B에서 A로는 갈 수 없는 상황을 모델링하는데 유용합니다.  도로를 모델링할 경우 일방통행로가 해당될 것이고, 공정을 모델링할 경우 비가역적(Irreversible) 변이가 이에 해당될 것입니다.

21장 : 가중 그래프 (Weighted Graph)


이번 장에서 배우는 가중 그래프(Weighted Graph)는 정점(Vertex)를 연결하는 간선(Edge)에 가중치를 부여한 것입니다.

예를 들어 정점을 도시라고 생각하고, 간선은 도시를 연결하는 도로라고 한다면, 간선에 매겨진 가중치는 이동하는데 걸리는 비용(시간, 통행료, 연료비 등)이라고 모델링할 수 있습니다.

이런 모델링이 자연스럽기 때문에 가중 그래프의 예로는 두 정점 간의 최소 비용 경로(최단 경로)를 찾는 것이 주요 문제가 됩니다.

자동차의 최단 경로를 안내하는 내비게이션도 도로를 가중 그래프로 모델링하고 그 안에서 최소 비용 경로를 찾는 것입니다.

이번 장에서 가중 그래프를 프로그램으로 표현하는 법, 그리고 최소 비용 신장 트리를 찾기 위한 Kruskal 알고리즘과 최단 경로를 찾기 위한 Dijkstra 알고리즘에 대해 알아볼 것입니다.

인기글