문제 해결을 위한 알고리즘 with 수학

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

요네다 마사타카 지음 | 윤인성 옮김

위키북스 2024년 02월 15일 출간 국내도서 : 2023년 09월 26일 출간

작품소개

책소개

이 책은 수학과 알고리즘을 함께 공부할 수 있는 완벽한 가이드입니다. 알고리즘은 프로그래밍을 통해 문제를 해결하기 위한 필수 도구이지만, 이를 이해하고 활용하기 위해서는 수학적 지식과 사고력이 필요합니다. 이 책에서는 중등학교부터 대학 교양 수준의 수학적 지식을 다루며, 알고리즘 학습에 필요한 내용을 자세히 설명합니다. 풍부한 도표와 꼼꼼하게 배치된 200 문항의 예제와 연습문제를 제공하여 내용을 보다 쉽게 이해하고 익힐 수 있습니다. 파이썬 언어로 실습하며 깃허브에서 C, C++, 자바 코드도 제공합니다. 또한 연습 문제에 대한 자세한 해설도 실려 있어 학습 과정을 더욱 효율적으로 만들어 줍니다.

논리적인 사고력과 문제 해결 능력을 향상시키고자 하는 분, 알고리즘과 이를 뒷받침하는 수학에 대해 기초부터 배우고 싶은 프로그래머, 엔지니어, 그리고 알고리즘 시험을 준비하는 분들에게 많은 도움이 될 것입니다.

목차

▣ 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.6 2진법이란?
__2.1.7 2진법→10진법으로 변환하기
__2.1.8 3진법 등에 대해서
__2.1.9 10진법을 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.11 3개 이상의 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.13 desmos.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.5 3개 이상의 최대공약수
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.10.2 분배 법칙
__5.10.3 대칭성 활용
__5.10.4 일반성 유지하기
__5.10.5 조건 바꾸기
__5.10.6 상태 수 생각하기

최종 확인 문제
맺으며
권장 도서
참고 문헌
자동 채점 시스템 이용 방법

▣ 부록: 문제 풀이
2장 알고리즘을 위한 기본적인 수학
__연습 문제 2.1 해답
__연습 문제 2.2 해답
__연습 문제 2.3 해답
__연습 문제 2.4 해답
__연습 문제 2.5 해답
3장 기본 알고리즘
__연습 문제 3.1 해답
__연습 문제 3.2 해답
__연습 문제 3.3 해답
__연습 문제 3.4 해답
__연습 문제 3.5 해답
__연습 문제 3.6 해답
__연습 문제 3.7 해답
4장 고급 알고리즘
__연습 문제 4.1 해답
__연습 문제 4.2 해답
__연습 문제 4.3 해답
__연습 문제 4.4 해답
__연습 문제 4.5 해답
__연습 문제 4.6 해답
__연습 문제 4.7 해답
5장 문제 해결을 위한 수학적 접근 방법
__연습 문제 5.2 해답
__연습 문제 5.3 해답
__연습 문제 5.4 해답
__연습 문제 5.5 해답
__연습 문제 5.6 해답
__연습 문제 5.7 해답
__연습 문제 5.8 해답
__연습 문제 5.9 해답
__연습 문제 5.10 해답
6장 최종 확인 문제
__최종 확인 문제 1~5 해답
__최종 확인 문제 6~10 해답
__최종 확인 문제 11~15 해답
__최종 확인 문제 16~20 해답
__최종 확인 문제 21~25 해답
__최종 확인 문제 26~30 해답
7장 마치며
__마치며

작가정보

저자(글) 요네다 마사타카

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

번역 윤인성

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