• 컴퓨터/IT > 컴퓨터공학 > 알고리즘/자료구조

출판사 리뷰

1장에서는 동적 계획법, 역추적, 너비 우선 탐색, 투 포인터, 슬라이딩 윈도 등을 포함해 자주 사용하는 알고리즘의 핵심과 문제 해결의 프레임을 확인합니다. 2장에서는 동적 계획법에서 사용되는 사고의 프레임을 사용해 정규 표현식(regular expression), 배낭 문제 등 기본적인 동적 계획법 문제를 해결합니다. 상태 전이 방정식을 작성하고, 상태 압축을 진행하는 방법 등을 소개합니다. 3장은 데이터 구조와 관련하여 이진 트리, LRU, LFU 등 면접 시 자주 접하는 알고리즘과 그 원리를 설명합니다. 4장은 역추적 알고리즘, 너비 우선 탐색 알고리즘 등의 핵심 비법과 프레임을 자세히 알아봅니다. 마지막으로 5장은 앞에서 배운 알고리즘들을 응용하여 면접에 자주 나오는 문제 18가지를 설명합니다. 다양한 알고리즘과 결합하여 문제를 설명하고 여러 가지 해법을 소개합니다. 리트코드(LeetCode)는 사용자도 많을뿐더러 문제도 2,000개 이상 보유하고 있습니다. 이 책은 그중에서 테스트에 자주 출제되는 문제만을 엄선했습니다. 특히 본 한국어판은 리트코드를 처음 접하는 독자를 위해 리트코드 사이트 사용법을 부록으로 추가했습니다. 테스트에 자주 나오는 알고리즘 문제를 직접 풀어보며 쉽고 재미있게 익혀보아요.

옮긴이 머리말 x
베타리더 후기 xii
머리말 xiv
이 책에 대하여 xv
이 책을 읽는 법 xviii

CHAPTER 0 언어 기초 1
0.1 C++ 1
0.2 자바 8
0.3 파이썬 3 14

CHAPTER 1 핵심 알고리즘 17
1.1 알고리즘 학습과 문제 해결 아이디어 17
1.2 동적 계획법 문제 해결 방법 27
1.3 역추적 알고리즘 문제 해결 방법 39
1.4 BFS 알고리즘 문제 해결 방법 50
1.5 투 포인터 기법 프레임 60

CHAPTER 2 동적 계획법 95
2.1 동적 계획법: 최장 증가 부분 수열 95
2.2 2차원 증가 부분 수열: 봉투 중첩 문제 103
2.3 최대 부분 배열 문제 106
2.4 동적 계획법 Q&A: 최적 하위 구조와 dp 순회 방향 110
2.5 기본 동적 계획법: 최장 공통 부분 순열 116
2.6 기본 동적 계획법: 편집 거리 121
2.7 부분 수열 문제 해결 템플릿: 최장 회문 부분 수열 135
2.8 상태 압축: 동적 계획법 차원 축소 140
2.9 최소 삽입 횟수로 회문 문자열 구성 147
2.10 동적 계획법의 정규 표현식 155
2.11 다른 정의에 따른 다른 해법 163
2.12 기본 동적 계획법: 고층에서 계란 던지기 169
2.13 기본 동적 계획법: 고층에서 계란 던지기(심화) 174
2.14 기본 동적 계획법: 풍선 터트리기 문제 182
2.15 기본 동적 계획법: 0-1 배낭 문제 190
2.16 기본 동적 계획법: 하부 집합 배낭 문제 194
2.17 기본 동적 계획법: 완전한 배낭 문제 198
2.18 문제는 변해도 방법은 변하지 않는다 202
2.19 동적 계획법과 역추적 알고리즘의 관계 209

CHAPTER 3 데이터 구조 219
3.1 LRU 캐시 제거 알고리즘 219
3.2 계층별로 분해하여 LFU 알고리즘 작성하기 231
3.2.4 LFU 핵심 로직 237
3.3 이진 탐색 트리 작업 모음 239
3.4 완전 이진 트리의 노드 계산이 어려운 이유 247
3.5 다양한 순회 프레임을 사용한 이진 트리 직렬화와 역직렬화 251
3.6 Git 원리, 이진 트리의 최소 공통 조상 263
3.7 특수 데이터 구조: 단조 스택 269
3.8 특수 데이터 구조: 단조 큐 274
3.8.3 알고리즘 복잡도 분석 280
3.9 회문 연결 리스트 판단 280
3.10 순수 재귀의 반전 연결 리스트 조작 286
3.11 k개의 반전 연결 리스트 292

CHAPTER 4 알고리즘 사고 299
4.1 하부 집합, 조합, 순열 문제 해결을 위한 역추적 알고리즘 299
4.2 역추적 알고리즘 실전: 스도쿠 문제 풀기 307
4.3 역추적 알고리즘 실전: 괄호 생성 312
4.4 BFS 알고리즘 무차별 탐색으로 퍼즐 문제 풀기 316
4.5 2Sum 문제의 핵심 아이디어 321
4.6 nSum 문제를 해결하는 함수 325
4.7 복잡한 문제 분해하기: 계산기 구현 333
4.8 호떡을 정리하는 재귀 아이디어 342
4.9 구간 합 기법을 사용한 부분 배열 문제 해결 346
4.10 중첩 리스트 평탄화 350

CHAPTER 5 면접에 자주 나오는 문제 357
5.1 효율적으로 소수를 찾는 방법 357
5.2 효율적인 모듈로 지수 연산 361
5.3 이진 탐색 알고리즘 사용하기 366
5.4 빗물 받는 문제의 효율적인 해결 방법 370
5.5 정렬된 배열의 중복 요소 제거 377
5.6 최장 회문 부분 문자열 찾기 379
5.7 탐욕 알고리즘을 활용한 점프 게임 382
5.8 탐욕 알고리즘을 사용한 시간 관리 388
5.9 괄호의 유효성 판단 394
5.10 수험생의 좌석 배치 396
5.11 Union-Find 알고리즘 상세 403
5.12 Union-Find 알고리즘 응용 414
5.13 한 줄의 코드로 풀 수 있는 알고리즘 문제 420

APPENDIX A 한국어판 부록: LeetCode 가이드 427

문제 목록 433
찾아보기 436