퍼즐로 이해하는 알고리즘

제목 퍼즐로 이해하는 알고리즘

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

저자 오츠키 겐스케

역자 윤모린

출판사 비제이퍼블릭(BJ퍼블릭)

출간/배본가능일 2023년 10월 20일

정가 22,200원

페이지 304쪽

판형 148*210

ISBN 979-11-6592-236-8 (93000)

 

관련분류 – 카테고리 분류

국내도서 > IT모바일 > 컴퓨터 공학 > 자료구조/알고리즘

국내도서 > IT 모바일 > 프로그래밍 언어 > 프로그래밍 언어 기타

국내도서 > 건강 취미 > 퍼즐/스도쿠/기타

국내도서 > 청소년 > 청소년 수학/과학

국내도서 > 인문 > 논리학

 

이 상품의 태그

#기초수학 #C++ #알고리즘 #퍼즐 #스도쿠 #오셀로 #오델로

 

책 소개

“생각의 힘을 키우는 가장 좋은 방법, 다양한 퍼즐 즐겁게 배우기!”

다양한 문제를 해결하기 위해선 적절한 알고리즘을 판단하거나 때로는 직접 해결하는 능력이 필요합니다. 지식을 온전히 내 것으로 만들기 위해선 직접 실천해보는 것도 중요합니다. 본서에서는 ‘템퍼즐’ ‘스도쿠’ ‘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: 로이드

직접 풀어보기

[칼럼] 테트로미노

이분 매칭 문제로 귀착

이분 매칭 문제 해법

도미노 채우기 프로그램 적용

정리

 

마치며

북가이드

찾아보기

 

저자 소개

오츠키 켄스케

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

 

출판사 리뷰

“생각의 힘을 키우는 가장 좋은 방법”

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

기쁨. 퍼즐은 끝까지 포기하지 않은 사람에게 값진 성취감을 선사합니다.

 

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

 

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

 

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

 

이 책을 추천합니다.

- 재미있게 알고리즘을 배우고 싶은 사람

- 경기 프로그래밍에 흥미가 있는 사람

- 생각의 힘을 키우고 싶은 사람

 

책 보러 가기

- 예스24: https://www.yes24.com/Product/Goods/123038111

- 알라딘: https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=327007915

- 교보문고: https://product.kyobobook.co.kr/detail/S000210544869

 

[도서 오탈자 제보 & 질의응답 게시판 바로가기]