컴퓨팅의 정수 : 컴퓨팅 사고력을 키우는 199가지 기술 문제

우쥔

저자:우쥔
자,엔지니어,투자가,작가이자성공한사업가.칭화대학에서학사,존스홉킨스대학교에서박사학위를받았고,음성인식,자연어처리,특히통계적언어모델링에대해연구했다.구글수석엔지니어로근무하며한·중·일검색알고리즘에공헌을많이했고,중국최대IT기업이자세계최대게임회사인텐센트의검색부문부사장을거쳐현재는벤처투자사인아미노캐피털을창업하여성공적으로운영하고있다.국내에소개된저서로《스마트시대무엇부터해야하나》(살림출판사,2018),《수학의아름다움》(세종서적,2019),《어떻게살아야할지막막한너에게》(오월구일,2019),《성장을꿈꾸는너에게》(오월구일,2021)등이있다.

역자:신준기
중국어전공을했으나정보를어떻게표현하고처리하는게가장효율적인지를고민하던끝에,인문계소프트웨어인재전형으로IT회사에입사하였다.입사후현재까지스마트팩토리관련소프트웨어를개발하면서공장에서나오는수많은데이터와씨름중이다.

옮긴이머리말ix
베타리더후기xii
추천사Ixiv
추천사IIxviii
시작하며xxi
이책에대하여xxix

CHAPTER0컴퓨팅의본질:기계운동에서전자운동으로1
0.1컴퓨터란무엇인가?1
0.2기계식컴퓨터,불대수와스위칭회로4
0.3튜링기계,컴퓨팅의본질은기계운동12
0.4인공지능의한계17
0.5마무리20

CHAPTER1작지만큰차이:BigO개념21
1.1알고리즘의정규화와정량화21
1.2컴퓨팅에서의차수적차이25
1.3최적의알고리즘을찾는방법30
1.4정렬에관한논의40
__1.4.1직관적인정렬알고리즘은어디에서시간을낭비할까?41
__1.4.2효과적인정렬알고리즘효율성은어디에서올까?43
__1.4.3특정한경우에서더나은알고리즘이있을까?48
1.5마무리51
부록:정렬알고리즘복잡도가O(NlogN)보다작아질수없는이유52

CHAPTER2역방향사고:순환에서재귀로53
2.1재귀:컴퓨팅사고의핵심53
__2.1.1간단해보이는순환적사고공식55
__2.1.2하노이의탑과구련환:재귀로표현되는문제57
__2.1.3가우스조차해결하지못한여덟개퀸문제61
2.2순회:재귀적사고의전형적응용63
__2.2.1이진트리와그순회65
__2.2.2재귀를사용한이진트리순회구현68
2.3스택과큐:순회의데이터구조71
2.4중첩:자연어의구조적특징76
2.5마무리81
부록1:피보나치수열의재귀공식유도82
부록2:여덟퀸문제알고리즘의의사코드84
부록3:임의의트리를이진트리로변환하기85

CHAPTER3모든것이코드다:추상화와표현86
3.1인간과컴퓨터사이의정보인코딩의차이점87
3.2황금분할문제와실험쥐문제91
3.3데이터표현:정밀도와범위96
3.4비선형코딩과차등코딩100
3.5허프먼코드102
3.6행렬의효과적인표현107
3.7마무리114
부록1:100층건물에서두개의유리공으로파손높이를테스트하는최적의방법115
부록2:허프먼코딩의유효성증명115

CHAPTER4지능의본질:분류와조합116
4.1문제는선택분류116
4.2정보의구성:집합과판단120
__4.2.1의사결정트리121
__4.2.2해시테이블124
4.3B+트리,B*트리:데이터베이스의데이터를구성하는방식127
4.4카탈랑수132
4.5마무리139
부록1:집합의열가지공리140
부록2:카탈랑수의재귀공식도출141

CHAPTER5도구와알고리즘:그래프이론및응용142
5.1그래프본질:점과선143
5.2그래프접근:순회와연결성148
5.3웹크롤러구축의개발자문제151
5.4동적계획법:최단경로를찾는효과적인방법154
5.5최대흐름:트래픽문제해결방법161
5.6최대매칭:흐름문제의확장169
5.7마무리173
부록1:그래프의깊이우선순회알고리즘173
부록2:그래프의너비우선순회알고리즘174
부록3:동적계획법을사용한최단거리를계산하는의사코드174
부록4:최대흐름알고리즘의사코드175

CHAPTER6복잡함의단순화:분할정복법응용176
6.1분할정복:O(N2)에서O(NlogN)으로177
6.2분할알고리즘:퀵정렬과중앙값문제186
6.3병렬에대한토론:행렬곱셈과맵리듀스197
6.4머신러닝에서딥러닝까지:구글브레인203
6.5마무리209

CHAPTER7공간과시간의균형:스토리지의이해211
7.1액세스:순차vs.임의213
7.2메모리계층:용량vs.속도225
__7.2.1CPU캐시에서클라우드스토리지까지226
__7.2.2두가지실제사례231
7.3인덱스:주소vs.내용234
7.4마무리237
부록:x&(x?1)를사용하여x에포함된1의수를세는방법238

CHAPTER8병렬과직렬:파이프라인과분산컴퓨팅239
8.1파이프라이닝:논리적직렬및물리적병렬처리239
8.2무어의법칙의두분수령242
8.3클라우드컴퓨팅이해하기:GFS와맵리듀스244
8.4마무리252

CHAPTER9상태와과정:등가성과인과관계254
9.1문제에서상태로255
9.2등가성:상태를추상화하는도구261
9.3인과관계:상태간의연결설정266
9.4마무리272

CHAPTER10결정론적알고리즘과확률:확률론적알고리즘과응용273
10.1데이터지문:무작위성으로확정한다274
10.2무작위성과양자통신278
10.3신뢰수준:비용과효과의균형282
10.4마무리288

CHAPTER11이론과실습:전형적인문제풀이289
11.1가장긴연속부분수열문제289
11.2구간병합문제294
11.3열두개의공문제296
11.4스카이라인문제302
11.5가장긴회문문제307
11.6계산기문제314
11.7검색결과요약문제317
11.8합이k인부분수열을찾는문제324
11.9마무리327

찾아보기329

컴퓨팅의본질을꿰뚫는글로벌IT기업문제풀이

내가배운기술이앞으로도유망할까?챗GPT가나온이후많은개발자가고민하는부분이다.급변하는기술시장에서나만의경쟁력을유지하려면컴퓨팅의본질을알아야한다고중국IT업계의대가우쥔박사는말한다.새로운기술이나와도컴퓨터는컴퓨팅의원리로작동하며,개발자는컴퓨팅사고를통해코드를제대로작성할수있어야경쟁력을유지할수있다.

저자는11장에걸쳐BigO,재귀,코드,분류,조합,그래프이론,분할정복법,스토리지,병렬,상태,난수등핵심개념들로컴퓨팅사고를이끌어낸다.이개념들을들어는봤더라도그뒤에있는컴퓨팅사고의본질을아는사람은드물것이다.개발자가어디까지발전할수있는지는컴퓨터과학을얼마나이해했느냐에달렸다고저자는말한다.

글로벌IT기업면접관출신의저자가알려주는40여개문제와풀이를통해컴퓨팅사고력을키울수있으며,각절말미에는심화사고문제를수록해독자가자신의수준을평가하고실전훈련을하는데도움이되게구성했다.알고리즘책치고쉽지만은않다.그럼에도독자가시간을할애하고연구하여심화사고문제까지풀어낸다면뿌듯함은물론이고,여기서배운컴퓨팅사고는IT업계에서일하는데평생도움이될것이다.

컴퓨터분야종사자라면커리어를더욱빨리성장시킬수있으며,IT업계에진출하려는이들은컴퓨팅의정수를깨닫고시행착오를줄일수있을것이다.또한,IT기술에흥미를가진독자라면기술적인세부사항을건너뛰고읽는것만으로도IT기술의특징과컴퓨팅사고방식을이해할수있을것이다.급변하는IT업계에서변하지않는든든한뒷배로컴퓨팅사고력을길러보자.

주요내용

-BigO개념
-순환에서재귀로
-추상화와표현
-분류와조합
-그래프이론
-분할정복법
-스토리지의이해
-파이프라인과분산컴퓨팅
-등가성과인과관계
-확률론적알고리즘