책소개
'코딩 테스트, 프로그래밍 경진대회'에 필요한 기술을 한 권에 담았다!
'코딩 테스트'는 지원자의 프로그래밍 능력을 평가하기 위해 기업이나 조직에서 실시하는 시험이다. '프로그래밍 경진대회'는 문제를 해결하며 프로그래밍 능력을 겨루는 대회이다. 이 책에서는 코딩 테스트나 프로그래밍 경진대회에 필요한 알고리즘, 데이터 구조, 사고 기법을 자세히 설명한다.
이 책에서는 초급자도 쉽게 이해할 수 있도록 풀컬러 이미지를 사용해 알기 쉽게 설명했으며, 익힌 지식을 확실히 습득할 수 있도록 150개 이상의 예제와 연습문제를 수록하고 해답과 해설을 제공한다. 또한, 모든 연습문제는 채점 시스템을 통해 프로그래밍이 올바른지 자동으로 확인할 수 있어 효율적으로 학습할 수 있다. 코딩 테스트에 합격하고자 하는 사람, 프로그래밍 경진대회에서 좋은 성적을 내고 싶은 사람, 알고리즘과 자료구조를 본격적으로 배우고 싶은 사람, 프로그래밍 능력을 좀 더 향상시키고 싶은 사람들을 위한 충실한 참고서이다.
저자소개
2002년생. 2021년 츠쿠바대학 부속 코마바 고등학교를 졸업하고 현재 도쿄대학에 재학 중이다. 프로그래밍 경진대회에서는 'E869120'이라는 이름으로 활약하고 있다. 일본 최대의 프로그래밍 경진대회 사이트 '앳코더(AtCoder)'에서 최고 등급인 붉은색 칭호를 보유하고 있으며, 2020년까지 국제정보올림피아드(IOI)에서 금메달을 세 번 획득했다. 또한, Qiita에 다수의 글을 게시하고 프로그래밍 경진대회 중상급자를 위한 문제집 '프로그래밍 경진대회 전형 90문제'를 제작하는 등 알고리즘과 프로그래밍 경진대회 보급 활동도 하고 있다. 저서로는 『문제 해결을 위한 알고리즘 with 수학』 (위키북스, 2023) 등이 있다.
목차
▣ 들어가기: 프로그래밍 경진대회 입문
프로그래밍 경진대회란
콘테스트의 종류
프로그래밍 경진대회에서 요구되는 것
책의 진행 방식
▣ 01장: 알고리즘과 계산량
1.0 _ 알고리즘과 계산량
1.1 _ 도입 문제
1.2 _ 완전 탐색 (1)
1.3 _ 완전 탐색 (2)
1.4 _ 2진법
1.5 _ 도전 문제
칼럼 1 _ 비트 연산
칼럼 2 _ 비트 완전 탐색
▣ 02장: 누적 합
2.0 _ 누적 합이란?
2.1 _ 1차원 누적 합 (1)
2.2 _ 1차원 누적 합 (2)
2.3 _ 2차원 누적 합 (1)
2.4 _ 2차원 누적 합 (2)
2.5 _ 도전 문제
칼럼 3 _ 알고리즘에서 사용하는 수학
▣ 03장: 바이너리 서치
3.0 _ 바이너리 서치란
3.1 _ 배열의 바이너리 서치
3.2 _ 답에서 바이너리 서치
3.3 _ 자벌레 알고리즘
3.4 _ 이분 완전 열거
3.5 _ 도전 문제
▣ 04장: 동적 계획 알고리즘
4.0 _ 동적 계획 알고리즘이란
4.1 _ 동적 계획 알고리즘의 기본
4.2 _ 동적 계획 알고리즘 복원
4.3 _ 2차원 DP(1): 부분합 문제
4.4 _ 2차원 DP(2): 배낭 문제
4.5 _ 2차원 DP(3): 최장 공통 부분열 문제
4.6 _ 2차원 DP(4): 구간 DP
4.7 _ 전이 형식 개선
4.8 _ 비트 DP
4.9 _ 최장 증가 부분열 문제
4.10 _ 도전 문제
▣ 05장: 수학적 문제
5.0 _ 수학적 문제에 관해
5.1 _ 소수 판정
5.2 _ 최대공약수
5.3 _ 나머지 계산(1): 기본
5.4 _ 나머지 계산(2): 반복 제곱
5.5 _ 나머지 계산(3): 나눗셈
5.6 _ 포함-배제 원리
5.7 _ 게임(1): 필승 알고리즘
5.8 _ 게임(2): Nim
5.9 _ 게임(3): Grundy 수
5.10 _ 도전 문제
▣ 06장: 고찰 테크닉
6.0 _ 고찰 테크닉 입문
6.1 _ 홀짝을 생각하라
6.2 _ 더한 횟수를 생각하라
6.3 _ 상한 값을 생각하라
6.4 _ 한 수 앞을 생각하라
6.5 _ 개수를 생각하라
6.6 _ 뒤에서부터 생각하라
6.7 _ 값을 제한한 뒤 완전 탐색
6.8 _ 문제를 바꿔서 표현하라
6.9 _ 데이터 보유 방법을 개선하라
6.10 _ 불변량에 착안하라
▣ 07장: 휴리스틱
7.0 _ 휴리스틱 계열 콘테스트란
7.1 _ 탐욕 알고리즘
7.2 _ 국소 탐색 알고리즘
7.3 _ 담금질 알고리즘
7.4 _ 빔 서치
7.5 _ 도전 문제
칼럼 4 _ 재귀 함수
▣ 08장: 데이터 구조와 쿼리 처리
8.0 _ 데이터 구조란
8.1 _ 스택
8.2 _ 큐
8.3 _ 우선순위 큐
8.4 _ 연상 배열
8.5 _ 집합 관리(C++)
8.6 _ 문자열의 해시
8.7 _ 더블링
8.8 _ 세그먼트 트리: RMQ
8.9 _ 세그먼트 트리: RSQ
8.10 _ 도전 문제
▣ 09장: 그래프 알고리즘
9.0 _ 그래프란
칼럼 5 _ 그래프 관련 용어
9.1 _ 그래프 구현 방법
9.2 _ 깊이 우선 탐색
9.3 _ 너비 우선 탐색
9.4 _ 데이크스트라 알고리즘
9.5 _ 트리에 대한 동적 계획 알고리즘
9.6 _ Union-Find 트리
9.7 _ 최소 전역 트리 문제
9.8 _ 최대 플로 문제
9.9 _ 이분 매칭 문제
9.10 _ 도전 문제
칼럼 6 _ Bellman-Ford 알고리즘
칼럼 7 _ Warshall-Floyd 알고리즘
▣ 10장: 종합 문제
10.0 _ 프로그래밍 경진대회 대응 방법
10.1 _ 종합 문제(1)
10.2 _ 종합 문제(2)
10.3 _ 종합 문제(3)
10.4 _ 종합 문제(4)
10.5 _ 종합 문제(5)
10.6 _ 종합 문제(6)
10.7 _ 종합 문제(7)
능력 시험 문제
▣ 마무리: 실력을 더욱 향상하려면
다양한 콘테스트에 참가하자
기출 문제를 풀자
라이브러리를 준비하자
‘프로그래밍 경진대회 전형 90문제’로의 초대
숙달된다는 것
▣ 부록
해답해설1장: 알고리즘과 계산량
해답해설2장: 누적 합
해답해설3장: 바이너리 서치
해답해설4장: 동적 계획 알고리즘
문제1~10: 능력 시험 문제 풀이 Part A
문제11~20: 능력 시험 문제 풀이 Part B
