알고리즘은 오래 동안 학부 4학년 선택 과목으로 다루어져 왔다. 그러나 언제부턴가 이 과목이 거의 모든 대학에서 3학년 필수 과목으로 바뀌게 되었고, 여기에는 대학 교육 협의회의 영향이 컸던 것 같다. 과목 내용의 중요성으로 보아 필수 과목으로 바뀌게 된 데에는 충분히 수긍이 간다. 그러나 4학년 과목에서 3학년 과목으로 내려온 것은 조금 문제 소지가 있다. 물론 알고리즘을 먼저 이해해야만 그 이후에, 요즘 이슈가 되고 있는 인공 지능이나 컴퓨터 보안을 들을 수 있지만, 그렇게 되면 이 과목을 3학년 수준에서 이해할 수 있는 과목으로 난이도를 조절해야하기 때문이다.
문제 해결을 위한 방법이 바로 알고리즘이다. 그러나 방법을 이해하는데 그치면 초급 수준이다. 어떤 방법이 더 나은지에 관한 것이 효율이다. 일반적인 효율 분석은 물론 상각 복잡도에 의한 효율 분석까지 가할 수 있어야 중급 수준에 이른다. 나아가 알고리즘이 옳은지를 묻는 타당성 증명도 놓쳐서는 안 된다. 논리 전개나 귀납법, 귀류법을 통해 타당성을 증명할 수 있어야 비로소 고급 수준에 이른다. 3 박자다. 방법과 효율과 타당성이다.
알고리즘 관련 서적은 외형 면에서 볼 때 두 가지 부류로 나눌 수 있다. 첫째가 코딩 위주의 책이다. 그러나 알고리즘에서 다루어야 할 주제는 너무나도 많다. 목적을 코딩 그 자체에 둔다면 책 한 권에서 다룰 수 있는 주제는 그리 많지 않다. 제한된 지면 대부분을 소스 코드가 차지하기 때문이다. 둘째는 이론 위주의 책으로서 이론 설명과 함께 복잡한 수식을 전개하는데 치중할 때가 많다. 물론 이렇게 함으로써 상대적으로 많은 주제를 다룰 수 있지만 이 역시 문제가 될 수 있다. 지면 대부분이 수식으로 채워지면 독자 입장에서는 다가가기 쉽지 않기 때문이다.
이 책은 이론 위주의 책이지만, 수식 대신 유사 코드를 사용하여 주요 논리를 설명하고자 한다. 제한된 지면에 다양한 주제를 폭넓게 그리고 쉽게 설명하기 위해서다. 수식을 완전히 피할 수는 없다. 따라서 수식이 필요한 경우 가급적 단순한 형태로 나타내기로 한다.
알고리즘 관련 서적은 내용 면에서 볼 때에도 두 가지 부류로 나누어 볼 수 있다. 첫째는 자료구조에서 시작하여, 이른바 고급 자료구조라 불리는 균형 탐색트리까지만 다루는 부류다. 물론 난이도를 낮추고자 한다면 이러한 책도 의미는 있다. 그러나 이러한 내용을 알고리즘이라 부르기에는 미흡하다. 둘째는 자료구조나 고급 자료구조를 아예 생략하고 곧바로 알고리즘에서 시작하여 기초적인 계산이론까지 커버하는 부류다.
이 책은 자료구조, 고급 자료구조, 알고리즘, 기초 계산이론까지를 포괄적으로 다룬다. 물론 주안점은 알고리즘에 있다. 그러나 그 이전에 자료구조나 고급 자료구조를 간단하게 요약해 두는 것이 그 다음 파트인 알고리즘을 이해하는데 도움이 된다. 나아가 적절한 수준에서 기초적인 계산이론을 설명하고자 한다. 계산이론은 일반적으로 대학원에서 가르치는 과목이지만 알고리즘과의 연관된 부분을 이해하는 것은 큰 의미가 있다. 현업에서 제기되는 다양한 알고리즘 문제에 대처하려면, 보다 넓은 관점에서 문제를 바라볼 수 있어야하기 때문이다.
1부인 자료구조 요약에서는 리스트, 스택, 큐, 2진 트리, 우선순위 큐 등에 대해 핵심적인 내용을 요약하기로 한다. 2부 알고리즘과 효율에서는 효율 분석을 위한 다양한 방법을 설명하고 정렬, 탐색, 그래프 등의 주제를 대상으로 알고리즘의 효율을 분석하기로 한다. 3부 알고리즘 설계에서는 억지 기법, 분할 정복 기법, 탐욕 기법, 백트래킹 기법, 분기 한정 기법, 동적 프로그래밍 기법, 랜덤 알고리즘, 근사 알고리즘, 휴리스틱 알고리즘, 유전자 알고리즘 등 열 가지 설계 기법을 설명하고 예시하기로 한다. 4부 알고리즘의 한계에서는 컴퓨터 계산 능력의 한계를 바탕으로 문제를 분류하는 방법을 설명한다. 또, 컴퓨터로 풀 수 있는 문제가 어디까지인지를 묻는 계산 가능성에 대해 설명하기로 한다.
이 책의 가장 큰 특징은 알고리즘 설계 기법 상의 차이점을 분명하게 설명한다는 점이다. 제로 원 배낭 문제나 거스름 돈 문제 등 동일한 주제에 대해 탐욕 기법, 백트래킹 및 분기 한정 기법, 동적 프로그래밍 기법 등 다양한 방법으로 풀어 봄으로써 알고리즘 설계 방법의 차이점이 분명해진다.
타당성 분석에도 많은 부분을 할애한다. 이 분야의 대부분 서적이 단순히 이런 저런 방법으로 풀 수 있다고 말하고 끝내는 경우가 많다. 물론 그렇게 함으로써 난이도는 낮아진다. 그러나 학습자 입장에서 볼 때, 그러한 방법은 별 도움이 되지 않는다. 알고리즘이 타당한 이유를 설명해야 더욱 깊은 이해가 될 수 있고 그래야 코딩 면접이나 알고리즘 경진대회에 대처하는 창의성이 생긴다. 알고리즘 효율 분석에 있어서도 외국 대학에서 특히 중시하는 상각 복잡도에 관해 구체적으로 설명하고 다양한 주제를 통해 분석 과정을 예시한 점이 특징이다.
사실상 난이도라는 말은 상대적이다. 이해하고자 하는 사람이 집중한 상태에서 조리 있게 설명한다면 이해 안 될 것은 거의 없다. 특히 대부분 교수들이 이 과목은 수업 직전에 강의할 내용을 반드시 다시 한 번 상기한 다음에 수업에 들어간다. 잊어버리기 쉬운, 상당히 까다로운 논리를 전달해야 할 때가 많기 때문이다. 이 책은 700 여개의 그림 및 표를 통해 때로는 직관적으로, 때로는 논리적으로, 다양한 알고리즘을 이해할 수 있도록 했다. 나아가 250 여개의 연습 문제를 통해 응용 방법을 고민해 볼 수 있도록 했다.
교수자 입장에서 보자면 장별로 주제 수가 차이가 있고 또, 난이도 차이도 있을 수 있다. 특히 1부 자료구조 요약에 너무 많은 시간을 할애하면 정작 중요한 이후 주제를 강의할 시간이 모자라므로, 1부는 1-2주 정도에 끝내고 과제물로 대체하는 것도 좋다. 모든 주제를 강의하기에는 너무 많은 시간이 걸릴 것 같으면 일부 주제만 선택적으로 강의하는 방법도 생각해 볼 수 있다. 교수자의 일방적 강의가 아니라 팀별 발표 형태로 진행함으로써 수강생의 자발적인 참여를 유도할 수도 있다.
코딩의 중요성을 강조하려면 본문의 예제나 연습 과제 일부를 코딩 형태의 과제로 바꾸는 방법을 생각해 볼 수 있다. 생각하는데 많은 시간을 요할 뿐, 실제로 코딩이 길어지는 경우는 드물다. 또, 대부분의 알고리즘을 이미 본문을 통해 유사 코드 형태로 제공했기 때문에 그리 어렵지 않은 과제가 될 수 있다. C++나 Java, Python 등 어떤 언어든 사용할 수 있으며, 필요시 라이브러리를 호출로 더욱 간단한 코딩이 되도록 요구할 수도 있다.
물론 학습 방식에 따라서 난이도를 조절할 필요는 있다. 예를 들어 이항 힙, 피보나치 힙, 양자 컴퓨터 이론 등은 약간의 난이도가 있으므로 필요하다면 건너 뛸 수도 있다. 또, 수식을 사용한 증명 부분도 불필요해 보일 경우 결론만 이해해도 무방할 것으로 생각된다. 컴퓨터 계산 능력의 한계를 설명한 튜어링 머신 부분도 필요하다면 개념만 이해해도 족할 것으로 생각된다. 다시 말해, 이 책의 모든 부분이 선택적이다.
샘플 피피티 자료는 저자의 네이버 블로그를 참조하면 된다. 피피티의 경우 어떤 주제를 얼마나 상세하게 설명해야 할 것인가에 따라서 올려 진 자료를 수정하고 보완하여 사용하는 것이 바람직하다. 연습 과제에 대해서는 조금이라도 어려울 것으로 생각되면 힌트를 제공했기 때문에 학습자 스스로 해결하는데 별 어려움은 없을 것으로 보인다. 샘플 답안도 올려 져 있으나 참고 자료일 뿐이므로 정답 여부는 학습자의 판단에 맡기기로 한다.
이십여 년을 대학에서 알고리즘 과목을 가르치면서도 적절해 보이는 교재가 없어 수시로 교재를 바꾸어 가면서 슬라이드 위주로 강의해 왔던 것 같다. 물론 요점만 대충 파악하는 데에는 슬라이드만큼 좋은 것도 없다. 그러나 그것은 결국 일종의 요약일 뿐이다. 구체성이나 이면 논리가 결여되어 있기 때문에 깊이 있는 학습을 하는 데에는 크게 도움이 되지 않는다. 이런 점에서 그간의 수강생들에게는 미안한 마음이 남지만 이 책을 통해서나마 일말의 보상이 되었으면 한다.
특히 흑백 버전의 종이책 대신 이번에 새로이 발행하게 된 컬러 버전의 전자책으로 인해 독자의 이해도가 대폭 향상되리라 믿는다.
책이 나올 때까지 알게 모르게 도움을 주신 주위의 많은 분들께 감사를 드린다. 표지 디자인과 삽화를 제공한 주민지 님과 정정애 님에게도 감사드린다. 강의 도중 이런 저런 질문을 통해 이해하기 어려운 부분이 무엇인지를 깨닫게 해 준 수강생들에게도 감사드린다. 하나님 은혜로 오늘이 있기까지 키워주신 사랑하는 부모님과 사랑하는 가족들 모두에게 감사드린다.
약력
서울공대 전자공학과 학사
University of Florida 컴퓨터공학 석사
University of Florida 컴퓨터공학 박사
University of Florida Postdoctoral Researcher
University of California Irvine Visiting Professor
IBM Korea, 데이콤 정보통신연구소
현) 명지대학교 공과대학 컴퓨터공학과 명예교수
저서
전공자를 위한 C 언어 프로그래밍(한빛 아카데미, 2018)
C, C++로 배우는 자료구조론(한빛 아카데미, 2015)
openGL로 배우는 3차원 컴퓨터 그래픽스(한빛 아카데미, 2013)
이공계 논문 작성법(부크크: 2022, 유페이퍼: 2024)
논술 글쓰기 원리(부크크: 2022, 유페이퍼: 2024)
디자인, 일러스트: 주민지, 정정애
글꼴: KoPub 서체, 나눔 글꼴