알고리듬으로 생각하기 : 국제 프로그래밍 경진대회 문제로 배우는 - 에이콘 프로그래밍 언어 시리즈

다니엘진가로

저자:다니엘진가로(DanielZingaro)
토론토대학의컴퓨터과학과조교수이며토론토대학의교육상을수상했다.주요연구분야는컴퓨터과학교육연구로써,컴퓨터과학교재를통한학습방법을연구한다.

역자:이정표
모바일브라우저개발부터클라우드서비스기획까지20년간다양한개발프로젝트에참여했으며,현재는SW와IT분야의기술조사와분석업무를하고있다.옮긴책으로는에이콘출판사에서펴낸『난독화,디지털프라이버시생존전략』(2017),『젠킨스마스터』(2018),『젠킨스블루오션시작하기』(2019),『린모바일앱개발』(2019),『알고리즘윤리』(2021),『배포자동화와지속적인도』(2022),『알고리듬으로생각하기』(2023)등이있다.

1장.해시테이블
__문제1:고유한눈송이
____문제설명
____문제단순화
____핵심부분풀이
____해법1:쌍비교
____해법2:작업량줄이기
__해시테이블
____해시테이블설계
____해시테이블사용이유
__문제2:복합어
____문제설명
____복합어식별
____해법
__문제3:철자검사
____문제설명
____해시테이블방식의적합성판단
____임시해법
__요약
__참고사항

2장.트리와재귀
__문제1:할로윈하울
____문제설명
____이진트리
____예제문제해결
____이진트리표현
____모든사탕모으기
____완전히다른해법
____최소경로이동
____입력받기
__재귀사용이유
__문제2:후손거리
____문제설명
____입력받기
____단일노드의후손의수
____모든노드의후손의수
____노드정렬
____정보출력
____main함수
__요약
__참고사항

3장.메모이제이션과동적프로그래밍
__문제1:버거마니아
____문제설명
____계획세우기
____최적해의특성
____해법1:재귀
____해법2:메모이제이션
____해법3:동적프로그래밍
__메모이제이션과동적프로그래밍
____1단계:최적해구조
____2단계:재귀해법
____3단계:메모이제이션
____4단계:동적프로그래밍
__문제2:구두쇠
____문제설명
____최적해의특성
____해법1:재귀
____main함수
____해법2:메모이제이션
__문제3:하키라이벌
____문제설명
____라이벌정보
____최적해의특성
____해법1:재귀
____해법2:메모이제이션
____해법3:동적프로그래밍
____공간최적화
__문제4:통과방법
____문제설명
____해법:메모이제이션
__요약
__참고사항

4장.그래프및너비우선탐색
__문제1:나이트추격
____문제설명
____최적이동
____최상의결과
____변덕스런해법
____시간최적화
__그래프와BFS
____그래프란?
____그래프와트리
____그래프와BFS
__문제2:로프오르기
____문제설명
____해법1:동작찾기
____해법2:리모델링
__문제3:책번역
____문제설명
____그래프작성
____BFS구현
____총비용
__요약
__참고사항

5장.가중치그래프의최단경로
__문제1:생쥐미로
____문제설명
____BFS이동
____가중치그래프의최단경로
____그래프작성
____다익스트라알고리즘구현
____두가지최적화
__다익스트라알고리즘
____다익스트라알고리즘의실행시간
____음수-가중치에지
__문제2:할머니집찾기
____문제설명
____인접행렬
____그래프작성
____이상한경로
____과제1:최단경로
____과제2:최단경로수
__요약
__참고사항

6장.이진탐색
__문제1:개미먹이기
____문제설명
____새로운형태의트리문제
____입력받기
____타당성시험
____해법찾기
__이진탐색
____이진탐색실행시간
____타당성결정
____정렬된배열탐색
__문제2:강건너기
____문제설명
____탐욕알고리즘
____타당성시험
____해법찾기
____입력받기
__문제3:삶의질
____문제설명
____전체사각형정렬
____이진탐색
____타당성시험
____좀더빠른타당성시험
__문제4:동굴문
____문제설명
____하위작업풀이
____선형탐색사용
____이진탐색사용
__요약
__참고사항

7장.힙과세그먼트트리
__문제1:수퍼마켓판촉행사
____문제설명
____해법1:배열의최댓값과최솟값
____최대-힙
____최소힙
____해법2:힙
__힙
____두가지응용사례
____데이터구조선택
__문제2:트립생성
____문제설명
____재귀를이용한트립출력
____레이블정렬
____해법1:재귀
____구간최대쿼리
____세그먼트트리
____해법2:세그먼트트리
__세그먼트트리
__문제3:두합
____문제설명
____세그먼트트리채우기
____세그먼트트리쿼리
____세그먼트트리업데이트
____main함수
__요약
__참고사항

8장.유니온파인드
__문제1:소셜네트워크
____문제설명
____그래프모델링
____해법1:BFS
____유니온파인드
____해법2:유니온파인드
____최적화1:크기별유니온
____최적화2:경로압축
__유니온파인드
____관계:세가지요구사항
____유니온파인드선택
____최적화
__문제2:친구와적
____문제설명
____확장:적
____main함수
____파인드와유니온
____SetFriends와SetEnemies
____AreFriends와AreEnemies
__문제3:서랍정리
____문제설명
____동등한서랍
____main함수
____파인드와유니온
__요약
__참고사항

후기

부록A.알고리즘실행시간
__제한시간의한계
__빅오표기법
____선형시간
____상수시간
____추가예제
____2차시간
____이책의빅오표기법

부록B.추가자료
__고유한눈송이:암시적연결리스트
__버거마니아:해법재구성
__나이트추격:이동인코딩
__다익스트라알고리즘:힙사용
____생쥐미로:힙을사용한추적
____생쥐미로:힙을사용한구현
__경로압축을압축하기
____1단계:삼항연산자제거
____2단계:할당연산자정리
____3단계:재귀이해

부록C문제출처

이책에서다루는내용

-체스게임을하는최적의방법과책을번역하는최적의방법을찾기위한너비우선검색알고리듬
-미로를빠져나갈수있는생쥐의수또는두위치사이의가장빠른경로의수를결정하는다익스트라알고리듬
-소셜네트워크의연결여부또는친구여부를결정하기위한유니온-파인드데이터구조
-매장판촉에서제공되는금액을결정하기위한힙데이터구조
-눈송이가고유한지여부를확인하거나사전에서복합어를식별하기위한해시테이블데이터구조

이책의대상독자

난이도높은문제를해결하는학습법을배우려는모든프로그래머를위한책이다.이책을통해다양한데이터구조와알고리듬,문제풀이에도움이되는유형및구현방법을배울수있다.이책의코드는전부C언어로작성됐으나C언어의기초는다루지는않는다.독자가C/C++에익숙하다면바로시작하는데어려움이없을것이다.그외에자바나파이썬등다른언어로프로그래밍한경험이있다면대부분의내용은읽으면서대략이해할수있을것이다.그래도1장을시작하기전에C언어의개요를복습한다면좀더도움이될것이다.특히,포인터와동적메모리할당에대해서는기존의프로그래밍경험에관계없이숙지해둘필요가있다.독자에게추천하는C언어책은K.N.킹의『CProgramming:AModernAccess,2ndEdition』(W.W.Norton&Company,2008)으로,C언어에익숙한사람에게도참고용으로서유용한책이다.

저자의말

기획단계에서최신의멋진알고리듬을설명하고기존의기법들과비교하는구성도고민했었다.설명을위주로하고실제알고리듬문제를접하지않으면금방기억에서잊힌다는단점을떠올릴수밖에없었다.이책은알고리듬기법을먼저설명하지않고,문제를먼저제시하는방식을사용한다.게다가제시되는문제도상당히어려워서기존의방법으로는쉽게풀수없다.즉,독자들이어려운문제를접하면서이미알고있는경험과문제해결에필요한지식을연결시키는방식으로기술을습득할수있다.아마도기존의교과서에서봤던문제는찾을수없을것이다.행렬을곱하거나피보나치수열을계산하는최적방법에대한내용도없다.또한,하노이탑문제를풀일도없을거라고장담한다.다른많은훌륭한교과서들이이런문제를다루고있는것이현실이지만,과연그런종류의문제에흥미를느끼는지는의문이다.

오히려독자들이접해보지못한새로운문제를활용하려고한다.해마다수천명의사람들이프로그래밍경진대회에참가한다.대회를준비하는주최측은참가자들이기존답안을다시쓰거나구글검색만이용해서풀수없도록새로운문제를준비한다.새로운문제는기존의문제를새로운상황에맞도록변형하며,참가자들이새로운해법을찾아내도록도전하고흥미를유발한다.이런문제를푸는데필요한프로그래밍과컴퓨터지식은끝이없다.제대로된문제를고를수만있다면실컷배울수있다.가장기초적인정의를떠올려보자.자료구조,즉데이터구조란데이터를구조화해연산을빠르게하는방법을말한다.알고리듬은문제해결방법을순서대로나열한것이다.가끔은정교한데이터구조없이도빠른알고리듬을만들어낼수있다.그러나올바른데이터구조를사용한다면알고리듬의속도를획기적으로향상시킬수있다.

이책을열심히공부하면실력있는프로그래머가될수는있지만,그것이필자의목표는아니다.프로그래밍경진대회의문제풀이를통해데이터구조와알고리듬을재미있게가르치고배우는것을마음에두고썼다.이책에서배울만한것이나,재미난것을찾았다면소감을이메일로보내주길바란다.