문제풀이로 완성하는 알고리즘+자료구조

프로그래밍 경진대회 & 코딩 테스트 대비를 위한 77가지 핵심 기법

요네다 마사타카 지음 | 김모세 옮김

위키북스 2024년 10월 25일 출간 국내도서 : 2024년 10월 15일 출간

작품소개

책소개

'코딩 테스트, 프로그래밍 경진대회'에 필요한 기술을 한 권에 담았습니다!

'코딩 테스트'는 지원자의 프로그래밍 능력을 평가하기 위해 기업이나 조직에서 실시하는 시험입니다. '프로그래밍 경진대회'는 문제를 해결하며 프로그래밍 능력을 겨루는 대회입니다. 이 책에서는 코딩 테스트나 프로그래밍 경진대회에 필요한 알고리즘, 데이터 구조, 사고 기법을 자세히 설명합니다.

이 책에서는 초급자도 쉽게 이해할 수 있도록 풀컬러 이미지를 사용해 알기 쉽게 설명했으며, 익힌 지식을 확실히 습득할 수 있도록 150개 이상의 예제와 연습문제를 수록하고 해답과 해설을 제공합니다. 또한, 모든 연습문제는 채점 시스템을 통해 프로그래밍이 올바른지 자동으로 확인할 수 있어 효율적으로 학습할 수 있습니다.

코딩 테스트에 합격하고자 하는 사람, 프로그래밍 경진대회에서 좋은 성적을 내고 싶은 사람, 알고리즘과 자료구조를 본격적으로 배우고 싶은 사람, 프로그래밍 능력을 좀 더 향상시키고 싶은 사람들을 위한 충실한 참고서입니다.

★ 이 책의 특징 ★

◎ 코딩 테스트, 프로그래밍 경진대회에 필요한 77가지 핵심 기술을 망라
◎ 320개 이상의 풀컬러 그림으로 이해하기 쉽게 설명
◎ 지식을 습득할 수 있는 153개의 연습, 응용문제와 해답, 해설 제공
◎ 모든 문제를 '자동 채점 시스템'으로 확인 가능
◎ 새로운 경향의 '휴리스틱 최적화'도 설명

목차

▣ 들어가기: 프로그래밍 경진대회 입문
프로그래밍 경진대회란
콘테스트의 종류
프로그래밍 경진대회에서 요구되는 것
책의 진행 방식

▣ 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

작가정보

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

2002년생. 2021년 츠쿠바대학 부속 코마바 고등학교를 졸업하고 현재 도쿄대학에 재학 중이다. 프로그래밍 경진대회에서는 'E869120'이라는 이름으로 활약하고 있다. 일본 최대의 프로그래밍 경진대회 사이트 '앳코더(AtCoder)'에서 최고 등급인 붉은색 칭호를 보유하고 있으며, 2020년까지 국제정보올림피아드(IOI)에서 금메달을 세 번 획득했다. 또한, Qiita에 다수의 글을 게시하고 프로그래밍 경진대회 중상급자를 위한 문제집 '프로그래밍 경진대회 전형 90문제'를 제작하는 등 알고리즘과 프로그래밍 경진대회 보급 활동도 하고 있다. 저서로는 《문제 해결을 위한 알고리즘 with 수학》 (위키북스, 2023)이 있다.

번역 김모세

대학 졸업 후 소프트웨어 엔지니어, 소프트웨어 품질 엔지니어, 애자일 코치 등 다양한 부문에서 소프트웨어 개발에 참여했다. 재미있는 일, 나와 조직이 성장하도록 돕는 일에 보람을 느껴 2019년부터 번역을 시작했다. 옮긴 책으로는 『타입스크립트, 리액트, Next.js로 배우는 실전 웹 애플리케이션 개발(위키북스)』 『파이썬과 자바스크립트로 배우는 OpenAI 프로그래밍(제이펍)』 『애자일 개발의 기술 2판(에이콘)』 『추천 시스템 입문(한빛미디어)』 『웹 개발 리터러시(정보문화사)』 등이 있다.