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 연습 문제
○이 책에서 다루는 내용
단순히 알고리즘 동작을 설명하기보다는 좋은 알고리즘을 설계하는 방법에 중점을 둡니다. 알고리즘을 처음 배우는 분부터 실용적인 알고리즘 설계 기법을 배우고 싶은 분까지 폭넓게 즐길 수 있으면 좋겠습니다.
필요한 예비지식
고등학교 수학을 배웠고 프로그래밍 경험이 있다고 전제합니다. 복잡한 수학적 이해가 필요한 부분도 있는데, 초보자에게 어려운 내용은 (* 기호로 표시했습니다.
책에 나오는 소스 코드는 C++로 작성했는데, 기본 기능만 사용하므로 프로그래밍 경험이 있다면 큰 문제 없이 읽을 수 있습니다. C++의 고유 기능 중 다음을 사용합니다.
- std::vector 같은 STL 컨테이너
- std::sort( 같은 표준 라이브러리
- const 수식자
- 템플릿
- 포인터
- 참조
- 구조체
사용하는 언어
이 책은 C++를 사용해서 알고리즘을 작성하며, 다음과 같은 C++ 11 이후 기능을 일부 사용합니다.
- 범위 for문
- auto를 사용한 타입 추론(범위 for문에서만 사용
- std::vector 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
[베타테스터 실습 후기]
이 책은 전반적으로 알고리즘 개념을 설명하고 증명하고 구현한 후 간
