퍼즐로 이해하는 알고리즘

예제를 통해 문제를 풀고, 만들고, 해결하며 배우는 생각하는 힘

오츠키 겐스케 지음 | 윤모린 옮김

비제이퍼블릭 2023년 10월 20일 출간 종이책 : 2023년 10월 20일 출간

작품소개

책소개

다양한 문제를 해결하기 위해선 적절한 알고리즘을 판단하거나 때로는 직접 해결하는 능력이 필요합니다. 지식을 온전히 내 것으로 만들기 위해선 직접 실천해보는 것도 중요합니다. 본서에서는 ‘템퍼즐’ ‘스도쿠’ ‘4×4 오델로’ 등 다양한 퍼즐의 풀이를 설명하며, 효율적인 알고리즘을 즐겁게 배워 나갈 수 있습니다. 각 알고리즘 개요는 그림으로 충분히 해설했으며 수학적 해법 등 심화 내용도 담았습니다. 프로그래밍 경시대회에 도전하고 싶은 분들에게도 많은 도움이 될 것입니다.

목차

들어가며
이 책에 대해
감사의 말
퍼즐 베타리더 추천사

제1장 알고리즘 입문
1-1 텐퍼즐(ten puzzle): 완전 탐색
텐퍼즐
퍼즐에 도전
텐퍼즐을 푸는 알고리즘
[칼럼] 스택과 큐 Part 1
[칼럼] 컴퓨터의 계산 능력
텐퍼즐 프로그램 적용
텐퍼즐 파고들기
정리
퍼즐 정답
[칼럼] 알고리즘과 프로그램의 차이
[더 알아보기] 트럼프 게임 ‘사칙’

1-2 고마치잔: 재귀 함수
고마치잔
직접 풀어보기
고마치잔을 푸는 알고리즘
[칼럼] 재귀 호출의 효율화
고마치잔 프로그램 적용
정리
[더 알아보기] 고마치잔 문제 만들기

1-3 충식산: 가지치기
충식산
퍼즐에 도전
충식산을 푸는 알고리즘
가지치기
[칼럼] 조합 폭발
충식산 프로그램 요소 준비
충식산 프로그램 적용
정리
퍼즐 정답
[더 알아보기] 충식산 만들기

제2장 그래프 알고리즘
2-1 스도쿠: 깊이 우선 탐색 1
스도쿠
스도쿠의 수 소개
그래프
[칼럼] 쾨니히스베르크 다리와 4색 정리
스도쿠를 푸는 알고리즘
스도쿠 프로그램의 요소 준비
스도쿠 프로그램 적용
고속화를 위한 궁리
정리
퍼즐 정답
[칼럼] 스도쿠의 최소 힌트 개수는 17
[더 알아보기] 스도쿠 제작: 언덕 오르기 방법

2-2 복면산: 깊이 우선 탐색 2
복면산
[칼럼] 퍼즐 거장 소개 1: 듀드니
퍼즐에 도전
[칼럼] 단어 퍼즐로 복면산 만들기
복면산 프로그램 적용
복면산을 만드는 알고리즘
리스트업 방식에 따른 복면산 메이커 적용
와일드카드 방식에 따른 복면산 메이커 적용
정리
퍼즐 정답
[더 알아보기] 충식산과 복면산의 융합

2-3미로: 너비 우선 탐색
미로
[칼럼] 퍼즐이란 무엇인가?
미로와 관련된 퍼즐
풀어볼 문제 설정
미로 프로그램 적용
[칼럼] 샘 로이드의 ‘해먹 퍼즐’
그래프상의 너비 우선 탐색
[칼럼] 스택과 큐 Part 2
기름 나누기 문제 응용
정리
퍼즐 정답
[더 알아보기] 바둑돌 줍기

제3장 심화 알고리즘
3-1 15퍼즐: 반복적 깊이 증가 A*
15퍼즐
[칼럼] 샘 로이드의 ‘14-15퍼즐’15퍼즐
직접 풀어보기
[칼럼] 일반적인 15퍼즐
15퍼즐 프로그램 방침
반복 심화 깊이 우선 탐색
반복적 깊이 증가 A
15퍼즐 프로그램 적용
15퍼즐 프로그램
정리
[칼럼] 루빅스 큐브의 신의 수(God’s Number)

3-2 4×4 오델로: 게임 탐색
4×4 오델로
‘게임을 푼다’는 것
각 게임의 분석 상황
직접 풀어보기
게임 해석을 그래프 탐색으로 생각한다
게임 탐색 적용
4×4 오델로 프로그램 적용
정리

3-3 편집 거리: 동적 계획법
편집 거리
퍼즐에 도전
[칼럼] 편집 거리의 실제 응용
편집 거리를 그래프로 나타내기
동적 계획법
편집 거리 프로그램 적용
[칼럼] 알고리즘의 시간 복잡도
정리
퍼즐 정답
[칼럼] 다익스트라 알고리즘

3-4 도미노 채우기: 매칭
도미노 채우기
[칼럼] 퍼즐 거장 소개 2: 로이드
직접 풀어보기
[칼럼] 테트로미노
이분 매칭 문제로 귀착
이분 매칭 문제 해법
도미노 채우기 프로그램 적용
정리

마치며
북가이드
찾아보기

출판사 서평

“생각의 힘을 키우는 가장 좋은 방법”
퍼즐은 논리적 사고로 여러 번의 시행착오를 거쳐 즐겁게 풀어내는 문제입니다. 오래전부터 전 세계에서 머리를 쓰는 지능형 게임으로 사랑받았습니다. 찬찬히 생각에 몰입할 때 가려졌던 문제 구조가 조금씩 보이기 시작해 마침내 답이 훤히 보이는 재미, 아무리 머리를 굴려도 종잡을 수 없던 답이 궁리를 거듭한 끝에 섬광처럼 번뜩일 때의
기쁨. 퍼즐은 끝까지 포기하지 않은 사람에게 값진 성취감을 선사합니다.

한편 알고리즘은 문제를 푸는 일종의 도구입니다. 우리는 알고리즘의 힘을 빌려 수많은 문제를 해결합니다. 내비게이션은 ‘현 위치에서 목적지로 가는 경로를 찾아’ 문제를 해결하고, diff 명령어는 ‘주어진 두 문서의 내용을 비교’해 문제를 풉니다. 방법에 상관없이 ‘같은 방법으로’ 풀고자 하는 문제의 답을 찾아낸다는 점이 알고리즘의 위대한 특징입니다. 스도쿠를 푸는 알고리즘은 바르게 적용하기만 하면 프로그램에 어떤 스도쿠 문제를 입력하든 답을 출력합니다.

이 책에서는 퍼즐 프로그램을 만들어보면서 알고리즘으로 사고하는 능력을 즐겁게 연마합니다. 각 절은 다양한 퍼즐을 소개하며 시작합니다. 먼저 퍼즐을 손으로 풀어보며 흥미롭게 두루두루 살펴봅니다. 충식산, 스도쿠, 오델로 등 예전부터 널리 알려진 퍼즐은 단지 재미만이 아니라 알고리즘으로 사고하는 힘을 기르는 데 도움이 되는 요소가 여럿 있습니다. 가령 스도쿠를 풀 때 ‘이 칸에는 이 수가 들어올 수 없다’, ‘이 수는 이 칸에 넣을 수 없다’ 같은 생각을 하는 분이 많을 겁니다. 이러한 방식을 알고리즘 세계에서는 ‘탐색 가지치기’라 합니다. 퍼즐을 풀고 프로그램을 적용하다 보면 알고리즘적 사고력도 자연스럽게 배양됩니다.

이 책에 제시한 프로그램에는 퍼즐을 푸는 데 필요한 최소한의 기능만 담았습니다. 고속화, 기능 추가, 예외 처리 등 다양한 방법으로 프로그램을 개선해 여러분만의 독자적인 프로그램을 만들어보기를 바랍니다.

이 책을 추천합니다.
- 재미있게 알고리즘을 배우고 싶은 사람
- 경기 프로그래밍에 흥미가 있는 사람
- 생각의 힘을 키우고 싶은 사람

작가정보

저자(글) 오츠키 겐스케

2014년 도쿄대학교 대학원 정보과학기술대학원 석사과정 수료. 현재 주식회사 NTT 데이터 수리 시스템 고문, 주식회사 아르고식(공동 창업) 집행임원. 알고리즘을 비롯한 컴퓨터 과학의 여러 분야의 계몽 활동에 종사하고 있고, 수리 최적화 및 머신러닝을 활용한 수리 컨설팅 업무 경험도 다수 있다. 저서로는 『問題解決力を鍛える!アルゴリズムとデータ構造』（講談社，2020）가 있다.

번역 윤모린