홈앤서비스 SK BROADBAND

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

다양한 문제를 해결하기 위해선 적절한 알고리즘을 판단하거나 때로는 직접 해결하는 능력이 필요합니다. 지식을 온전히 내 것으로 만들기 위해선 직접 실천해보는 것도 중요합니다. 본서에서는 ‘템퍼즐’ ‘스도쿠’ ‘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: 로이드
직접 풀어보기
[칼럼] 테트로미노
이분 매칭 문제로 귀착
이분 매칭 문제 해법
도미노 채우기 프로그램 적용
정리

마치며
북가이드
찾아보기