알고리즘 퍼즐
더북(TheBook)

알고리즘 퍼즐

코딩은 괜찮아!
생각이 문제지!
코딩 능력이 아니라
알고리즘 사고력이 필요하다
문제 해결은 퍼즐을 해결하는 과정과 같다

알고리즘 테스트 != 코딩 능력! 알고리즘 테스트는 코딩 능력 테스트가 아니다. 알고리즘 테스트가 코딩 능력이라고 생각하는 것은 흔히 하는 실수이며, 실제로는 알고리즘 사고력이 핵심이다. 코딩을 못하는 게 아니라 알고리즘 사고력을 배우지 못했기 때문이다. 상위 레벨의 접근법으로 문제를 이해하고 풀어내는 과정이 알고리즘 사고력의 핵심이다. 문제에 급급해서는 상위 레벨의 접근법을 배울 수 없다. 문제를 어떤 전략으로 접근할지 결정하는 알고리즘 사고력을 배워야 한다.

알고리즘 사고력을 위해 엄선된 퍼즐! 직접 코딩을 하는 책은 아니지만, 알고리즘을 설계하거나 분석하기 위한 일반적인 원리를 보여줄 만한 퍼즐을 골랐다. 이러한 퍼즐을 통해 배울 수 있는 알고리즘 설계 전략은 다음과 같다.

  • 완전 검색
  • 역추적
  • 감소 정복
  • 분할 정복
  • 변환 정복
  • 탐욕 접근법
  • 반복 향상
  • 동적 프로그래밍
  • 분석 기술

마방진, N-퀸 문제, 애너그램 감지, 최단 경로 개수, 네덜란드 국기 문제 등의 퍼즐 문제는 알고리즘 코딩 테스트의 단골 문제이며, 다양한 코딩 테스트 사이트에서 문제로 출제된 것을 확인할 수 있다. 문제를 이해하고 풀 수 있다면 코딩 능력은 문제가 되지 않는다. 이것이 이 책의 핵심 가치다.

퍼즐의 난이도별 접근! 퍼즐이 어려운 독자를 위해 150개의 퍼즐을 난이도에 따라 초급, 중급, 고급으로 분류했다. 알고리즘 풀이 기법과 난이도에 따라 다양한 방식으로 문제에 접근할 수 있게 구성되어 있으며 이를 통해 알고리즘 디자인 전략과 분석 기법을 학습할 수 있게 했다.

«알고리즘 퍼즐»은 1장을 공개합니다.

목차

  • 1장 튜토리얼
  • 1.1 알고리즘 설계를 위한 일반 전략
  • 1.2 완전 검색
  • 1.3 역추적
  • 1.4 감소 정복
  • 1.5 분할 정복
  • 1.6 변환 정복
  • 1.7 탐욕 접근법
  • 1.8 반복 향상
  • 1.9 동적 프로그래밍
  • 1.10 분석 기술
  • 2장 퍼즐, 힌트와 풀이
  • 2.001 늑대, 염소, 양배추
  • 2.002 장갑 고르기
  • 2.003 직사각형 분할
  • 2.004 강 건너기
  • 2.005 행과 열 맞바꾸기
  • 2.006 손가락으로 숫자 세기
  • 2.007 밤에 다리 건너기
  • 2.008 조각 그림 맞추기
  • 2.009 암산
  • 2.010 동전 여덟 개 중에서 가짜 동전 찾아내기
  • 2.011 가짜 동전 무더기
  • 2.012 타일 채우기
  • 2.013 막힌 경로
  • 2.014 체스판 다시 조립하기
  • 2.015 트로미노 타일 채우기
  • 2.016 팬케이크 만들기
  • 2.017 킹이 갈 수 있는 곳
  • 2.018 끝에서 끝까지
  • 2.019 쪽번호 붙이기
  • 2.020 최대 합 내려가기
  • 2.021 정사각형 쪼개기
  • 2.022 팀 정렬
  • 2.023 폴란드 국기 문제
  • 2.024 체스판 색칠하기
  • 2.025 살아있기 좋은 날
  • 2.026 순위 구하기
  • 2.027 20변 게임
  • 2.028 한붓그리기
  • 2.029 마방진 톺아보기
  • 2.030 막대 자르기
  • 2.031 카드 맞히기 마술
  • 2.032 싱글 엘리미네이션 토너먼트
  • 2.033 마방진과 유사 마방진
  • 2.034 별 위의 동전
  • 2.035 물병 세 개
  • 2.036 +- 배치
  • 2.037 2n개의 말
  • 2.038 테트로미노 타일 배치
  • 2.039 판 밟기
  • 2.040 네 나이트 퍼즐
  • 2.041 원형으로 배치된 조명
  • 2.042 또 다른 늑대-염소-양배추 문제
  • 2.043 수 배치
  • 2.044 가벼운가 무거운가
  • 2.045 나이트 최단 경로
  • 2.046 삼색 배치
  • 2.047 전시 계획
  • 2.048 맥너겟 수
  • 2.049 선교사와 식인종
  • 2.050 마지막 공
  • 2.051 빠진 수 맞히기
  • 2.052 삼각형 개수
  • 2.053 용수철 저울로 가짜 동전 찾아내기
  • 2.054 직사각형 판 자르기
  • 2.055 주행거리 퍼즐
  • 2.056 신병 줄 세우기
  • 2.057 피보나치의 토끼
  • 2.058 한 번 정렬, 두 번 정렬
  • 2.059 두 가지 색 모자
  • 2.060 삼각형과 정사각형
  • 2.061 대각선상의 체커
  • 2.062 동전 줍기
  • 2.063 플러스와 마이너스
  • 2.064 팔각형 그리기
  • 2.065 암호 맞히기
  • 2.066 남은 수
  • 2.067 평균
  • 2.068 각 자리 숫자 더하기
  • 2.069 칩 옮기기
  • 2.070 점프해 쌍 만들기 I
  • 2.071 칸 표시하기 I
  • 2.072 칸 표시하기 II
  • 2.073 닭 쫓기
  • 2.074 위치 선택
  • 2.075 주유소 점검
  • 2.076 효율적인 루크
  • 2.077 패턴을 찾아서
  • 2.078 직선 트로미노 채우기
  • 2.079 사물함 문
  • 2.080 왕자의 여행
  • 2.081 유명 인사 문제 II
  • 2.082 모두 앞면 만들기
  • 2.083 제한된 하노이의 탑
  • 2.084 팬케이크 정렬
  • 2.085 루머 퍼뜨리기 I
  • 2.086 루머 퍼뜨리기 II
  • 2.087 뒤집힌 잔
  • 2.088 두꺼비와 개구리
  • 2.089 말 바꾸기
  • 2.090 자리 재배치
  • 2.091 수평 도미노와 수직 도미노
  • 2.092 사다리꼴 타일 배치
  • 2.093 전함 맞히기
  • 2.094 정렬된 표 검색
  • 2.095 최대-최소 무게
  • 2.096 계단 모양 영역 채우기
  • 2.097 탑스웝스 게임
  • 2.098 회문 개수 세기
  • 2.099 정렬 뒤집기
  • 2.100 나이트가 갈 수 있는 곳
  • 2.101 방에 페인트 칠하기
  • 2.102 원숭이와 코코넛
  • 2.103 반대편으로 점프하기
  • 2.104 말 나누기
  • 2.105 MU 퍼즐
  • 2.106 전구 켜기
  • 2.107 여우와 토끼
  • 2.108 최장 경로
  • 2.109 더블-n 도미노
  • 2.110 카멜레온
  • 2.111 동전 삼각형 뒤집기
  • 2.112 도미노 채우기 II
  • 2.113 동전 제거하기
  • 2.114 점 가로지르기
  • 2.115 바셰의 무게 추
  • 2.116 부전승 횟수
  • 2.117 1차원 솔리테어
  • 2.118 여섯 개의 나이트
  • 2.119 삼색 트로미노
  • 2.120 동전 분배기
  • 2.121 초강력 달걀 시험
  • 2.122 의회의 평화
  • 2.123 네덜란드 국기 문제
  • 2.124 사슬 자르기
  • 2.125 다섯 개를 일곱 번 안에 정렬하는 방법
  • 2.126 케이크를 공평하게 나누는 방법
  • 2.127 나이트의 여행
  • 2.128 보안 스위치
  • 2.129 리브의 퍼즐
  • 2.130 독이 든 와인
  • 2.131 테이트의 카운터 퍼즐
  • 2.132 솔리테어 군대
  • 2.133 라이프 게임
  • 2.134 점 색칠하기
  • 2.135 서로 다른 짝
  • 2.136 스파이 잡기
  • 2.137 점프해 쌍 만들기 II
  • 2.138 사탕 나누기
  • 2.139 아서왕의 원탁
  • 2.140 n-퀸 문제 다시 보기
  • 2.141 요세푸스 문제
  • 2.142 12개의 동전
  • 2.143 감염된 체스판
  • 2.144 정사각형 죽이기
  • 2.145 퍼즐
  • 2.146 움직이는 목표물 맞히기
  • 2.147 번호 달린 모자
  • 2.148 자유를 위한 동전 한 개
  • 2.149 자갈 펼치기
  • 2.150 불가리아식 솔리테어
신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.