문제 해결을 위한 알고리즘 with 수학
도서명:문제 해결을 위한 알고리즘 with 수학
저자/출판사:요네다 마사타카/위키북스
쪽수:628쪽
출판일:2023-09-26
ISBN:9791158394653
목차
▣ 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장 마치며
__마치며
