알고리즘 문제 해결 전략

알고리즘을 공부하면서 문제에 대한 암기보다, 알고리즘 자체에 대한 개념을 학습하기 위해 읽기 시작한 책이다.

머리말

컴퓨터 관련 학과를 졸업하고 프로그래밍에 자신없어하는 사람은 매우 많다.

프로그래밍이 어렵다거나 교육의 문제라고 치부해도 잘하는 사람과 못하는 사람의 생산성 차이가 스무배 가까이 나오기도 한다.

이런 현상의 가장 근본적인 이유는 대부분 컴퓨터 과학 교육 과정이 프로그래밍 기술과 지식을 가르칠 뿐, 그것을 응용할 수 있는 능력을 주지 못하기 때문이다.

글을 기계적으로 해석할 수는 있어도, 시를 감상하거나 좋은 글을 직접 쓰지는 못한다.

즉, 알고리즘을 배운 뒤 연습 문제는 풀 수 있어도, 문제를 해결하기 위한 새로운 무언가를 고안할 수는 없는 개발자가 되는 것이다.

이런 비극이 일어난 가장 큰 원인은 현대의 컴퓨터 과학 교육이 실제 학문이 발전하는 방향의 반대 순서로 이루어져 있기 때문이다.

처음부터 완전한 체계를 갖추고 발전하는 학문은 없으므로, 발전 과정에서 학자들은 모두 어둠속에서 직관에 의존해 해매게 된다.(삽질)

이에 따른 시행착오가 쌓이면서 학문의 기초를 세우고 나면, 자연스럽게 학문의 뼈대가 되는 공리들과 법칙들을 만들고 학문의 체계를 정리해 나가게 된다.

반면 대부분의 교과서에서는 발전 과정의 최종 결과물인 복잡한 개념과 도구를 먼저 제시하고, 그 개념의 이론에 대해 설명한 뒤, 곧장 연습 문제를 풀도록 한다.

이 과정에서 이론을 만들기 위해 필요했던 직관이나 경험적 요소는 완전히 배제된다.

그래프의 최단 거리 알고리즘은 크게 한 정점에서부터 모든 정점까지의 최단 거리를 구하는 단일 시작점 알고리즘과 모든 정점 쌍 간의 최단 거리를 구하는 모든 쌍 최단 경로 알고리즘으로 나뉜다. 단일 시작점 알고리즘의 대표적인 것으로 다익스트라 알고리즘이 있다. 의사 코드는 이렇다. 이 그래프에 대해서 알고리즘을 실행해 보자. 이 간선, 이 간선, 이 간선 순으로 완화가 이루어지므로 최단 거리는 이렇게 된다. 자, 이제 시간 복잡도를 분석해보자.

과연 이 수업에서 학생이 다익스트라 알고리즘이 생겨난 배경과 이 알고리즘을 설계하는 데 필요했던 결정적 통찰을 얻을 수 있을까?

이런 교육형태는 학문 발전의 결과물에 대한 체계적인 지식을 학생에게 주입하는 데 좋을지 몰라도, 문제의 답을 스스로 고안할 수 있는 학생을 기르기에는 턱없이 부족하다.

이런 경험과 깨달음을 얻기 위한 좋은 통로가 바로 프로그래밍 대회이다.

대회는 알고리즘 설계 기법과 자료 구조를 직관적으로 이해하고, 나아가 알고리즘 문제 해결 능력을 키울 수 있도록 구성되어 있다.

이 책은 실제 대회 문제를 가지고 유형을 분석하고, 기법을 만들기 위한 과정과 배경을 자세하게 다루었다.

댓글남기기