코딩 인터뷰를 위한 알고리즘 치트시트

옮긴이 머리말 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

우리는 문제의 유형을 파악하고 아이디어와 해법을 도출해내는 방식을 배울 것이다. 틀에서 벗어나 문제의 공통점과 본질을 파악하면 한 문제를 통해 비슷한 유형의 문제들을 풀 수 있다. / 우리는 일반적인 데이터 구조를 다루는 것이지 알고리즘 대회를 준비하는 것이 아니다. 따라서 일반적인 문제만 풀면 된다. 설명과 함께 나의 개인적인 문제 풀이 경험도 공유한다. 따라서 독자는 나의 시점에서 이해해보는 것도 도움이 될 것이며 다른 세부 사항에는 신경 쓰지 않아도 된다. 이번 절에서 데이터 구조와 알고리즘에 대한 이해의 틀을 확립할 수 있기를 바란다.

무차별 탐색은 효율이 매우 낮아 불필요한 계산을 피하기 위해서는 메모 또는 DP 테이블을 사용한 최적화 과정이 필요하다. / 이런 과정을 통해 동적 계획법 문제는 최적의 하위 구조를 가질 수 있으며, 하위 문제의 최댓값을 통해 상위 문제의 최댓값을 얻을 수 있다. / 동적 계획법의 핵심 아이디어는 무차별 탐색을 통해 최댓값을 찾는 것이지만, 문제는 다양한 방식으로 변형될 수 있다. 무차별 탐색은 쉽지 않으며, 정확한 상태 전이 방정식을 통해서만 정확한 탐색이 가능하다.