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

저자 : 주우석 약력 서울공대 전자공학과 학사 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) 이공계 논문 작성법(부크크, 2022)

Part I. 자료구조 요약 1장. 리스트, 스택, 큐 1.1 배열로 구현한 리스트 1.2 연결 리스트로 구현한 리스트 1.3 스택 구현과 응용 1.4 스택과 깊이우선 탐색 1.5 큐 구현과 응용 1.6 큐와 너비우선 탐색 1.7 데크 1.8 연습 과제 2장. 2진 트리와 우선순위 큐 2.1 2진 트리와 순회 2.2 우선순위 큐 2.3 2진 힙과 힙 정렬 2.4 이항 힙과 피보나치 힙 2.5 연습 과제 Part II. 알고리즘과 효율 3장. 알고리즘과 효율 분석 3.1 알고리즘의 타당성 3.2 효율 분석 도구 3.3 재귀 알고리즘의 효율 3.4 재귀 트리와 마스터 정리 3.5 재귀호출과 반복문 3.6 상각 복잡도 3.7 연습 과제 4장. 정렬 알고리즘 4.1 기본적 정렬 4.2 합병 정렬과 퀵 정렬 4.3 카운팅 정렬과 버킷 정렬 4.4 기수 정렬 4.5 외부 정렬 4.6 연습 과제 5장. 탐색 알고리즘 5.1 2진 탐색트리 5.2 AVL 트리와 스플레이 트리 5.3 2-3 트리와 2-3-4 트리 5.4 레드 블랙 트리 5.5 B 트리 5.6 기수 탐색트리 5.7 해시 5.8 연습 과제 6장. 그래프 알고리즘 6.1 너비우선 탐색과 깊이우선 탐색 6.2 위상 정렬 6.3 연결 그래프 6.4 배타적 집합과 유니언 파인드 6.5 연습 과제 Part III. 알고리즘 설계 7장. 분할정복 기법 7.1 수학적 귀납법 7.2 유명인사 찾기 7.3 최대 부분배열 문제 7.4 최 근접 쌍 찾기 7.5 연습 과제 8장. 탐욕 기법 8.1 부분 배낭 문제 8.2 행사 선택 문제 8.3 거스름돈 문제 I 8.4 최대 지연 최소화 8.5 방 배정 문제 8.6 허프만 코딩 8.7 다이익스트라 알고리즘 8.8 최소 신장트리 8.9 컨벡스 헐 문제 8.10 안정된 결혼 문제 8.11 선형 계획법 8.12 연습 과제 9장. 백트래킹 기법과 한정 분기 기법 9.1 문자 순열 9.2 거스름돈 문제 II 9.3 8 퀸 문제 9.4 그래프 컬러링 문제 9.5 제로 원 배낭 문제 I 9.6 제로 원 배낭 문제 II 9.7 거스름돈 문제 III 9.8 할당 문제와 헝가리 법 9.9 연습 과제 10장. 동적 프로그래밍 기법 10.1 피보나치 수열 10.2 거스름돈 문제 IV 10.3 제로 원 배낭 문제 III 10.4 최대 연속 부분수열 10.5 최장 공통 부분열 10.6 최소 편집 거리 10.7 최장 증가 부분수열 10.8 행렬의 연속 곱셈 10.9 최단 경로 문제 10.10 부분집합 합계 문제 10.11 균형 분할 문제 10.12 연습 과제 11장. 랜덤, 근사, 휴리스틱, 유전자 기법 11.1 랜덤 알고리즘 11.2 근사 알고리즘 11.3 휴리스틱 알고리즘 11.4 유전자 알고리즘 11.5 연습 과제 12장. 주제별 알고리즘 12.1 문자열 탐색 12.2 난수 생성기 12.3 네트워크 플로우 12.4 이분 매칭 12.5 연습 과제 Part IV. 알고리즘의 한계 13장. 알고리즘 문제의 분류 13.1 P 문제와 NP 문제 13.2 NPC 문제 13.3 NP-Hard 문제 13.4 다항 시간 환원 13.5 공개키 암호화 13.6 RSA의 타당성 13.7 양자 컴퓨터 13.8 연습 과제 14장. 튜어링 머신 14.1 튜어링 머신 14.2 계산 가능성과 멈춤 문제 14.3 결정 불가능 문제 14.4 명제 논리와 괴델의 불완전성 이론 14.5 연습 과제 참고문헌 색인 참고자료 URL