자바로 쉽게 배우는 알고리즘

알고리즘은 컴퓨터 과학의 기본일 뿐만 아니라 공학, 자연 과학과 경영학 등과 같은 인접 학문 분야에서도 아주 중요하다. 알고리즘 개발은 우리가 매일 마주치는 도전 과제들의 더 나은 해결 방법을 찾는 것을 의미한다. 최근에 대학 교육의 주요 목표중의 하나가 학생들의 문제해결 능력을 배양하는 것이다. 이 목표를 이루기 위해 알고리즘이 문제를 해결하기 위한 특유의 전략을 제시해 주기 때문에 알고리즘 개발 능력을 배우는 것이 꼭 필요하다.



지금까지 많은 알고리즘 책들이 출판되었다. 최근 학생들은 암기 위주의 교육을 주로 받아 논리적 사고 능력이 부족하여 알고리즘을 이해하는 능력이 현저히 떨어지는 것처럼 보인다. 따라서 보다 쉽게 쓰여진 알고리즘 책에 대한 수요가 늘고 있다. 특히 학생들이 문제 해결을 잘 하기 위해서 필수적인 알고리즘 작성 과정에 초점을 맞춘 책은 적어도 국내에는 거의 나오지 않았다. 또한 본인의 10여년의 강의 경험에 의하면 학생들은 알고리즘을 보고 프로그램을 작성하는 것도 어려워함을 알 수 있었다. 그래서 학생들이 쉽게 이해할 수 있고 알고리즘뿐만이 아니라 알고리즘에 따라 작성된 완전한 자바 프로그램을 제시하는 책을 쓰게 되었다.



이 책은 알고리즘을 배우고자 하는 학생들이 꼭 알아야 하는 아주 중요한 고전적인 알고리즘들을 다룬다. 이 알고리즘들을 문제 유형보다는 알고리즘 설계 기법들을 중심으로 구성하여 제시하였다. 알고리즘 설계 기법은 일반적인 문제 해결 도구로 여겨진다. 응용 분야가 전통적인 컴퓨팅과 수학적 문제들로 한정되지 않는다. 더욱 더 많은 알고리즘 응용 분야들이 등장하고 있다. 이러한 구성이 알고리즘의 설계 및 분석에 관한 기초 과목에 더 적절하다. 무엇보다 중요한 것은 독자가 알고리즘을 개발할 수 있다는 자신감을 가지게 하는 것이다. 이를 위해 본 교재에서는 매 장의 주제마다 비교적 이해하기 쉽고 중요한 여러 문제들에 대한 알고리즘들을 제공한다. 대부분의 경우에 한 문제를 해결하는 여러 전략들이 있다는 것을 보여 주기 위해 여러 설계 기법들을 사용하여 해결하는 알고리즘들을 제시한다.



이 책은 알고리즘을 쉽게 배울 수 있도록 쓰여 졌다. 먼저 주어진 문제를 해결하기 위한 핵심 아이디어/전략을 제시한다. 다음으로 제시된 아이디어/전략을 작은 크기의 문제 사례에 적용하여 해결하는 과정을 단계별로 보여준다. 그리고 나서 이 과정을 일반화한 알고리즘을 제시하고 효율성을 분석한다. 마지막으로 알고리즘을 자바 프로그램으로 구현하고 실행 결과를 보여준다. 특히 알고리즘들을 쉽게 이해할 수 있도록 비교적 많은 삽화나 그림들을 활용한다.



이 책의 내용을 이해하기 위해서 이산 수학, 자료 구조와 자바 프로그래밍을 알아야 한다. 정렬과 기본적인 그래프 알고리즘에 대해 잘 알고 있는 독자들은 3장과 4장을 건너 뛰거나 빠르게 읽기 바란다.



본인이 텍사스 대학의 컴퓨터과학과 대학원 재학 시 알고리즘 과목을 강의하셨던 Bitner 박사님께 진심으로 감사드린다. 그 교수님은 알고리즘의 작성 과정을 이해하기 쉽게 해 주셨고 알고리즘에 대한 관심과 흥미를 불러 일으켜 주셨다. 이 책의 일부 내용이 그 교수님의 강의에 바탕을 두고 있음을 밝힌다. 이 책의 많은 부분에 직간접적으로 기여한 지난 10여년 동안 본인의 부족한 알고리즘 강의를 수강한 수많은 학생들에 진심 어린 고마움을 표한다.



이 책이 출판되기까지 많은 격려와 도움을 주신 생능출판사의 김승기 사장님과 편집부 직원들에게 깊은 감사를 드린다. 특히 이 책의 초안에 대해 꼼꼼히 읽은 후 이 책의 내용이 쉽게 전달될 수 있도록 전문적인 검토 의견을 주신 한 분의 소프트웨어 개발자와 두 분의 교수님들에게 진심으로 감사드린다. 마지막으로 자식들의 교육에 애쓰셨던 돌아가신 아버지께 진정한 감사를 드리면서 이 책을 바친다. 평생 자식들을 위해 헌신하시고 힘들 때마다 적극적으로 도움을 주셨던 어머니께 깊은 감사를 표한다. 또한 이 책이 나오기까지 많은 관심과 격려를 아끼지 않은 사랑하는 아내, 아들과 며느리에게도 진심으로 감사를 표한다. 특별히 이 책 원고의 문서 작업을 도와준 사랑하는 딸에게도 고마움을 표한다.

1장 알고리즘 소개

1.1 알고리즘이란?

1.2 알고리즘적 문제 해결 과정

1.3 알고리즘의 표현

1.4 알고리즘의 분류



2장 알고리즘의 효율성 분석

2.1 알고리즘 분석 체계

2.2 시간 복잡도

2.3 복잡도의 점근적 표기

2.4 비재귀 알고리즘의 효율성 분석

2.5 재귀 알고리즘의 효율성 분석



3장 정렬 알고리즘

3.1 선택 정렬

3.2 삽입 정렬 9

3.3 힙 정렬



4장 기본적인 그래프 알고리즘

4.1 그래프의 표현

4.2 깊이 우선 탐색

4.3 너비 우선 탐색

4.4 위상 정렬



5장 분할 정복

5.1 최댓값과 최솟값 찾기

5.2 합병 정렬

5.3 빠른 정렬

5.4 선택

5.5 분할 정복이 부적절한 경우



6장 동적 계획

6.1 막대 자르기

6.2 연속 행렬 곱셈

6.3 모든 쌍 최단 경로 찾기

6.4 배낭 채우기



7장 탐욕 기법

7.1 거스름돈 주기

7.2 최소 비용 신장 트리 찾기

7.3 단일 출발점 최단 경로 찾기

7.4 배낭 빈틈없이 채우기



8장 NP - 완전

8.1 문제의 분류

8.2 결정 문제와 최적화 문제

8.3 NP

8.4 NP-완전

8.5 NP-완전 문제



9장 되추적

9.1 상태공간트리 3 7

9.2 순열 생성

9.3 해밀토니안 회로 찾기

9.4 그래프 색칠하기



10장 분기한정

10.1 최선 우선 탐색

10.2 배낭 채우기

10.3 일 배정



11장 근사 알고리즘

11.1 정점 커버 찾기

11.2 외판원 문제



참고 문헌

찾아보기

이충기 1979년 서울대학교 계산통계학과(이학사)

1981년 서울대학교 계산통계학과(이학석사)

1993년 조지아공과대학교 전산과학대학(전산학박사)

1994 ~ 1996 한국전산원 전산망 표준본부 선임연구원

2000 ~ 2001 명지대학교 정보통신교육연구센터 센터장

2003 ~ 2004 조지아공과대학교 전산과학대학 방문교수

2010 ~ 2011 퍼듀대학교 컴퓨터과학과 방문교수

1996 ~ 현재 명지대학교 컴퓨터공학과 교수



관심분야 | 모바일 컴퓨팅, 공학 교육

E - mail | cklee@mju.ac.kr