문제 해결을 위한 알고리즘 with 수학 : 알고리즘 문제 해결에 꼭 필요한 수학적 지식과 사고력

요네다마사타카

저자:요네다마사타카
2002년출생,2021년쓰쿠바대학부속고마바고등학교를졸업하고,현재도쿄대학에재학중이다.프로그래밍대회에서'E869120'라는이름으로활약하고있다.일본최대의프로그래밍대회사이트'앳코더(AtCoder)'에서최고등급인붉은색호칭을획득하고있으며,2018~2020년에는국제정보올림픽(IOI)에서금메달을3번획득했다.또한알고리즘관련연구에서도일본학생과학상을받았으며,MATHCon등에서다양한실적을남기고있다.이외에도Qiita에서〈RedCoder가알려주는프로그래밍대회공략가이드라인〉등을집필하고있으며,AtCoder에서수천명이참가하는'경쟁프로전형90문(競プロ典型90問)'을운영하는등알고리즘과프로그래밍대회보급활동에도힘쓰고있다.

역자:윤인성
어쩌다가책을집필/번역하기시작해서,지금까지계속해서집필/번역하고있다.현재직업특성상집에서나갈이유가별로없다는것에굉장히만족하고있다.오전에는커피,오후에는홍차를마신다.요리,피아노,기타,작곡,그림,스컬핑등의취미를갖고있다.《HTML5웹프로그래밍입문》《혼자공부하는파이썬》《모던웹을위한HTML5+CSS3바이블》등을저술했으며《나의첫블렌더》《프로일러스트레이터가알려주는캐릭터채색테크닉[결정판]》《러닝스쿨!한권으로끝내는HTML+CSS웹디자인입문》《최신표준HTML+CSS디자인》《파이썬을이용한머신러닝,딥러닝실전개발입문》《파이썬을이용한웹크롤링과스크레이핑》등을번역하였다.

▣1장:알고리즘과수학의관계
1.1알고리즘이란?
__1.1.1알고리즘의예①:하나씩더하기
__1.1.2알고리즘의예②:변형해서한번에계산하기
__1.1.3다양한문제를풀때도움이되는알고리즘
__1.1.4알고리즘개선하기
1.2왜알고리즘에수학이필요할까?
__1.2.1알고리즘의이해와수학
__1.2.2알고리즘성능평가와수학
__1.2.3이론적사고력과수학
1.3이책의구성/이책을읽는방법
__1.3.1이책의구성
__1.3.2이책을학습하는순서
__1.3.3사전지식
__1.3.4예제,연습문제,최종확인문제
__1.3.5이책의소스코드
__1.3.6이책을모두읽은후에
__1.3.7주의사항
1.4이책에서다루는알고리즘
1.5이책에서다루는수학적지식과수학적접근방법

▣2장:알고리즘을위한기본적인수학
2.1수의분류,문자식,2진법
__2.1.1정수,유리수,실수
__2.1.2문자식
__2.1.3이책의문제형식①
__2.1.4이책의문제형식②
__2.1.5이책의문제형식③
__2.1.62진법이란?
__2.1.72진법→10진법으로변환하기
__2.1.83진법등에대해서
__2.1.910진법을2진법등으로변환하기
2.2기본적인연산과기호
__2.2.1나머지(mod)
__2.2.2절댓값(abs)
__2.2.3제곱(pow)
__2.2.4루트(sqrt)
__2.2.5비트연산을배우기전에:논리연산
__2.2.6비트연산의흐름
__2.2.7비트연산의예①:AND
__2.2.8비트연산의예②:OR
__2.2.9비트연산의예③:XOR
__2.2.10비트연산구현하기
__2.2.113개이상의AND,OR,XOR
__2.2.12비트연산의예④:왼쪽시프트와오른쪽시프트
2.3다양한함수
__2.3.1함수란?
__2.3.2함수의예:물통에넣는물의양
__2.3.3함수그래프를살펴보기전에:좌표평면이란?
__2.3.4함수그래프
__2.3.5다양한함수①:일차함수
__2.3.6다양한함수②:이차함수
__2.3.7다양한함수③:다항식과다항식함수
__2.3.8지수함수를살펴보기전에:거듭제곱의확장
__2.3.9다양한함수④:지수함수
__2.3.10다양한함수⑤:로그함수
__2.3.11다양한함수⑥:바닥함수,천장함수,가우스기호
__2.3.12주의점:프로그래밍함수와의차이
__2.3.13desmos.com으로그래프그려보기
2.4계산횟수예측하기:전체탐색과이진탐색
__2.4.1도입:계산횟수가중요한이유
__2.4.2계산횟수란?
__2.4.3계산횟수의예①:정수시간
__2.4.4계산횟수의예②:선형시간
__2.4.5계산횟수의예③:전체탐색계산횟수
__2.4.6계산횟수의예④:전체탐색과지수시간
__2.4.7계산횟수의예⑤:이진탐색과로그함수
__2.4.8란다우의O표기법
__2.4.9복잡도와알고리즘의예
__2.4.10복잡도비교
__2.4.11복잡도와관련된주의사항
2.5추가적인기본수학지식
__2.5.1소수
__2.5.2최대공약수와최소공배수
__2.5.3팩토리얼(계승)
__2.5.4수열기본
__2.5.5집합기본
__2.5.6필요조건과충분조건
__2.5.7절대오차와상대오차
__2.5.8폐구간,반개구간,개구간
__2.5.9시그마기호
__2.5.10합의공식
__2.5.11이후에배우는새로운수학지식

▣3장:기본알고리즘
3.1소수판정법
__3.1.1단순한소수판정법
__3.1.2빠른소수판정방법
__3.1.3귀류법이란?
__3.1.4알고리즘의정당성증명하기
__3.1.5응용예:약수모두출력하기
3.2유클리드호제법
__3.2.1단순한알고리즘
__3.2.2효율적인알고리즘:유클리드호제법
__3.2.3유클리드호제법이작동하는이유
__3.2.4계산횟수가log로나오는이유
__3.2.53개이상의최대공약수
3.3경우의수와알고리즘
__3.3.1기본공식①:곱의법칙
__3.3.2기본공식②:곱의법칙확장
__3.3.3기본공식③:n개의대상을나열하는방법의수는n!
__3.3.4기본공식④:n개의대상중에서r개를나열하는방법은nPr
__3.3.5기본공식⑤:n개에서r개를선택하는방법은nCr
__3.3.6응용예①:물건구매경우의수
__3.3.7응용예②:같은색의카드조합하기
__3.3.8응용예③:전체탐색계산횟수
3.4확률기댓값과알고리즘
__3.4.1확률이란?
__3.4.2기댓값이란?
__3.4.3기댓값의선형성이란?
__3.4.4응용예①:2개의주사위
__3.4.5응용예②:두주사위문제일반화
__3.4.6응용예③:시험에서모든객관식문제찍기
3.5몬테카를로법:통계적접근방법
__3.5.1도입:동전던지기
__3.5.2몬테카를로법
__3.5.3응용예:원주율π계산하기
__3.5.4이론적으로검증하기전에①:평균과표준편차
__3.5.5이론적으로검증하기전에②:정규분포란?
__3.5.6몬테카를로법의이론적검증
3.6정렬과재귀
__3.6.1정렬이란?
__3.6.2선택정렬
__3.6.3재귀란?
__3.6.4재귀적정의의예:5!구하기
__3.6.5재귀함수의예①:팩토리얼
__3.6.6재귀함수의예②:유클리드호제법
__3.6.7재귀함수의예③:분할정복법으로합계구하기
__3.6.8재귀함수를구현할때의주의점
__3.6.9병합정렬
__3.6.10병합정렬의복잡도
__3.6.11그밖의정렬알고리즘
3.7동적계획법(점화식사용하기)
__3.7.1수열점화식이란?:점화식의예①:등차수열
__3.7.2점화식의예②:피보나치수열
__3.7.3점화식의예③:복잡한점화식
__3.7.4동적계획법이란?
__3.7.5동적계획법의예①:개구리의이동
__3.7.6동적계획법의예②:개구리의이동일반화
__3.7.7동적계획법의예③:계단을오르는방법
__3.7.8동적계획법의예④:냅색문제
__3.7.9그밖의대표적인문제

▣4장:고급알고리즘
4.1컴퓨터로도형문제풀기:계산기하학
__4.1.1벡터란?
__4.1.2벡터의덧셈과뺄셈
__4.1.3벡터의크기
__4.1.4벡터의내적
__4.1.5벡터의외적
__4.1.6예제:점과선분의거리
__4.1.7그밖의대표적인문제
4.2계차와누적합
__4.2.1계차와누적합의개념
__4.2.2예제1:입장인원계산하기
__4.2.3예제2:눈시뮬레이션
4.3뉴턴법:수치계산해보기
__4.3.1도입:미분의개념
__4.3.2접선과미분계수의관계
__4.3.3다양한함수의미분
__4.3.4미분의정확한정의
__4.3.5뉴턴법으로구해보기
__4.3.6뉴턴법일반화
__4.3.7수치계산과관련된대표적인문제
4.4에라토스테네스의체
__4.4.1에라토스테네스의체란?
__4.4.2적분기본
__4.4.3다양한함수의정적분
__4.4.4역수(1/x)의합
__4.4.5역수의합이log라는것증명하기
__4.4.6에라토네스의체의복잡도
4.5그래프를사용한알고리즘
__4.5.1그래프란?
__4.5.2다양한종류의그래프
__4.5.3그래프를사용해서표현할수있는실생활문제
__4.5.4그래프와관련된용어
__4.5.5그래프구현방법
__4.5.6깊이우선탐색
__4.5.7너비우선탐색
__4.5.8그밖의대표적인그래프알고리즘
4.6효율적인나머지계산
__4.6.1덧셈,뺄셈,곱셈과나머지계산
__4.6.2나누기도같은방법으로계산할수있을까?
__4.6.3나눗셈의나머지와모듈러역수
__4.6.4페르마의소정리로모듈러역수계산하기
__4.6.5나머지계산방법정리
__4.6.6예제1:피보나치수열의나머지
__4.6.7예제2:a의b제곱과나머지
__4.6.8예제3:경로의수에나머지적용하기
__4.6.9발전:RSA암호에대해서
4.7행렬의거듭제곱:피보나치수열빠르게계산하기
__4.7.1행렬이란?
__4.7.2행렬의덧셈과뺄셈
__4.7.3행렬의곱셈
__4.7.4행렬곱과관련된중요한성질
__4.7.5행렬의거듭제곱
__4.7.6피보나치수열의아래9자리숫자계산하기

▣5장:문제해결을위한수학적접근방법
5.1수학적접근방법이필요한이유
__5.1.1예제:말움직이기
__5.1.2해법도출하기
__5.1.3수학적접근방법이중요한이유
5.2규칙성생각하기
__5.2.1예제1:“2의N제곱”의일의자릿수
__5.2.2예제2:게임의승자구하기
5.3홀수짝수생각해보기
__5.3.1예제1:격자한붓긋기
__5.3.2예제2:수열의내용변경하기
5.4집합활용하기
__5.4.1여사건이란?
__5.4.2예제1:조건을만족하는카드조합
__5.4.3포함배제의원리
__5.4.4예제2:100칸계산하기
__5.4.5예제2의복잡도생각해보기
5.5경계생각하기
__5.5.1예제1:두숫자곱의최댓값
__5.5.2예제2:K개의점을감싸는직사각형
5.6작은문제로분해하기
__5.6.1예제1:쉼표의수세기
__5.6.2예제2:최대공약수의최댓값
5.7더해진횟수생각하기
__5.7.1도입:테크닉소개
__5.7.2예제1:차의합계구하기(Easy)
__5.7.3예제2:차의합계산하기(Hard)
__5.7.4예제3:덧셈피라미드(Easy)
__5.7.5예제4:덧셈피라미드(Hard)
__5.7.6예제5:상금기댓값구하기
5.8상한을생각하기
__5.8.1예제1:추의무게
__5.8.2예제2:나이의최댓값(Easy)
__5.8.3예제3:나이의최댓값(Hard)
5.9현재만생각하기:탐욕법
__5.9.1예제1:돈을지불하는방법
__5.9.2예제2:구간스케줄링문제
5.10그밖의수학적접근방법
__5.10.1오차와오버플로
__5.