패턴 공략! 자바스크립트 코딩 테스트

▶ 0장 시작하기 전에 1
0.1 왜 자바스크립트인가? 1
____0.1.1 자바스크립트의 특징 2
0.2 알고리즘 성능 평가와 복잡도 7
0.3 빅 오 표기법 8
____0.3.1 O(1) 상수 시간 9
____0.3.2 O(log n) 로그 시간 9
____0.3.3 O(n) 선형 시간 10
____0.3.4 O(n2) 2차 시간 11
____0.3.5 O(2n) 지수 시간 12
____0.3.6 O(n!) 팩토리얼 시간 13
____0.3.7 자바스크립트 주요 메서드의 시간 복잡도 13
____0.3.8 공간 복잡도 14

▶ 1장 문자열 패턴 19
1.1 문자열 객체 이해하기 19
____1.1.1 불변성 19
____1.1.2 원시 타입 vs 객체 타입 21
____1.1.3 인덱싱 21
1.2 속성 및 주요 메서드 22
1.3 문자열 문제 유형 23
____1.3.1 순서 뒤집기 23
____1.3.2 중복 제거 26
____1.3.3 문자열 압축 29
____1.3.4 가장 많이 등장하는 단어 30
____1.3.5 회문 32
____1.3.6 애너그램 35
____1.3.7 정수 변환 38
____1.3.8 재정렬 41
____1.3.9 괄호 유효성 검사 43
____1.3.10 회전된 문자열 46
____1.3.11 가장 긴 공통 접두사 48
1.4 응용 문제 49
____1.4.1 애너그램 분류하기 50
____1.4.2 가장 긴 회문 부분 문자열 찾기 52
____1.4.3 같은 패턴 찾기 56
1.5 인터뷰 팁과 고려 사항 59

▶ 2장 투 포인터 패턴 61
2.1 투 포인터 패턴 이해하기 61
2.2 투 포인터 패턴 문제 유형 63
____2.2.1 두 수의 합 63
____2.2.2 배열의 교집합 66
2.3 응용 문제: 배열 70
____2.3.1 정렬된 제곱수 70
____2.3.2 세 수의 합 74
____2.3.3 가장 큰 사각형 78
____2.3.4 음수 옮기기 82
____2.3.5 제곱수의 합 86
2.4 응용 문제: 연결 리스트 89
____2.4.1 사이클의 시작 노드 90
____2.4.2 정렬된 두 리스트의 병합 95
____2.4.3 연결 리스트의 합산 99
____2.4.4 리스트의 파티션 102
____2.4.5 리스트 역순 정렬 105
2.5 인터뷰 팁과 고려 사항 108

▶ 3장 슬라이딩 윈도 패턴 111
3.1 슬라이딩 윈도 패턴 111
3.2 문제 유형 분석 112
3.3 응용 문제 114
____3.3.1 가장 긴 부분 문자열 114
____3.3.2 세 문자 118
____3.3.3 연속된 자연수의 합 121
____3.3.4 과일 바구니 124
____3.3.5 가장 긴 대소문자 128
____3.3.6 애너그램 II 132
____3.3.7 최고 점수 136
3.4 인터뷰 팁과 고려 사항 140

▶ 4장 그리디 패턴 141
4.1 최적화 문제 유형 141
4.2 그리디 패턴 142
4.3 응용 문제 144
____4.3.1 강의실 145
____4.3.2 장바구니 149
____4.3.3 균형 잡힌 문자열 나누기 153
____4.3.4 XY 155
____4.3.5 구명 보트 158
____4.3.6 결승선 161
____4.3.7 주유소 164
4.4 인터뷰 팁과 고려 사항 168

▶ 5장 이진 탐색 패턴 171
5.1 분할 정복 171
5.2 이진 탐색 173
5.3 응용 문제 177
____5.3.1 첫 번째 True 177
____5.3.2 고정점 180
____5.3.3 제곱근 183
____5.3.4 배열의 중복 요소 찾기 186
____5.3.5 시작과 끝 189
____5.3.6 다음 문자 193
____5.3.7 최솟값 196
5.4 인터뷰 팁과 고려 사항 199

▶ 6장 정렬 패턴 201
6.1 정렬 201
6.2 정렬의 종류 202
____6.2.1 버블 정렬 202
____6.2.2 선택 정렬 203
____6.2.3 삽입 정렬 203
____6.2.4 퀵 정렬 203
____6.2.5 병합 정렬 205
____6.2.6 퀵 정렬 vs 병합 정렬 208
6.3 응용 문제 209
____6.3.1 0, 1, 2 정렬 210
____6.3.2 성적순 213
____6.3.3 빈도 정렬 216
____6.3.4 교집합 219
____6.3.5 문자열 섞기 222
____6.3.6 작은 수 224
____6.3.7 빈도순 정렬 227
____6.3.8 리스트 정렬 230
6.4 인터뷰 팁과 고려 사항 235

▶ 7장 행렬 237
7.1 행렬 237
____7.1.1 행렬과 빅 오 238
7.2 행렬 기초 학습 239
____7.2.1 순회 239
____7.2.2 셀 값 1로 만들기 240
____7.2.3 전치 행렬 만들기 241
7.3 응용 문제 243
____7.3.1 음수 세기 243
____7.3.2 90도 회전 246
____7.3.3 나선형 순회 250
____7.3.4 제로 행렬 254
____7.3.5 공통 요소 258
____7.3.6 대각선 차이 261
____7.3.7 행렬 탐색 264
7.4 인터뷰 팁과 고려 사항 267

▶ 8장 너비 우선 탐색 패턴 269
8.1 너비 우선 탐색 269
____8.1.1 선형 자료 구조 vs 비선형 자료 구조 269
____8.1.2 너비 우선 탐색이란? 269
8.2 그래프와 트리 순회 270
____8.2.1 너비 우선 탐색으로 그래프 순회 270
____8.2.2 너비 우선 탐색으로 트리 순회 272
8.3 응용 문제 274
____8.3.1 이진 트리 레벨 순회 275
____8.3.2 레벨의 평균값 279
____8.3.3 이진 트리의 최소 깊이 281
____8.3.4 레벨 순회 후속 노드 285
____8.3.5 지그재그 288
____8.3.6 섬의 개수 291
____8.3.7 영역 채우기 295
____8.3.8 최단 경로 301
8.4 인터뷰 팁과 고려 사항 305

▶ 9장 깊이 우선 탐색 패턴 307
9.1 깊이 우선 탐색 307
9.2 그래프와 트리 순회 307
____9.2.1 깊이 우선 탐색으로 그래프 순회 307
____9.2.2 깊이 우선 탐색으로 트리 순회 309
9.3 재귀 312
____9.3.1 재귀 함수의 기본 구조 313
____9.3.2 재귀 함수의 프롤로그와 에필로그 313
9.4 응용 문제 314
____9.4.1 같은 트리 314
____9.4.2 트리의 최대 깊이 317
____9.4.3 경로의 합 320
____9.4.4 가장 긴 경로 323
____9.4.5 경로 합의 개수 327
____9.4.6 가장 큰 섬 332
____9.4.7 이진 탐색 트리 336
____9.4.8 최소 공통 조상 340
9.5 인터뷰 팁과 고려 사항 343

▶ 10장 부분 집합 패턴 345
10.1 부분 집합 345
____10.1.1 부분 집합 345
____10.1.2 조합 345
____10.1.3 순열 346
10.2 백트래킹 vs 동적 프로그래밍 346
____10.2.1 백트래킹 346
____10.2.2 동적 프로그래밍 348
10.3 응용 문제 351
____10.3.1 부분 집합 351
____10.3.2 부분 집합 II 354
____10.3.3 부분 집합의 합 357
____10.3.4 같은 부분 집합의 합 364
____10.3.5 k개의 숫자 조합 찾기 371
____10.3.6 숫자 집합의 순열 375
____10.3.7 대소문자 변환 순열 379
____10.3.8 균형 잡힌 괄호 382
10.4 인터뷰 팁과 고려 사항 386

▶ 부록 A 자료 구조 핵심 정리 387
A.1 배열 387
____A.1.1 배열 선언/초기화 388
____A.1.2 읽기 388
____A.1.3 탐색 388
____A.1.4 삽입 389
____A.1.5 삭제 389
A.2 연결 리스트 390
____A.2.1 연결 리스트 생성 391
____A.2.2 읽기/탐색 391
____A.2.3 삽입 392
____A.2.4 삭제 393
A.3 스택 394
____A.3.1 스택 선언/초기화 395
____A.3.2 삽입 395
____A.3.3 삭제 395
____A.3.4 읽기 395
____A.3.5 탐색 396
A.4 큐 397
____A.4.1 큐 선언/초기화 397
____A.4.2 삽입 397
____A.4.3 제거 398
____A.4.4 확인 398
A.5 그래프 399
____A.5.1 그래프 구현 400
____A.5.2 그래프 순회 401
A.6 트리 404
____A.6.1 트리의 종류 405
____A.6.2 트리 구현 405
____A.6.3 탐색 407
____A.6.4 이진 트리의 순회 409
A.7 해시 테이블 410
____A.7.1 객체 410
____A.7.2 Map 객체 411

▶ 부록 B 실전 대비 문제 413
문제 1 안전한 비밀번호 413
문제 2 문자열 게임 414
문제 3 두 카드의 조합 415
문제 4 김대리의 부동산 투자 415
문제 5 로미의 고민 416
문제 6 보리를 이겨라 417
문제 7 크리스마스 트리 418
문제 8 카일의 첫 업무 419
문제 9 마라톤 대회 420
문제 10 최소 편집 거리 421

▶ 부록 C 실전 대비 문제 풀이 423
문제 1 안전전한 비밀번호 423
문제 2 문자열 게임 425
문제 3 두 카드의 조합 426
문제 4 김대리의 부동산 투자 427
문제 5 로미의 고민 428
문제 6 보리를 이겨라 430
문제 7 크리스마스 트리 431
문제 8 카일의 첫 업무 432
문제 9 마라톤 대회 434
문제 10 최소 편집 거리 436

찾아보기 439