알고리즘의 기초를 퍼즐로 배우자
프로그래밍이란 말을 들으면 코드를 만들어내는 코딩만 떠올리기 쉽지만 그에 못지않게 문제를 해결할 수 있는 알고리즘 능력 역시 중요하다. 알고리즘이란 문제를 이해하고 그에 맞는 해결법을 떠올리게 하는 문제 해결 능력을 말한다. 그렇다면 알고리즘 실력은 어떻게 기를 수 있을까? 이 책은 그에 대한 답으로 알고리즘 퍼즐을 소개한다.
이 책은 웹사이트나 각종 도서에서 많이 접할 수 있는 알고리즘 퍼즐 21가지를 통해 프로그래밍에 기초가 되는 다양한 알고리즘 유형을 소개한다. 각 퍼즐은 정렬, 탐색, 분할정복, 그래프 등 하나의 알고리즘을 주제로 그에 맞는 해결법을 함께 고민한다. 퍼즐을 보고 가장 먼저 떠올릴 수 있는 해결책에서 시작해 더 좋은 방법을 찾아 하나씩 개선해가며 최종적으로는 새로운 알고리즘까지 구현해 그 장점을 직접 확인하는 식이다. 코딩에 관한 설명은 파이썬으로 진행되며 각 퍼즐을 해결하는 데 필요한 데이터 구조와 프로그래밍 구조 같은 코딩 지식 역시 함께 설명해 파이썬에 대한 부담을 느끼지 않고 구현이 가능하도록 구성되어 있다. 또한 스도쿠나 카드 마술, 하노이의 탑처럼 한번쯤 들어보았을 주제들을 퍼즐로 만들어 프로그래밍적인 해결법을 고안하며 일상 속에 숨어있는 알고리즘에 대한 흥미를 자극한다.
알고리즘 능력에 대한 관심도는 점점 높아지고 있다. 기업에서 개최하는 알고리즘 대회의 수는 점점 늘어나고 있으며 중/고등 소프트웨어 교육에서도 학생들의 문제 해결 능력과 알고리즘 설계 능력 향상을 목표로 잡고 있다. 단어만 봐선 어려울 것이란 생각이 먼저 드는 알고리즘이지만 이 책을 따라 21개의 퍼즐을 해결해나가다 보면 어느새 그에 대한 관심은 물론 실력도 함께 늘어 있을 것이다.
저자 소개
저자 : SRINI DEVADAS
MIT 전기공학과와 컴퓨터공학과의 교수를 겸임하고 있으며, MIT에서 MacVicar 펠로우를 수여받았습니다. 이 책은 실제 MIT에서 수업하는 내용을 정리한 것으로서, 유튜브의 MIT OpenCourseWare에 있는 영상을 통해 저자의 강의를 볼 수 있습니다.
목 차
퍼즐 01_ 모두 똑같이 만들기
1-1 연이어 서있는 마음이 통하는 사람들 찾기
1-2 문자열, 리스트 그리고 튜플
1-3 알고리즘을 코드로
1-4 코드 최적화
1-5 리스트의 생성과 수정
1-6 영역
1-7 알고리즘 최적화
1-8 한 번에 찾아내는 알고리즘
1-9 알고리즘 활용
퍼즐 02_ 파티에 참석하기 가장 좋은 시간
2-1 시간 확인하고 다시 또 확인하기
2-2 똑똑한 시간 확인 방법
2-3 정렬의 대표주자
퍼즐 03_ 다른 사람의 마음 읽기
3-1 조수 역할 코드 작성하기
3-2 마술사 역할의 코드 작성하기
3-3 혼자 놀기의 진수 - 트릭의 달인 되기
3-4 데이터 인코딩
3-5 네 개 카드의 트릭
퍼즐 04_ 여왕님들, 떨어지세요
4-1 체계적인 탐색
4-2 2차원 리스트/배열 체스판
4-3 1차원 리스트/배열의 체스판
4-4 완전 탐색
퍼즐 05_ 제발 유리 구슬이 깨지길
5-1 두 개의 구슬을 가지고 효율적으로 탐색하기
5-2 d개의 구슬을 가지고 효율적으로 탐색하기
5-3 두 개의 구슬로 실험 횟수 줄이기
퍼즐 06_ 가짜를 찾아라
6-1 분할 정복
6-2 반복적 분할 정복
6-3 3진수 표기법
6-4 그 외 유명한 저울질 퍼즐
퍼즐 07_ 제곱근 구하기
7-1 반복적 검색
7-2 구간 이분 탐색
7-3 이산 이분 탐색
7-4 삼분 탐색?
퍼즐 08_ 누가 저녁 파티에 오지 않게 될까?
8-1 첫 시도
8-2 항상 가장 많은 경우 선택하기
8-3 모든 조합 생성하기
8-4 친하지 않는 조합 제거하기
8-5 최대 조합 고르기
8-6 메모리 사용량 최적화하기
8-7 알고리즘 활용
퍼즐 09_ 영재 발굴단
9-1 조합 하나씩 만들고 테스트하기
9-2 재능이 모자란 조합 결정하기
9-3 알고리즘 활용
퍼즐 10_ 너무 많은 여왕님들
10-1 재귀적인 최대공약수
10-2 재귀적인 피보나치 수열
10-3 재귀적인 N-퀸
10-4 재귀 적용하기
퍼즐 11_ 정원에 타일을 깔아주세요
11-1 병합 정렬
11-2 병합 정렬 실행과 분석
11-3 기저 사례, 2 × 2 정원
11-4 재귀 과정
11-5 리스트 컴프리헨션 기초
11-6 예쁘게 출력하기
11-7 다른 종류의 타일 놓기 퍼즐
퍼즐 12_ 브라흐마의 탑
12-1 TOH의 재귀적 풀이
12-2 ATOH의 재귀적 풀이
12-3 그레이 코드와의 관계
퍼즐 13_ 못난 기술자
13-1 피벗을 사용한 분할 정복
13-2 정렬과의 관계
13-3 제자리 분할
13-4 정렬 매니아
퍼즐 14_ 다시는 스도쿠를 하고 싶지 않아요
14-1 재귀적인 스도쿠 풀이
14-2 재귀 탐색 중의 암시
14-3 스도쿠 퍼즐의 어려움
퍼즐 15_ 잔돈 내는 방법이 얼마나 있을까요?
15-1 재귀적 지폐 선택
15-2 중복 제거
15-3 가장 적은 수의 화폐만 사용하도록 변경하기
퍼즐 16_ 욕심은 옳습니다
16-1 탐욕적 접근
16-2 규칙 - 가장 시간이 짧은 수업
16-3 규칙 - 가장 먼저 시작하는 수업
16-4 규칙 - 가장 충돌이 적은 수업
16-5 규칙 - 가장 먼저 끝나는 수업
16-6 탐욕법은 언제 좋을까요?
퍼즐 17_ 애너그램(Anagram) 매니아
17-1 한 번에 한 개의 애너그램 그룹 찾기
17-2 정렬을 사용해서 애너그램 그룹 만들기
17-3 해시를 사용해서 애너그램 그룹 만들기
17-4 딕셔너리
17-5 해시 테이블
퍼즐 18_ 제 기억은 정확합니다
18-1 재귀적 방법
18-2 메모이제이션
18-3 예외 피하기
18-4 동적 프로그래밍
퍼즐 19_ 기억에 남을 주말
19-1 칸막이 세우기
19-2 이분 그래프 여부 확인
19-3 그래프 표현
19-4 그래프 색칠
퍼즐 20_ 여섯 단계 분리
20-1 너비 우선 탐색
20-2 집합
20-3 너비 우선 탐색에서 집합 사용하기
20-4 역사
퍼즐 21_ 질문에도 돈을 내야 합니다
21-1 딕셔너리를 사용한 이분 탐색 트리
21-2 딕셔너리 표현을 사용한 이분 탐색 트리의 연산
21-3 객체 지향 프로그래밍 스타일의 이분 탐색 트리
21-4 퍼즐로 돌아가기: 알고리즘
21-5 즐을 풀기 위한 코드
21-6 데이터 구조 비교
