쉽게 배우는 알고리즘

귀납적 사고를 통한 문제 해결 기법 훈련

이 책은 알고리즘에 대한 지식을 기반으로 제대로 된 프로그래밍을 하는 이들뿐 아니라, 알고리즘 속에 깃든 여러 가지 생각하는 방법, 자료구조, 테크닉을 통해 체계적으로 생각하는 훈련을 하고자 하는 모든 이를 대상으로 한다. 알고리즘의 설계와 분석을 활용해 체계적으로 사고할 수 있는 빌딩 블록을 구축하여, 컴퓨터 및 관련 분야의 연구자 또는 개발자로서 갖춰야 할 지적 기반을 쌓을 수 있다. 3판에서는 알고리즘 표기를 더욱 명확한 형태로 변경하였고 전체 장에 걸쳐 수정 및 보강을 진행하였다. 특히 4장 정렬은 완전히 새로 쓰고 내용을 확장하였다. 또한 각 장에서 배운 내용을 문제와 해설을 통해 종합적으로 정리할 수 있도록 종합예제 코너를 신설하였다.

※ 본 도서는 대학 강의용 교재로 개발되었으므로 연습문제 해답은 제공하지 않습니다.

Chapter 01 알고리즘이란

01 알고리즘은 작업 과정의 묘사
02 알고리즘은 생각하는 방법의 훈련
03 알고리즘은 자료구조의 확장
Drift 알고리즘 단어의 유래: 알?콰리즈미

Chapter 02 알고리즘 설계와 분석의 기초

01 알고리즘 분석을 위한 기초 개념
1 알고리즘 분석의 필요성
2 알고리즘의 수행 시간
3 재귀(자기호출)와 귀납적 사고
4 알고리즘으로 해결할 수 있는 문제
02 점근적 표기
1 점근적 표기의 개념
2 Θ-표기
3 O-표기
4 Ω-표기
5 대표적인 점근적 표기의 직관적 이해
03 점근적 표기의 엄밀한 정의
1 O-표기
2 Ω-표기
3 Θ-표기
4 o-표기
5 ω-표기
6 직관적 이해
종합예제
요약
연습문제
Drift 에너지의 천재 크누스

Chapter 03 점화식과 알고리즘 복잡도 분석

01 점화식
02 점화식의 점근적 분석 방법
1 반복 대치
2 추정 후 증명
3 마스터 정리
종합예제
요약
연습문제
Drift 천재 알고리즘의 재현: 스트라센 알고리즘의 재고

Chapter 04 정렬

01 기초적인 정렬 알고리즘
1 선택 정렬
2 버블 정렬
3 삽입 정렬
02 고급 정렬 알고리즘
1 병합 정렬
2 퀵 정렬
3 힙 정렬
4 셸 정렬
03 비교 정렬 시간의 하한
04 특수 정렬 알고리즘
1 기수 정렬
2 계수 정렬
3 버킷 정렬
05 정렬 알고리즘 간 실제 성능 비교
종합예제
요약
연습문제
Drift 재귀와 관계 중심의 사고방식

Chapter 05 선택 알고리즘

01 평균 선형 시간 선택 알고리즘
02 최악의 경우에도 선형 시간을 보장하는 선택 알고리즘
종합예제
요약
연습문제
검색 트리

Chapter 06 검색 트리

01 레코드, 키의 정의 및 검색 트리
02 이진 검색 트리
1 이진 검색 트리의 검색
2 이진 검색 트리의 삽입
3 이진 검색 트리의 삭제
03 레드 블랙 트리
1 레드 블랙 트리의 삽입
2 레드 블랙 트리의 삭제
3 레드 블랙 트리의 작업 성능 분석
04 B-트리
1 B -트리의 검색
2 B -트리의 삽입
3 B -트리의 삭제
4 B -트리의 작업 성능 분석
05 다차원 검색 트리
1 KD -트리
2 KDB -트리
3 R -트리
4 그리드 파일
종합예제
요약
연습문제

Chapter 07 해시 테이블

01 해시 테이블: 검색 효율의 극단
02 해시 함수
1 나누기 방법
2 곱하기 방법
03 충돌 해결
1 체이닝
2 개방 주소 방법
04 해시 테이블의 검색 시간 분석
종합예제
요약
연습문제

Chapter 08 집합의 처리

01 연결 리스트를 이용한 집합의 처리
1 작업의 개요
2 수행 시간
02 트리를 이용한 집합의 처리
1 기본 원리
2 연산의 효율을 높이는 방법
종합예제
요약
연습문제
Drift 추상화와 은유

Chapter 09 동적 프로그래밍

01 어떤 문제를 동적 프로그래밍으로 푸는가
02 행렬 경로 문제
03 돌 놓기 문제
04 행렬 곱셈 순서 문제
05 최장 공통 부분 순서(LCS)
06 메모하기
1 탑다운 방식의 동적 프로그래밍
2 돌 놓기 문제의 메모하기 알고리즘
3 행렬 곱셈 순서 문제의 메모하기 알고리즘
종합예제
요약
연습문제
Drift 은유와 추상의 혁명, 트랜스포머 어텐션

Chapter 10 그래프

01 그래프
02 그래프의 표현
1 인접 행렬을 이용한 방법
2 인접 리스트를 이용한 방법
3 인접 배열과 인접 해시 테이블
03 너비 우선 탐색과 깊이 우선 탐색
04 최소 신장 트리
1 프림 알고리즘
2 크루스칼 알고리즘
3 안전성 정리
05 위상 정렬
06 최단 경로
1 다익스트라 알고리즘(음의 가중치를 허용하지 않는 경우)
2 벨만?포드 알고리즘(음의 가중치를 허용하는 경우)
3 모든 쌍 최단 경로 알고리즘
4 사이클이 없는 그래프의 최단 경로
07 강연결 요소
종합예제
요약
연습문제

Chapter 11 그리디 알고리즘

01 전형적인 그리디 알고리즘의 구조
02 그리디 알고리즘으로 최적해가 보장되지 않는 예
1 이진 트리의 최적합 경로 찾기
2 보따리 문제
3 동전 바꾸기
03 그리디 알고리즘으로 최적해가 보장되는 예
1 최소 신장 트리
2 회의실 배정 문제
3 그 밖의 예
04 매트로이드 : 그리디 알고리즘으로 최적해가 보장되는 공간 구조
1 매트로이드의 정의와 예
2 매트로이드의 확장과 포화
3 그리디 알고리즘으로 최적해를 보장하는 매트로이드 구조
4 문제 공간 탐색 관점에서 본 매트로이드
종합예제
요약
연습문제

Chapter 12 문자열 매칭

01 원시적 매칭
02 오토마타를 이용한 매칭
03 라빈-카프 알고리즘
04 KMP 알고리즘
05 보이어-무어 알고리즘
종합예제
요약
연습문제

Chapter 13 NP-완비

01 문제의 종류
02 Yes/No 문제와 최적화 문제
03 NP
04 다항식 시간 변환
05 NP-완비
06 NP-완비 문제들
07 NP-하드를 최적화 문제로 확장하기
★08 근사해 구하기
09 현상금 걸린 문제들
종합예제
요약
연습문제
Drift 비운의 천재 앨런 튜링과 정지 문제

Chapter 14 상태 공간 트리의 탐색

01 상태 공간 트리
02 백트래킹
1 미로 찾기 문제
2 색칠 문제
03 한정 분기
04 A* 알고리즘
1 최단 경로 찾기 문제
2 TSP
요약
연습문제
Drift 공간 탐색과 끌개
참고문헌
찾아보기

문병로

서울대 컴퓨터공학부 교수이자 ㈜옵투스투자자문 대표. 컴퓨터 알고리즘 최적화 전공자인 문병로 교수는 자신의 분야에서 여러 세계 기록들을 갈아치운 권위 있는 전문가다. 다양한 응용연구를 진행하던 문병로 교수는 2000년 최적화 이론의 가장 복잡한 응용 예로 주식시장 데이터에 본격적으로 관심을 갖게 되었고 실물 주식시장에서 놀라운 운용 수익률을 보이고 있다.

기존의 금융 전문가와는 전혀 다른 배경으로 주식시장에 진입한 그는‘한국판 제임스 사이먼스’로 불린다. 제임스 사이먼스는 대표적인 글로벌 헤지펀드 회사인 르네상스 테크놀로지스의 설립자이자 회장이다. 금융 전공자가 아닌 사이먼스는 MIT 수학 박사이며 뉴욕주립대에서 수학과 학과장을 지냈고 베블렌상을 받은 수학 천재다. 그의 메달리온펀드는 워런 버핏을 압도하는 수익률을 올려 왔다. 문병로 교수를 제임스 사이먼스에 견주는 것은 그가 학문적 공학기술을 바탕으로 한 국내 최초의 알고리즘 트레이딩 시스템을 개발,실제로 놀라운 성과를 올리고 있기 때문이다.

루머와 잡음투성이인 시장에서 투자자가 이익을 내기 위해서는, 수치와 확률에 근거한 영리한 접근이 필요하다. 하지만 공간의 방대함으로 인해, 이론 무장이 되지 않은 컴퓨터 프로그램이나 개인이 원하는 솔루션을 찾아내는 건 불가능하다. 문병로 교수는 ‘메트릭 스튜디오’라 부르는 그의 연구 공간에서 최첨단 기법을 이용하여 가장 매력적인 포트폴리오와 투자전략을 도출하고 있다.
금융시장은 사람 주도형 투자에서 컴퓨터 주도형 투자로 패러다임 전환이 이루어지고 있다. 향후 금융시장은 사람이 아닌 기계들, 알고리즘 간의 전쟁터가 될 것이다. 시장은 사람들의 일반적인 생각보다 훨씬 위험하다. 문병로 교수의 최적화 알고리즘은 시장의 위태롭고 무한한 다차원 공간을 돌아다니는 탁월한 교통수단과 같다. 그의 높은 수익률은 여기에 기반한다.

실제로 그는 2009년 2월부터 5년간 자산운용 수익률 222%를 기록하여 KOSPI 상승률 65% 대비 157% 포인트 높은 성과를 냈다. 연도별 기준으로 운용 수익률이 마이너스를 보인 때가 한 번도 없었으며 매년 KOSPI 대비 큰 폭의 초과 수익을 냈다. 워런 버핏도 3년에 한 번꼴로 시장에 졌다는 것을 감안하면 이것은 대단한 결과다.

문병로 교수는 세계 대회에서 우승한 최적화 기술을 1,700여 국내 전 종목에 적용하는 것은 물론, 의도적으로 자신이 가장 잘하는 분야 중심으로 관심을 좁혀 트레이딩 시스템을 완성해 가고있고, 스스로 진화를 거듭하고 있으며, 최적화 기법에 의한 세계 최고의 알고리즘 트레이딩 회사를 꿈꾸고 있다.

문병로 교수는 주식시장의 궁극적 추상화 수준이 10층이라면, 시장의 플레이어들은 대부분 1층 수준에 있고 자신의 시스템은 5, 6층 수준에 있다고 말한다. 이 책은 시장의 상식이 되어야 하지만 전혀 그렇지 못한 개념이나 기술들을 2층 정도의 수준에서 설명한다.

저서 『문병로 교수의 메트릭 스튜디오』는 투자 지침서이자 철학서다. 건강한 투자를 위해 일반 투자자와 전문 투자자 양쪽을 염두고 두고 집필해 이 책으로 독자들이 새로운 차원의 투자 근육을 형성할 수 있도록 안내한다. 그 밖의 저서로는 『IT CookBook, 쉽게 배우는 알고리즘』, 공저로는 『전산학개론』, 역서로 『Introduction to Algorithms』가 있다. 국제 저널과 학술대회에 120여 편의 논문을 발표했다.

Publication Date	2024/01/03
Pages/Weight/Size	18823522mm
ISBN	9791156640103
Categories	IT 모바일 > 컴퓨터 공학