코딩 인터뷰를 위한 알고리즘 치트시트 (리트코드LeetCode 문제를 풀면서 배우는 코딩 테스트)

푸둥라이

付东来
오픈소스를활용해새로운가치를창조하고있다.다년간의문제풀이경험으로복잡한알고리즘문제를쉽게가르치기위해노력중이다.IT종사자들이시행착오를줄이고알고리즘의난관을뛰어넘는데도움이되기를바라며이책을집필했다.

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

CHAPTER0언어기초1
0.1C++1
0.2자바8
0.3파이썬314

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

CHAPTER2동적계획법95
2.1동적계획법:최장증가부분수열95
2.22차원증가부분수열:봉투중첩문제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

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

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

CHAPTER5면접에자주나오는문제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.11Union-Find알고리즘상세403
5.12Union-Find알고리즘응용414
5.13한줄의코드로풀수있는알고리즘문제420

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

문제목록433
찾아보기436

리트코드LeetCode로실습하며코딩인터뷰를대비하는알고리즘문제풀이참고서

시험과면접이목적이라면두꺼운알고리즘서적보다는문제를직접풀어보는것이훨씬도움이됩니다.문제를푸는방식에는노하우가있기마련이고,깃허브에서스타를10만개받은저자푸둥라이의노하우를이책에서배울수있습니다.몇천개의문제를다풀어볼수는없으니문제를유형별로나누고공통되는프레임을익힙니다.이와같은방식으로해법을익히면하나의해법으로도수천가지문제에대응할수있습니다.

1장에서는동적계획법,역추적,너비우선탐색,투포인터,슬라이딩윈도등을포함해자주사용하는알고리즘의핵심과문제해결의프레임을확인합니다.2장에서는동적계획법에서사용되는사고의프레임을사용해정규표현식(regularexpression),배낭문제등기본적인동적계획법문제를해결합니다.상태전이방정식을작성하고,상태압축을진행하는방법등을소개합니다.

3장은데이터구조와관련하여이진트리,LRU,LFU등면접시자주접하는알고리즘과그원리를설명합니다.4장은역추적알고리즘,너비우선탐색알고리즘등의핵심비법과프레임을자세히알아봅니다.마지막으로5장은앞에서배운알고리즘들을응용하여면접에자주나오는문제18가지를설명합니다.다양한알고리즘과결합하여문제를설명하고여러가지해법을소개합니다.

리트코드(LeetCode)는사용자도많을뿐더러문제도2,000개이상보유하고있습니다.이책은그중에서테스트에자주출제되는문제만을엄선했습니다.특히본한국어판은리트코드를처음접하는독자를위해리트코드사이트사용법을부록으로추가했습니다.테스트에자주나오는알고리즘문제를직접풀어보며쉽고재미있게익혀보아요.