- 현재 위치
- home > 컴퓨터·ICT·어학 > 컴퓨터·IT 도서 > 컴퓨터공학 > 문제 해결력을 높이는 알고리즘과 자료 구조[길벗]
;)
알고리즘 문제의 답을 스스로 생각하는, 코딩 테스트와 프로그래밍 경진대회 전 필독서!
이 책은 알고리즘 입문서이자 응용력, 문제 해결력을 높여주는 알고리즘 활용서다. 궁극적으로 알고리즘을 잘 다룰 수 있게 실력을 키우는 것을 목표로 한다. 우선 알고리즘에 대해 전혀 모르는 사람이 알고리즘의 전반적인 모습을 체계적으로 인식하고, 필요한 기초 개념과 기본적인 알고리즘을 배울 수 있다. 알고리즘을 설명할 때는 유명한 알고리즘을 단순히 소개하는 것이 아니라 어떻게 설계되었는지 설계 기법과 설계 과정, 응용 방법과 사례도 함께 설명한다. 또한, 다양한 상황에서 알고리즘을 사용해 문제를 해결할 수 있도록 알고리즘을 설계할 때 필요한 지식과 접근법을 설명한다. 목표는 알고리즘의 동작을 구체적으로 이해하고 실제 문제 해결에 사용하는 것이며, 알고리즘을 단순히 아는 것을 넘어서 잘 다루는 것이다. 우리는 알고리즘을 사용해 주어진 문제를 잘 풀기도 하고, 내가 직접 설계도 하고, 더 효율적으로 개선할 수도 있어야 한다. 이 책은 이를 위해 필요한 방법과 지식을 학습한다. ?
이 책은 알고리즘 입문서이자 응용력, 문제 해결력을 높여주는 알고리즘 활용서다. 궁극적으로 알고리즘을 잘 다룰 수 있게 실력을 키우는 것을 목표로 한다. 우선 알고리즘에 대해 전혀 모르는 사람이 알고리즘의 전반적인 모습을 체계적으로 인식하고, 필요한 기초 개념과 기본적인 알고리즘을 배울 수 있다. 알고리즘을 설명할 때는 유명한 알고리즘을 단순히 소개하는 것이 아니라 어떻게 설계되었는지 설계 기법과 설계 과정, 응용 방법과 사례도 함께 설명한다. 또한, 다양한 상황에서 알고리즘을 사용해 문제를 해결할 수 있도록 알고리즘을 설계할 때 필요한 지식과 접근법을 설명한다. 목표는 알고리즘의 동작을 구체적으로 이해하고 실제 문제 해결에 사용하는 것이며, 알고리즘을 단순히 아는 것을 넘어서 잘 다루는 것이다. 우리는 알고리즘을 사용해 주어진 문제를 잘 풀기도 하고, 내가 직접 설계도 하고, 더 효율적으로 개선할 수도 있어야 한다. 이 책은 이를 위해 필요한 방법과 지식을 학습한다. ?
저자: 오츠키 켄스케 (지은이), 서수환 (옮긴이), 아키바 타쿠야 (감수)
1장 알고리즘이란?
1.1 알고리즘이란 무엇인가?
1.2 알고리즘 예제(1): 깊이 우선 탐색과 너비 우선 탐색
1.2.1 빈 칸 채우기 퍼즐로 배우는 깊이 우선 탐색
1.2.2 미로로 배우는 너비 우선 탐색
1.3 알고리즘 예제(2): 매칭
1.4 알고리즘 서술 방법
1.5 알고리즘을 배우는 의미
1.6 연습 문제
2장 복잡도와 빅오 표기법
2.1 복잡도란?
2.2 복잡도와 빅오 표기법
2.2.1 복잡도 빅오 표기법 생각해 보기
2.2.2 코드 2-1의 복잡도
2.2.3 코드 2-2의 복잡도
2.2.4 실제로 복잡도 구해 보기
2.2.5 복잡도를 빅오 표기법으로 표시하는 이유
2.3 복잡도를 구하는 예(1): 짝수 나열
2.4 복잡도를 구하는 예(2): 최근접 점쌍 문제
2.5 복잡도 사용법
2.6 복잡도 관련 주의 사항
2.6.1 시간 복잡도와 공간 복잡도
2.6.2 최악 시간 복잡도와 평균 시간 복잡도
2.7 란다우 빅오 표기법 상세 설명(*)
2.7.1 란다우 빅오 표기법
2.7.2 오메가 표기법
2.7.3 세타 표기법
2.8 마무리
2.9 연습 문제
3장 설계기법(1): 전체 탐색
3.1 전체 탐색을 배우는 의미
3.2 전체 탐색(1): 선형 탐색법
3.3 선형 탐색법의 응용
3.3.1 조건을 만족하는 위치 파악 가능
3.3.2 최솟값 구하기
3.4 전체 탐색(2): 쌍 전체 탐색
3.5 전체 탐색(3): 조합 전체 탐색(*)
3.6 정리
3.7 연습 문제
4장 설계기법(2): 재귀와 분할 정복법
4.1 재귀란 무엇인가?
4.2 재귀 사용 예(1): 유클리드 호제법
4.3 재귀 사용 예(2): 피보나치 수열
4.4 메모이제이션 동적 계획법
4.5 재귀 사용 예(3): 재귀 함수를 사용한 전체 탐색
4.5.1 부분합 문제
4.5.2 부분합 문제에 대한 재귀적 전체 탐색 복잡도(*)
4.5.3 부분합 문제에 대한 메모이제이션(*)
4.6 분할 정복법
4.7 정리
4.8 연습 문제
5장 설계 기법(3): 동적 계획법
5.1 동적 계획법이란?
5.2 동적 계획법 예제
5.3 동적 계획법 관련 개념도
5.3.1 완화
5.3.2 끌기 전이 형식과 밀기 전이 형식
5.3.3 끌기 전이 형식과 밀기 전이 형식 비교
5.3.4 전체 탐색 메모이제이션을 이용한 동적 계획법
5.4 동적 계획법 예제(1): 냅색 문제
5.5 동적 계획법 예제(2): 편집 거리
5.6 동적 계획법 예제(3): 구간 분할 최적화
5.7 정리
5.8 연습 문제
6장 설계기법(4): 이진 탐색법
6.1 배열 이진 탐색
6.1.1 배열 이진 탐색
6.1.2 배열 이진 탐색 복잡도(*)
6.2 C 의 std::lower_bound()
6.3 일반화한 이진 탐색법
6.4 좀 더 일반화한 이진 탐색법(*)
6.5 응용 예(1): 나이 맞히기 게임
6.6 응용 예(2): std::lower_bound() 활용
6.7 응용 예(3): 최적화 문제를 판정 문제로 바꾸기
6.8 응용 예(4): 중앙값 구하기
6.9 정리
6.10 연습 문제
7장 설계 기법(5): 탐욕법
7.1 탐욕법이란?
7.2 탐욕법으로 최적해를 구할 수 없는 경우
7.3 탐욕법 패턴(1): 교환해도 악화되지 않음
7.4 탐욕법 패턴(2): 현재가 좋으면 미래도 좋음
7.5 정리
7.6 연습 문제
8장 자료 구조(1): 배열, 연결 리스트, 해시 테이블
8.1 자료 구조를 배우는 의미
8.2 배열
8.3 연결 리스트
8.4 연결 리스트 삽입과 삭제
8.4.1 연결 리스트 삽입
8.4.2 연결 리스트 삭제
8.5 배열과 연결 리스트 비교
8.6 해시 테이블
8.6.1 해시 테이블 만드는 법
8.6.2 해시 충돌 대책
8.6.3 해시 테이블 복잡도
8.6.4 C 와 파이썬의 해시 테이블
8.6.5 연상 배열
8.7 정리
8.8 연습 문제
9장 자료구조(2): 스택과 큐
9.1 스택과 큐의 개념
9.2 스택과 큐의 동작과 구현
9.2.1 스택 동작과 구현
9.2.2 큐 동작과 구현
9.3 정리
9.4 연습 문제
10장 자료 구조(3): 그래프와 트리
10.1 그래프
10.1.1 그래프 사고방식
10.1.2 유향 그래프와 무향 그래프
10.1.3 워크, 사이클, 패스
10.1.4 연결성
10.2 그래프를 사용하는 공식화 예시
10.2.1 소셜 네트워크
10.2.2 교통 네트워크
10.2.3 게임 국면 전이
10.2.4 작업 의존 관계
10.3 그래프 구현
10.4 가중 그래프 구현
10.5 트리
10.5.1 루트 트리
10.5.2 부분 트리와 트리 높이
10.6 순서 트리와 이진 트리
10.6.1 순서 트리와 이진 트리
10.6.2 강균형 이진 트리
10.7 이진 트리를 사용한 자료 구조 예(1): 힙
10.7.1 힙이란?
10.7.2 힙 실현 방법
10.7.3 힙 쿼리 처리
10.7.4 힙 구현 예
10.7.5 O(N) 복잡도로 힙 구축(*)
10.8 이진 트리를 사용하는 자료 구조 예(2): 이진 탐색 트리
10.9 정리
10.10 연습 문제
11장 자료 구조(4): Union-Find
11.1 Union-Find란?
11.2 Union-Find 구조
11.3 Union-Find 복잡도를 줄이는 방법
11.4 Union-Find 개선법 1: union by size
11.4.1 union by size란?
11.4.2 union by size 복잡도 분석
11.5 Union-Find 개선법 2: 경로 압축
11.6 Union-Find 구현
11.7 Union-Find 응용: 그래프 연결 요소 개수
11.8 정리
11.9 연습 문제
12장 정렬
12.1 정렬이란?
12.2 정렬 알고리즘의 좋고 나쁨
12.2.1 in-place와 안정성
12.2.2 어떤 정렬 알고리즘이 좋은가?
12.3 정렬(1): 삽입 정렬
12.3.1 동작과 구현
12.3.2 삽입 정렬 복잡도와 성질
12.4 정렬(2): 병합 정렬
12.4.1 동작과 구현
12.4.2 병합 정렬 복잡도와 성질
12.4.3 병합 정렬 복잡도를 자세히 분석하기(*)
12.5 정렬(3): 퀵 정렬
12.5.1 동작과 구현
12.5.2 퀵 정렬 복잡도와 성질
12.5.3 무작위 선택 퀵 정렬(*)
12.6 정렬(4): 힙 정렬
12.7 정렬 복잡도의 하한값
12.8 정렬(5): 버킷 정렬
12.9 정리
12.10 연습 문제
13장 그래프(1): 그래프 탐색
13.1 그래프 탐색을 배우는 의의
13.2 깊이 우선 탐색과 너비 우선 탐색
13.3 재귀 함수를 사용하는 깊이 우선 탐색
13.4 전위 순회와 후위 순회
13.5 최단 경로 알고리즘으로 너비 우선 탐색
13.6 깊이 우선 탐색과 너비 우선 탐색의 복잡도
13.7 그래프 탐색 예(1): s-t 패스 구하기
13.8 그래프 탐색 예(2): 이분 그래프 판정
13.9 그래프 탐색 예(3): 위상 정렬
13.10 그래프 탐색 예(4): 트리 동적 계획법(*)
13.11 정리
13.12 연습 문제
14장 그래프(2): 최단 경로 문제
14.1 최단 경로 문제란?
14.1.1 가중치 유향 그래프
14.1.2 단일 시작점 최단 경로 문제
14.1.3 음의 변과 음의 닫힌 경로
14.2 최단 경로 문제 정리
14.3 완화
14.4 DAG의 최단 경로 문제: 동적 계획법
14.5 단일 시작점 최단 경로 문제: 벨만-포드 알고리즘
14.5.1 벨만-포드 알고리즘 아이디어
14.5.2 벨만-포드 알고리즘 구현
14.5.3 벨만-포드 알고리즘의 정확성(*)
14.6 단일 시작점 최단 경로 문제: 다익스트라 알고리즘
14.6.1 두 종류의 다익스트라 알고리즘
14.6.2 단순한 다익스트라 알고리즘
14.6.3 다익스트라 알고리즘의 직감적인 이미지
14.6.4 다익스트라 알고리즘 정확성(*)
14.6.5 희소 그래프인 경우: 힙을 사용한 고속화(*)
14.7 모든 쌍의 최단 경로 문제: 플로이드-워셜 알고리즘
14.8 참고: 포텐셜과 차분 제약계(*)
14.9 정리
14.10 연습 문제
15장 그래프(3): 최소 신장 트리 문제
15.1 최소 신장 트리 문제란?
15.2 크러스컬 알고리즘
15.3 크러스컬 알고리즘 구현
15.4 신장 트리 구조
15.4.1 컷
15.4.2 기본 사이클
15.4.3 기본 컷 집합
15.5 크러스컬 알고리즘의 정확성(*)
15.6 정리
15.7 연습 문제
16장 그래프(4): 네트워크 흐름
16.1 네트워크 흐름을 배우는 의의
16.2 그래프 연결도
16.2.1 변 연결도
16.2.2 최소 컷 문제
16.2.3 변 연결도를 구하는 알고리즘과 강 쌍대성 증명
16.3 최대 흐름 문제와 최소 컷 문제
16.3.1 최대 흐름 문제란?
16.3.2 흐름의 성질
16.3.3 최소 컷 문제와 쌍대성
16.3.4 포드-풀커슨 알고리즘
16.4 포드-풀커슨 알고리즘 구현
16.5 응용 예(1): 이분 매칭
16.6 응용 예(2): 점 연결도
16.7 응용 예(3): 프로젝트 선택 문제
16.8 정리
16.9 연습 문제
17장 P와NP
17.1 문제의 어려움을 측정하는 방법
17.2 P와 NP
17.3 P ≠ NP 문제
17.4 NP 완전
17.5 다항식 시간 환원 예
17.5.1 꼭짓점 커버 문제
17.5.2 부분합 문제(*)
17.6 NP 난해
17.7 정지 문제
17.8 정리
17.9 연습 문제
18장 어려운 문제 대책
18.1 NP 난해 문제와 마주하기
18.2 특수한 경우로 풀리는 방법
18.3 탐욕법
18.4 국소 탐색과 담금질 기법
18.5 분기 한정법
18.6 정수계획 문제로 공식화
18.7 근사 알고리즘
18.8 정리
18.9 연습 문제
19장 참고 문헌
19.1 알고리즘 전반
19.2 알고리즘 전반(본격적인 전문서)
19.3 복잡도, P와 NP
19.4 그래프 알고리즘, 조합 최적화
19.5 어려운 문제 대책
19.6 기타 분야
후기
찾아보기
1.1 알고리즘이란 무엇인가?
1.2 알고리즘 예제(1): 깊이 우선 탐색과 너비 우선 탐색
1.2.1 빈 칸 채우기 퍼즐로 배우는 깊이 우선 탐색
1.2.2 미로로 배우는 너비 우선 탐색
1.3 알고리즘 예제(2): 매칭
1.4 알고리즘 서술 방법
1.5 알고리즘을 배우는 의미
1.6 연습 문제
2장 복잡도와 빅오 표기법
2.1 복잡도란?
2.2 복잡도와 빅오 표기법
2.2.1 복잡도 빅오 표기법 생각해 보기
2.2.2 코드 2-1의 복잡도
2.2.3 코드 2-2의 복잡도
2.2.4 실제로 복잡도 구해 보기
2.2.5 복잡도를 빅오 표기법으로 표시하는 이유
2.3 복잡도를 구하는 예(1): 짝수 나열
2.4 복잡도를 구하는 예(2): 최근접 점쌍 문제
2.5 복잡도 사용법
2.6 복잡도 관련 주의 사항
2.6.1 시간 복잡도와 공간 복잡도
2.6.2 최악 시간 복잡도와 평균 시간 복잡도
2.7 란다우 빅오 표기법 상세 설명(*)
2.7.1 란다우 빅오 표기법
2.7.2 오메가 표기법
2.7.3 세타 표기법
2.8 마무리
2.9 연습 문제
3장 설계기법(1): 전체 탐색
3.1 전체 탐색을 배우는 의미
3.2 전체 탐색(1): 선형 탐색법
3.3 선형 탐색법의 응용
3.3.1 조건을 만족하는 위치 파악 가능
3.3.2 최솟값 구하기
3.4 전체 탐색(2): 쌍 전체 탐색
3.5 전체 탐색(3): 조합 전체 탐색(*)
3.6 정리
3.7 연습 문제
4장 설계기법(2): 재귀와 분할 정복법
4.1 재귀란 무엇인가?
4.2 재귀 사용 예(1): 유클리드 호제법
4.3 재귀 사용 예(2): 피보나치 수열
4.4 메모이제이션 동적 계획법
4.5 재귀 사용 예(3): 재귀 함수를 사용한 전체 탐색
4.5.1 부분합 문제
4.5.2 부분합 문제에 대한 재귀적 전체 탐색 복잡도(*)
4.5.3 부분합 문제에 대한 메모이제이션(*)
4.6 분할 정복법
4.7 정리
4.8 연습 문제
5장 설계 기법(3): 동적 계획법
5.1 동적 계획법이란?
5.2 동적 계획법 예제
5.3 동적 계획법 관련 개념도
5.3.1 완화
5.3.2 끌기 전이 형식과 밀기 전이 형식
5.3.3 끌기 전이 형식과 밀기 전이 형식 비교
5.3.4 전체 탐색 메모이제이션을 이용한 동적 계획법
5.4 동적 계획법 예제(1): 냅색 문제
5.5 동적 계획법 예제(2): 편집 거리
5.6 동적 계획법 예제(3): 구간 분할 최적화
5.7 정리
5.8 연습 문제
6장 설계기법(4): 이진 탐색법
6.1 배열 이진 탐색
6.1.1 배열 이진 탐색
6.1.2 배열 이진 탐색 복잡도(*)
6.2 C 의 std::lower_bound()
6.3 일반화한 이진 탐색법
6.4 좀 더 일반화한 이진 탐색법(*)
6.5 응용 예(1): 나이 맞히기 게임
6.6 응용 예(2): std::lower_bound() 활용
6.7 응용 예(3): 최적화 문제를 판정 문제로 바꾸기
6.8 응용 예(4): 중앙값 구하기
6.9 정리
6.10 연습 문제
7장 설계 기법(5): 탐욕법
7.1 탐욕법이란?
7.2 탐욕법으로 최적해를 구할 수 없는 경우
7.3 탐욕법 패턴(1): 교환해도 악화되지 않음
7.4 탐욕법 패턴(2): 현재가 좋으면 미래도 좋음
7.5 정리
7.6 연습 문제
8장 자료 구조(1): 배열, 연결 리스트, 해시 테이블
8.1 자료 구조를 배우는 의미
8.2 배열
8.3 연결 리스트
8.4 연결 리스트 삽입과 삭제
8.4.1 연결 리스트 삽입
8.4.2 연결 리스트 삭제
8.5 배열과 연결 리스트 비교
8.6 해시 테이블
8.6.1 해시 테이블 만드는 법
8.6.2 해시 충돌 대책
8.6.3 해시 테이블 복잡도
8.6.4 C 와 파이썬의 해시 테이블
8.6.5 연상 배열
8.7 정리
8.8 연습 문제
9장 자료구조(2): 스택과 큐
9.1 스택과 큐의 개념
9.2 스택과 큐의 동작과 구현
9.2.1 스택 동작과 구현
9.2.2 큐 동작과 구현
9.3 정리
9.4 연습 문제
10장 자료 구조(3): 그래프와 트리
10.1 그래프
10.1.1 그래프 사고방식
10.1.2 유향 그래프와 무향 그래프
10.1.3 워크, 사이클, 패스
10.1.4 연결성
10.2 그래프를 사용하는 공식화 예시
10.2.1 소셜 네트워크
10.2.2 교통 네트워크
10.2.3 게임 국면 전이
10.2.4 작업 의존 관계
10.3 그래프 구현
10.4 가중 그래프 구현
10.5 트리
10.5.1 루트 트리
10.5.2 부분 트리와 트리 높이
10.6 순서 트리와 이진 트리
10.6.1 순서 트리와 이진 트리
10.6.2 강균형 이진 트리
10.7 이진 트리를 사용한 자료 구조 예(1): 힙
10.7.1 힙이란?
10.7.2 힙 실현 방법
10.7.3 힙 쿼리 처리
10.7.4 힙 구현 예
10.7.5 O(N) 복잡도로 힙 구축(*)
10.8 이진 트리를 사용하는 자료 구조 예(2): 이진 탐색 트리
10.9 정리
10.10 연습 문제
11장 자료 구조(4): Union-Find
11.1 Union-Find란?
11.2 Union-Find 구조
11.3 Union-Find 복잡도를 줄이는 방법
11.4 Union-Find 개선법 1: union by size
11.4.1 union by size란?
11.4.2 union by size 복잡도 분석
11.5 Union-Find 개선법 2: 경로 압축
11.6 Union-Find 구현
11.7 Union-Find 응용: 그래프 연결 요소 개수
11.8 정리
11.9 연습 문제
12장 정렬
12.1 정렬이란?
12.2 정렬 알고리즘의 좋고 나쁨
12.2.1 in-place와 안정성
12.2.2 어떤 정렬 알고리즘이 좋은가?
12.3 정렬(1): 삽입 정렬
12.3.1 동작과 구현
12.3.2 삽입 정렬 복잡도와 성질
12.4 정렬(2): 병합 정렬
12.4.1 동작과 구현
12.4.2 병합 정렬 복잡도와 성질
12.4.3 병합 정렬 복잡도를 자세히 분석하기(*)
12.5 정렬(3): 퀵 정렬
12.5.1 동작과 구현
12.5.2 퀵 정렬 복잡도와 성질
12.5.3 무작위 선택 퀵 정렬(*)
12.6 정렬(4): 힙 정렬
12.7 정렬 복잡도의 하한값
12.8 정렬(5): 버킷 정렬
12.9 정리
12.10 연습 문제
13장 그래프(1): 그래프 탐색
13.1 그래프 탐색을 배우는 의의
13.2 깊이 우선 탐색과 너비 우선 탐색
13.3 재귀 함수를 사용하는 깊이 우선 탐색
13.4 전위 순회와 후위 순회
13.5 최단 경로 알고리즘으로 너비 우선 탐색
13.6 깊이 우선 탐색과 너비 우선 탐색의 복잡도
13.7 그래프 탐색 예(1): s-t 패스 구하기
13.8 그래프 탐색 예(2): 이분 그래프 판정
13.9 그래프 탐색 예(3): 위상 정렬
13.10 그래프 탐색 예(4): 트리 동적 계획법(*)
13.11 정리
13.12 연습 문제
14장 그래프(2): 최단 경로 문제
14.1 최단 경로 문제란?
14.1.1 가중치 유향 그래프
14.1.2 단일 시작점 최단 경로 문제
14.1.3 음의 변과 음의 닫힌 경로
14.2 최단 경로 문제 정리
14.3 완화
14.4 DAG의 최단 경로 문제: 동적 계획법
14.5 단일 시작점 최단 경로 문제: 벨만-포드 알고리즘
14.5.1 벨만-포드 알고리즘 아이디어
14.5.2 벨만-포드 알고리즘 구현
14.5.3 벨만-포드 알고리즘의 정확성(*)
14.6 단일 시작점 최단 경로 문제: 다익스트라 알고리즘
14.6.1 두 종류의 다익스트라 알고리즘
14.6.2 단순한 다익스트라 알고리즘
14.6.3 다익스트라 알고리즘의 직감적인 이미지
14.6.4 다익스트라 알고리즘 정확성(*)
14.6.5 희소 그래프인 경우: 힙을 사용한 고속화(*)
14.7 모든 쌍의 최단 경로 문제: 플로이드-워셜 알고리즘
14.8 참고: 포텐셜과 차분 제약계(*)
14.9 정리
14.10 연습 문제
15장 그래프(3): 최소 신장 트리 문제
15.1 최소 신장 트리 문제란?
15.2 크러스컬 알고리즘
15.3 크러스컬 알고리즘 구현
15.4 신장 트리 구조
15.4.1 컷
15.4.2 기본 사이클
15.4.3 기본 컷 집합
15.5 크러스컬 알고리즘의 정확성(*)
15.6 정리
15.7 연습 문제
16장 그래프(4): 네트워크 흐름
16.1 네트워크 흐름을 배우는 의의
16.2 그래프 연결도
16.2.1 변 연결도
16.2.2 최소 컷 문제
16.2.3 변 연결도를 구하는 알고리즘과 강 쌍대성 증명
16.3 최대 흐름 문제와 최소 컷 문제
16.3.1 최대 흐름 문제란?
16.3.2 흐름의 성질
16.3.3 최소 컷 문제와 쌍대성
16.3.4 포드-풀커슨 알고리즘
16.4 포드-풀커슨 알고리즘 구현
16.5 응용 예(1): 이분 매칭
16.6 응용 예(2): 점 연결도
16.7 응용 예(3): 프로젝트 선택 문제
16.8 정리
16.9 연습 문제
17장 P와NP
17.1 문제의 어려움을 측정하는 방법
17.2 P와 NP
17.3 P ≠ NP 문제
17.4 NP 완전
17.5 다항식 시간 환원 예
17.5.1 꼭짓점 커버 문제
17.5.2 부분합 문제(*)
17.6 NP 난해
17.7 정지 문제
17.8 정리
17.9 연습 문제
18장 어려운 문제 대책
18.1 NP 난해 문제와 마주하기
18.2 특수한 경우로 풀리는 방법
18.3 탐욕법
18.4 국소 탐색과 담금질 기법
18.5 분기 한정법
18.6 정수계획 문제로 공식화
18.7 근사 알고리즘
18.8 정리
18.9 연습 문제
19장 참고 문헌
19.1 알고리즘 전반
19.2 알고리즘 전반(본격적인 전문서)
19.3 복잡도, P와 NP
19.4 그래프 알고리즘, 조합 최적화
19.5 어려운 문제 대책
19.6 기타 분야
후기
찾아보기
알고리즘 문제를 풀 수 있다!
더 나아가, 설계하고 개선하고 확장하여 새로운 무언가를 생각해 낼 수 있다!
컴퓨터 과학을 배운다면 피할 수 없는 알고리즘
알고리즘이란 문제를 풀기 위한 절차다. 알고리즘을 배운다는 건 단순히 이론을 외우는 것이 아닌 세상의 다양한 문제를 해결하는 수단을 늘려가는 것을 말한다. 알고리즘을 잘 다뤄서 제시된 문제를 잘 풀고 싶다면? 내가 직접 알고리즘을 설계하고 더 효율이 높게 개선하고 싶다면? 이를 위해서는 어떤 알고리즘이 있는지 알기만 하는 데서 그치지 않고 설계하고 응용하는 과정을 학습해야 한다. 알고리즘 동작을 구체적으로 이해하는 걸 넘어서, 실제로 알고리즘을 활용하여 문제를 만족스럽게 해결할 때 비로소 알고리즘을 배웠다고 할 수 있다.
설계 기법을 중시하면서 알고리즘 전체를 체계적으로 설명
이 책은 문제의 답을 스스로 찾아내고, 알고리즘 지식을 확실히 자신의 것으로 만들어 활용하는 것을 목표로 한다. 이를 위해 먼저 알고리즘을 설계할 때 필요한 접근법(설계 기법)을 상세히 설명하고, 이어서 설계한 알고리즘을 효과적으로 실현하는 데 있어서 중요한 자료 구조를 살펴본다. 그리고 앞에서 배운 설계 기법과 자료 구조를 활용하여 정렬 알고리즘과 그래프 알고리즘을 배운다. 마지막으로 효율적으로 풀 수 있는 알고리즘을 설계할 수 없는 난제를 판별하는 방법과 이에 대응하는 방법을 살펴본다.
쉬운 문장, 쉬운 코드, 재미있는 그림, 어려운 내용도 간단히 이해
어려운 수식, 복잡한 내용은 담지 않았다. 중학 수학과 최소한의 C 지식만 있으면 알고리즘의 기초를 체계적으로 익힐 수 있다. 설계 기법에 중점을 둔 설명은 입문자뿐만 아니라 중급자 레벨에도 추천한다. 핵심 개요, 일반화, 좋은 예와 나쁜 예, 응용 예, 주의점 등을 단계별로 구성하고, 여러 측면에서 알고리즘 사고법과 기술을 살펴본다. 알고리즘, 자료 구조를 시각적으로 이해할 수 있도록 그림도 풍부하게 사용했다. 코드는 의사 코드가 아닌 C 코드를 사용했으며, 코드 또한 읽기 쉽고 이해하기 쉽도록 명확하게 작성하고자 했다.
이 책에서 다루는 내용
단순히 알고리즘 동작을 설명하기보다는 좋은 알고리즘을 설계하는 방법에 중점을 둡니다. 알고리즘을 처음 배우는 분부터 실용적인 알고리즘 설계 기법을 배우고 싶은 분까지 폭넓게 즐길 수 있으면 좋겠습니다.
필요한 예비지식
고등학교 수학을 배웠고 프로그래밍 경험이 있다고 전제합니다. 복잡한 수학적 이해가 필요한 부분도 있는데, 초보자에게 어려운 내용은 (*) 기호로 표시했습니다.
책에 나오는 소스 코드는 C 로 작성했는데, 기본 기능만 사용하므로 프로그래밍 경험이 있다면 큰 문제 없이 읽을 수 있습니다. C 의 고유 기능 중 다음을 사용합니다.
- std::vector 같은 STL 컨테이너
- std::sort() 같은 표준 라이브러리
- const 수식자
- 템플릿
- 포인터
- 참조
- 구조체
사용하는 언어
이 책은 C 를 사용해서 알고리즘을 작성하며, 다음과 같은 C 11 이후 기능을 일부 사용합니다.
- 범위 for문
- auto를 사용한 타입 추론(범위 for문에서만 사용)
- std::vector〈int〉 v = { 1, 2, 3 }; 같은 vector형 변수 초기화
- using을 사용한 자료형 별명 선언
- 템플릿 오른쪽 괄호에 공백 생략
- std::sort() 복잡도가 O(NlogN)이라는 것이 보증됨
동작 환경
이 책에 실린 소스 코드는 C 11 이후 버전의 C 에서 컴파일 가능하고, Wandbox에서 gcc 9.2.0으로 코드 동작을 확인했습니다. (번역 시 macOS Big Sur clang 12.0.0 버전에서 확인)
소스 코드는 다음 주소에서 다운로드 가능합니다.
- 저자 깃허브: https://github.com/drken1215/book_algorithm_solution
- 길벗 깃허브: https://github.com/gilbutITbook/080288
[감수자 서문]
이 책은 입문서에서 중요한 기초를 확실히 다지도록 해주면서 구성이 개성적입니다. 유명 알고리즘을 소개하는 데 그치지 않고 알고리즘 응용법과 설계 방법에도 비중을 둡니다. 널리 쓰이는 알고리즘 교과서의 구성은 유명 알고리즘을 단순히 소개하는 형식이 대다수입니다. ‘이런 처리를 하면 되니까 XX 알고리즘을 사용하자’라고 바로 답이 나오는 상황이라면 참고용으로 좋겠지요. 하지만 현실 세계에서 우리가 직면하는 문제는 그렇게 간단히 끝나지 않습니다. 어떤 알고리즘을 어떻게 사용하면 좋을지 알 수 없고 직접 알고리즘을 설계해야 하거나 해결 가능 여부조차 알 수 없는 그런 상황도 적지 않습니다. 이 책은 이런 다양한 상황에서 알고리즘 능력을 사용해 문제를 해결할 수 있도록 유명 알고리즘을 소개할 뿐만 아니라 알고리즘을 설계할 때 필요한 접근법(설계 기법)을 상세히 설명합니다.
[지은이 서문]
알고리즘을 배운다는 건 단순히 지식을 흡수하는 것이 아니라 세상의 다양한 문제를 해결하는 수단을 늘려가는 것입니다. 알고리즘이란 원래 문제를 풀기 위한 절차를 말합니다. 알고리즘 동작을 구체적으로 이해하는 걸 넘어서 실제로 문제 해결에 도움이 될 때 비로소 알고리즘을 배웠다고 할 수 있습니다. 알고리즘을 배우기 시작한 후 세상의 여러 문제와 마주쳤을 때 세계관에 혁명이 일어난 걸 기억합니다. 저도 알고리즘을 배우기 전에는 문제를 해결하는 행위란 고등학교 수학에서 배우던 ‘공식’ 같은 걸 찾는 거라고 생각했습니다. 그러니까 문제를 푸는 구체적이고 명확한 답을 구하는 것이 문제 해결이라고 무의식적으로 생각했습니다. 하지만 알고리즘을 배우고 나서는 ‘구체적인 답을 구하지 못하더라도 답에 다가가는 절차를 찾는 것’이라고 문제 풀이를 바라보는 관점이 변했고, 그에 따라 문제 해결 수단이 크게 늘어난 기분이 들었습니다. 이 책으로 여러분과 이런 감각을 공유할 수 있게 되길 바라며, 알고리즘을 설계하고 구현하는 즐거움을 느낄 수 있다면 저에게도 큰 즐거움일 것입니다.
[베타테스터 실습 후기]
이 책은 전반적으로 알고리즘 개념을 설명하고 증명하고 구현한 후 간단한 개선을 계속 반복해서 보여주는 구성입니다. (1) 먼저 도표와 그림을 통해 개념을 잡아 줍니다. (2) 시간 복잡도를 간단한 증명 과정을 통해 이해하고, (3) 실제 코드를 구현하면서 그 개념이 어떻게 코드로 구현되는지를 보여줍니다. (4) 개선 단계에서는 간단한 사고의 변화를 통해 성능이 얼마나 좋아지는지를 보여주고 이를 반복적으로 가이드해 줌으로써 독자를 훈련시킵니다. 또 어떻게 접근해야 하는지 쉬운 방법부터 설명한 뒤 사고의 방향을 바꿔 더 좋은 접근법을 설명하면서 차근차근 독자를 이끌어 나갑니다. 처음에 문제를 봤을 때는 떠올리지 못했던 방법이라도, 사고를 전환하고 다르게 접근하여 새로운 문제 해결 방법을 시도하도록 설명해 주므로 쉽게 느껴지고 비슷한 문제에 어떻게 접근해야 할지 배울 수 있습니다. 마치 페어 프로그래밍하는 느낌으로 독자를 이끌어 줍니다.
- 김효진(스튜디오주)
알고리즘 개념들을 간결하고 쉬운 문장으로 풀어내고 있으며, 처음 접하는 사람도 헤매지 않고 생각할 수 있도록 차곡차곡 개념을 쌓는 방향으로 서술하고 있습니다. 또한, 관례적인 예제가 아니라 구체적이고 수학적인 검증을 통한 예제로 기법들을 자세히 설명해 줍니다. 실제로 적용할 수 있고 실무에서도 반드시 필요한 여러 알고리즘 기법을 어떻게 알아야 하는지 쉽게 알려 주는 책입니다.
- 현진원(세이프텍리서치)
가장 기초적인 알고리즘의 개념부터 알고리즘에 자주 쓰이는 시간 복잡도, 설계 기법, 자료 구조, 정렬, 그래프 등 알고리즘 문제를 해결하는 데 꼭 필요한 지식을 총망라하여 보여주도록 구성되어 있습니다. 개인적으로 무작정 문제 풀이부터 부딪혀서 알고리즘을 공부해 왔는데, 알고리즘 공부의 시작을 이 책과 함께했다면 더욱 체계적이고 명확했을 것이라는 생각이 듭니다.
- 고민지(이화여자대학교)
알고리즘을 독학하면서 가장 어려웠던 부분이 시간 복잡도의 추상적인 개념과 다양한 알고리즘이었는데, 새로운 개념마다 그림으로 묘사되어 있어 글만으로는 이해하기 어려운 개념(동적 계획, 냅색, 트리 그래프 등)을 수월하게 이해할 수 있었습니다.
- 마영준(인천대학교 컴퓨터공학부)
더 나아가, 설계하고 개선하고 확장하여 새로운 무언가를 생각해 낼 수 있다!
컴퓨터 과학을 배운다면 피할 수 없는 알고리즘
알고리즘이란 문제를 풀기 위한 절차다. 알고리즘을 배운다는 건 단순히 이론을 외우는 것이 아닌 세상의 다양한 문제를 해결하는 수단을 늘려가는 것을 말한다. 알고리즘을 잘 다뤄서 제시된 문제를 잘 풀고 싶다면? 내가 직접 알고리즘을 설계하고 더 효율이 높게 개선하고 싶다면? 이를 위해서는 어떤 알고리즘이 있는지 알기만 하는 데서 그치지 않고 설계하고 응용하는 과정을 학습해야 한다. 알고리즘 동작을 구체적으로 이해하는 걸 넘어서, 실제로 알고리즘을 활용하여 문제를 만족스럽게 해결할 때 비로소 알고리즘을 배웠다고 할 수 있다.
설계 기법을 중시하면서 알고리즘 전체를 체계적으로 설명
이 책은 문제의 답을 스스로 찾아내고, 알고리즘 지식을 확실히 자신의 것으로 만들어 활용하는 것을 목표로 한다. 이를 위해 먼저 알고리즘을 설계할 때 필요한 접근법(설계 기법)을 상세히 설명하고, 이어서 설계한 알고리즘을 효과적으로 실현하는 데 있어서 중요한 자료 구조를 살펴본다. 그리고 앞에서 배운 설계 기법과 자료 구조를 활용하여 정렬 알고리즘과 그래프 알고리즘을 배운다. 마지막으로 효율적으로 풀 수 있는 알고리즘을 설계할 수 없는 난제를 판별하는 방법과 이에 대응하는 방법을 살펴본다.
쉬운 문장, 쉬운 코드, 재미있는 그림, 어려운 내용도 간단히 이해
어려운 수식, 복잡한 내용은 담지 않았다. 중학 수학과 최소한의 C 지식만 있으면 알고리즘의 기초를 체계적으로 익힐 수 있다. 설계 기법에 중점을 둔 설명은 입문자뿐만 아니라 중급자 레벨에도 추천한다. 핵심 개요, 일반화, 좋은 예와 나쁜 예, 응용 예, 주의점 등을 단계별로 구성하고, 여러 측면에서 알고리즘 사고법과 기술을 살펴본다. 알고리즘, 자료 구조를 시각적으로 이해할 수 있도록 그림도 풍부하게 사용했다. 코드는 의사 코드가 아닌 C 코드를 사용했으며, 코드 또한 읽기 쉽고 이해하기 쉽도록 명확하게 작성하고자 했다.
이 책에서 다루는 내용
단순히 알고리즘 동작을 설명하기보다는 좋은 알고리즘을 설계하는 방법에 중점을 둡니다. 알고리즘을 처음 배우는 분부터 실용적인 알고리즘 설계 기법을 배우고 싶은 분까지 폭넓게 즐길 수 있으면 좋겠습니다.
필요한 예비지식
고등학교 수학을 배웠고 프로그래밍 경험이 있다고 전제합니다. 복잡한 수학적 이해가 필요한 부분도 있는데, 초보자에게 어려운 내용은 (*) 기호로 표시했습니다.
책에 나오는 소스 코드는 C 로 작성했는데, 기본 기능만 사용하므로 프로그래밍 경험이 있다면 큰 문제 없이 읽을 수 있습니다. C 의 고유 기능 중 다음을 사용합니다.
- std::vector 같은 STL 컨테이너
- std::sort() 같은 표준 라이브러리
- const 수식자
- 템플릿
- 포인터
- 참조
- 구조체
사용하는 언어
이 책은 C 를 사용해서 알고리즘을 작성하며, 다음과 같은 C 11 이후 기능을 일부 사용합니다.
- 범위 for문
- auto를 사용한 타입 추론(범위 for문에서만 사용)
- std::vector〈int〉 v = { 1, 2, 3 }; 같은 vector형 변수 초기화
- using을 사용한 자료형 별명 선언
- 템플릿 오른쪽 괄호에 공백 생략
- std::sort() 복잡도가 O(NlogN)이라는 것이 보증됨
동작 환경
이 책에 실린 소스 코드는 C 11 이후 버전의 C 에서 컴파일 가능하고, Wandbox에서 gcc 9.2.0으로 코드 동작을 확인했습니다. (번역 시 macOS Big Sur clang 12.0.0 버전에서 확인)
소스 코드는 다음 주소에서 다운로드 가능합니다.
- 저자 깃허브: https://github.com/drken1215/book_algorithm_solution
- 길벗 깃허브: https://github.com/gilbutITbook/080288
[감수자 서문]
이 책은 입문서에서 중요한 기초를 확실히 다지도록 해주면서 구성이 개성적입니다. 유명 알고리즘을 소개하는 데 그치지 않고 알고리즘 응용법과 설계 방법에도 비중을 둡니다. 널리 쓰이는 알고리즘 교과서의 구성은 유명 알고리즘을 단순히 소개하는 형식이 대다수입니다. ‘이런 처리를 하면 되니까 XX 알고리즘을 사용하자’라고 바로 답이 나오는 상황이라면 참고용으로 좋겠지요. 하지만 현실 세계에서 우리가 직면하는 문제는 그렇게 간단히 끝나지 않습니다. 어떤 알고리즘을 어떻게 사용하면 좋을지 알 수 없고 직접 알고리즘을 설계해야 하거나 해결 가능 여부조차 알 수 없는 그런 상황도 적지 않습니다. 이 책은 이런 다양한 상황에서 알고리즘 능력을 사용해 문제를 해결할 수 있도록 유명 알고리즘을 소개할 뿐만 아니라 알고리즘을 설계할 때 필요한 접근법(설계 기법)을 상세히 설명합니다.
[지은이 서문]
알고리즘을 배운다는 건 단순히 지식을 흡수하는 것이 아니라 세상의 다양한 문제를 해결하는 수단을 늘려가는 것입니다. 알고리즘이란 원래 문제를 풀기 위한 절차를 말합니다. 알고리즘 동작을 구체적으로 이해하는 걸 넘어서 실제로 문제 해결에 도움이 될 때 비로소 알고리즘을 배웠다고 할 수 있습니다. 알고리즘을 배우기 시작한 후 세상의 여러 문제와 마주쳤을 때 세계관에 혁명이 일어난 걸 기억합니다. 저도 알고리즘을 배우기 전에는 문제를 해결하는 행위란 고등학교 수학에서 배우던 ‘공식’ 같은 걸 찾는 거라고 생각했습니다. 그러니까 문제를 푸는 구체적이고 명확한 답을 구하는 것이 문제 해결이라고 무의식적으로 생각했습니다. 하지만 알고리즘을 배우고 나서는 ‘구체적인 답을 구하지 못하더라도 답에 다가가는 절차를 찾는 것’이라고 문제 풀이를 바라보는 관점이 변했고, 그에 따라 문제 해결 수단이 크게 늘어난 기분이 들었습니다. 이 책으로 여러분과 이런 감각을 공유할 수 있게 되길 바라며, 알고리즘을 설계하고 구현하는 즐거움을 느낄 수 있다면 저에게도 큰 즐거움일 것입니다.
[베타테스터 실습 후기]
이 책은 전반적으로 알고리즘 개념을 설명하고 증명하고 구현한 후 간단한 개선을 계속 반복해서 보여주는 구성입니다. (1) 먼저 도표와 그림을 통해 개념을 잡아 줍니다. (2) 시간 복잡도를 간단한 증명 과정을 통해 이해하고, (3) 실제 코드를 구현하면서 그 개념이 어떻게 코드로 구현되는지를 보여줍니다. (4) 개선 단계에서는 간단한 사고의 변화를 통해 성능이 얼마나 좋아지는지를 보여주고 이를 반복적으로 가이드해 줌으로써 독자를 훈련시킵니다. 또 어떻게 접근해야 하는지 쉬운 방법부터 설명한 뒤 사고의 방향을 바꿔 더 좋은 접근법을 설명하면서 차근차근 독자를 이끌어 나갑니다. 처음에 문제를 봤을 때는 떠올리지 못했던 방법이라도, 사고를 전환하고 다르게 접근하여 새로운 문제 해결 방법을 시도하도록 설명해 주므로 쉽게 느껴지고 비슷한 문제에 어떻게 접근해야 할지 배울 수 있습니다. 마치 페어 프로그래밍하는 느낌으로 독자를 이끌어 줍니다.
- 김효진(스튜디오주)
알고리즘 개념들을 간결하고 쉬운 문장으로 풀어내고 있으며, 처음 접하는 사람도 헤매지 않고 생각할 수 있도록 차곡차곡 개념을 쌓는 방향으로 서술하고 있습니다. 또한, 관례적인 예제가 아니라 구체적이고 수학적인 검증을 통한 예제로 기법들을 자세히 설명해 줍니다. 실제로 적용할 수 있고 실무에서도 반드시 필요한 여러 알고리즘 기법을 어떻게 알아야 하는지 쉽게 알려 주는 책입니다.
- 현진원(세이프텍리서치)
가장 기초적인 알고리즘의 개념부터 알고리즘에 자주 쓰이는 시간 복잡도, 설계 기법, 자료 구조, 정렬, 그래프 등 알고리즘 문제를 해결하는 데 꼭 필요한 지식을 총망라하여 보여주도록 구성되어 있습니다. 개인적으로 무작정 문제 풀이부터 부딪혀서 알고리즘을 공부해 왔는데, 알고리즘 공부의 시작을 이 책과 함께했다면 더욱 체계적이고 명확했을 것이라는 생각이 듭니다.
- 고민지(이화여자대학교)
알고리즘을 독학하면서 가장 어려웠던 부분이 시간 복잡도의 추상적인 개념과 다양한 알고리즘이었는데, 새로운 개념마다 그림으로 묘사되어 있어 글만으로는 이해하기 어려운 개념(동적 계획, 냅색, 트리 그래프 등)을 수월하게 이해할 수 있었습니다.
- 마영준(인천대학교 컴퓨터공학부)
