Hello

: )

2016년 4월 3일 일요일

알고리즘 문제해결 전략 [책]

몇 년째 읽는 책: 알고리즘 문제해결 전략
저자: 구종만
책 소개&코드: http://book.algospot.com/index.html

https://algospot.com 에서 문제 풀이를 할 수 있고,
책에 있는 코드는 알고리즘의 핵심부분만 존재하기 때문에
입출력은 직접 작성해야 합니다.

특정 주제를 공부하고, 예를 들어, 31 장 최소 스패닝 트리 관련 내용을 공부 후에 해당 코드를 기반으로 BOJ 의 알고리즘 분류 - 최소 스패닝 트리로 가서 문제를 골라서 풀어보면 됩니다. 코드 31.1 로 9372번: 상근이의 여행 (https://www.acmicpc.net/problem/9372) 은 쉽게 풀 수 있습니다.


문제해결을 위한 창의적 알고리즘 보다는 내용이 훨씬 어렵고,
2017 년 들어 수면용으로 잘 사용하고 있습니다. 2018 년도..  그러고 있는 중이고, 2019 년에도.... ㅠ

1부 문제 해결 시작하기

  • 1장 문제 해결과 프로그래밍 대회
    • 1.1 도입
    • 1.2 프로그래밍 대회
    • 1.3 이 책을 읽는 방법
    • 1.4 국내에서 참가할 수 있는 프로그래밍 대회들
    • 1.5 대회 준비를 위한 조언
    • 1.6 더 읽을 거리
  • 2장 문제 해결 개관 (입문자 추천)
    • 2.1 도입
    • 2.2 문제 해결 과정
    • 2.3 문제 해결 전략
    • 2.4 더 읽을거리
  • 3장 코딩과 디버깅에 관하여 (입문자 추천)
    • 3.1 도입: 코딩의 중요성을 간과하지 말라
    • 3.2 좋은 코드를 짜기 위한 원칙
    • 3.3 자주 하는 실수
    • 3.4 디버깅과 테스팅
    • 3.5 변수 범위의 이해
    • 3.6 실수 자료형의 이해(OPTIONAL)
    • 3.7 더 읽을 거리

2부 알고리즘 분석

  • 4장 알고리즘의 시간 복잡도 분석 (입문자 추천)
    • 4.1 도입
    • 4.2 선형 시간 알고리즘
    • 4.3 선형 이하 시간 알고리즘
    • 4.4 지수 시간 알고리즘
    • 4.5 시간 복잡도
    • 4.6 수행 시간 어림짐작하기
    • 4.7 계산 복잡도 클래스: P, NP, NP-완비
    • 4.8 더 읽을 거리
  • 5장 알고리즘의 정당성 증명
    • 5.1 도입
    • 5.2 수학적 귀납법과 반복문 불변식
    • 5.3 귀류법
    • 5.4 다른 기술들
    • 5.5 더 읽을 거리

3부 알고리즘 설계 패러다임

  • 6장 무식하게 풀기 (입문자 추천)
    • 6.1 도입
    • 6.2 재귀 호출과 완전 탐색
    • 6.3 문제: 소풍 (난이도: 하, 문제 ID: PICNIC)
    • 6.4 풀이: 소풍
    • 6.5 문제: 게임판 덮기 (난이도: 하, 문제 ID: BOARDCOVER)
    • 6.6 풀이: 게임판 덮기
    • 6.7 최적화 문제
    • 6.8 문제: 시계 맞추기 (난이도: 중, 문제 ID: CLOCKSYNC)
    • 6.9 풀이: 시계 맞추기
    • 6.10 많이 등장하는 완전 탐색 유형
  • 7장 분할 정복 (입문자 추천)
    • 7.1 도입
    • 7.2 문제: 쿼드 트리 뒤집기 (문제 ID: QUADTREE, 난이도: 하)
    • 7.3 풀이: 쿼드 트리 뒤집기
    • 7.4 문제: 울타리 잘라내기 (문제 ID: FENCE, 난이도: 중)
    • 7.5 풀이: 울타리 잘라내기
    • 7.6 문제: 팬 미팅 (문제 ID: FANMEETING, 난이도: 상)
    • 7.7 풀이: 팬 미팅
  • 8장 동적 계획법 (입문자 추천)
    • 8.1 도입
    • 8.2 문제: 와일드카드 (문제 ID: WILDCARD, 난이도: 중)
    • 8.3 풀이: 와일드카드
    • 8.4 전통적 최적화 문제들
    • 8.5 문제: 합친 LIS (문제 ID: JLIS, 난이도: 하)
    • 8.6 풀이: 합친 LIS
    • 8.7 문제: 원주율 외우기 (문제 ID: PI, 난이도: 하)
    • 8.8 풀이: 원주율 외우기
    • 8.9 문제: QUANTIZATION (문제 ID: QUANTIZE, 난이도: 중)
    • 8.10 풀이: QUANTIZATION
    • 8.11 경우의 수와 확률
    • 8.12 문제: 비대칭 타일링 (문제 ID: ASYMTILING, 난이도: 하)
    • 8.13 풀이: 비대칭 타일링
    • 8.14 문제: 폴리오미노 (문제 ID: POLY, 난이도: 중)
    • 8.15 풀이: 폴리오미노
    • 8.16 문제: 두니발 박사의 탈옥 (문제 ID: NUMB3RS, 난이도: 중)
    • 8.17 풀이: 두니발 박사의 탈옥
  • 9장 동적 계획법 테크닉
    • 9.1 최적화 문제의 실제 답 계산하기
    • 9.2 문제: 여행 짐 싸기 (문제 ID: PACKING, 난이도: 중)
    • 9.3 풀이: 여행 짐 싸기
    • 9.4 문제: 광학 문자 인식 (문제 ID: OCR, 난이도: 상)
    • 9.5 풀이: 광학 문자 인식
    • 9.6 K번째 답 계산하기
    • 9.7 문제: K번째 최대 증가 부분 수열 (문제 ID: KLIS, 난이도: 상)
    • 9.8 풀이: K번째 최대 증가 부분 수열
    • 9.9 문제: 드래곤 커브 (문제 ID: DRAGON, 난이도: 중)
    • 9.10 풀이: 드래곤 커브
    • 9.11 정수 이외의 입력에 대한 메모이제이션
    • 9.12 문제: 웨브바짐 (문제 ID: ZIMBABWE, 난이도: 상)
    • 9.13 풀이: 웨브바짐
    • 9.14 문제: 실험 데이터 복구하기 (문제 ID: RESTORE, 난이도: 중)
    • 9.15 풀이: 실험 데이터 복구하기
    • 9.16 조합 게임
    • 9.17 문제: 숫자 게임 (문제 ID: NUMBERGAME, 난이도: 하)
    • 9.18 풀이: 숫자 게임
    • 9.19 문제: 블록 게임 (문제 ID: BLOCKGAME, 난이도: 중)
    • 9.20 풀이: 블록 게임
    • 9.21 반복적 동적 계획법
    • 9.22 문제: 회전초밥 (문제 ID: SUSHI, 난이도: 중)
    • 9.23 풀이: 회전초밥
    • 9.24 문제: 지니어스 (문제 ID: GENIUS, 난이도: 중)
    • 9.25 풀이: 지니어스
    • 9.26 더 읽을 거리
  • 10장 탐욕법
    • 10.1 도입
    • 10.2 문제: 도시락 데우기 (문제 ID: LUNCHBOX, 난이도: 하)
    • 10.3 풀이: 도시락 데우기
    • 10.4 문제: 문자열 합치기 (문제 ID: STRJOIN, 난이도: 중)
    • 10.5 풀이: 문자열 합치기
    • 10.6 문제: 미나스 아노르 (문제 ID: MINASTIRITH, 난이도: 상)
    • 10.7 풀이: 미나스 아노르
  • 11장 조합 탐색
    • 11.1 도입
    • 11.2 조합 탐색 기법들
    • 11.3 문제: 게임판 덮기 2 (문제 ID: BOARDCOVER2, 난이도: 하)
    • 11.4 풀이: 게임판 덮기 2
    • 11.5 문제: 알러지가 심한 친구들 (문제 ID: ALLERGY, 난이도: 중)
    • 11.6 풀이: 알러지가 심한 친구들
    • 11.7 문제: 카쿠로 (문제 ID: KAKURO2, 난이도: 중)
    • 11.8 풀이: 카쿠로
    • 11.9 더 읽을거리
  • 12장 최적화 문제 결정 문제로 바꿔 풀기
    • 12.1 도입
    • 12.2 문제: 남극 기지 (문제 ID: ARCTIC, 난이도: 하)
    • 12.3 풀이: 남극 기지
    • 12.4 문제: 캐나다 여행 (문제 ID: CANADATRIP, 난이도: 중)
    • 12.5 풀이: 캐나다 여행
    • 12.6 문제: 수강 철회 (문제 ID: WITHDRAWAL, 난이도: 상)
    • 12.7 풀이: 수강 철회

4부 유명한 알고리즘들

  • 13장 수치 해석
    • 13.1 도입
    • 13.2 이분법
    • 13.3 문제: 승률 올리기 (문제 ID: RATIO, 난이도: 하)
    • 13.4 풀이: 승률 올리기
    • 13.5 삼분 검색
    • 13.6 문제: 꽃가루 화석 (문제 ID: FOSSIL, 난이도: 상)
    • 13.7 풀이: 꽃가루 화석
    • 13.8 다른 주제들
  • 14장 정수론
    • 14.1 도입
    • 14.2 소수
    • 14.3 문제: 비밀번호 486 (문제 ID: PASS486, 난이도: 중)
    • 14.4 풀이: 비밀번호 486
    • 14.5 유클리드 알고리즘
    • 14.6 문제: 마법의 약 (문제 ID: POTION, 난이도: 중)
    • 14.7 풀이: 마법의 약
    • 14.8 모듈라 연산
    • 14.9 더 읽을거리(OPTIONAL)
  • 15장 계산 기하
    • 15.1 도입
    • 15.2 계산 기하의 도구들
    • 15.3 교차와 거리, 면적
    • 15.4 문제: 핀볼 시뮬레이션 (문제 ID: PINBALL, 난이도: 상)
    • 15.5 풀이: 핀볼 시뮬레이션
    • 15.6 다각형
    • 15.7 문제: 보물섬 (문제 ID: TREASURE, 난이도: 상)
    • 15.8 풀이: 보물섬
    • 15.9 문제: 너드인가, 너드가 아닌가? (문제 ID: NERDS, 난이도: 중)
    • 15.10 풀이: 너드인가, 너드가 아닌가?
    • 15.11 계산 기하 알고리즘 디자인 패턴
    • 15.12 자주 하는 실수와 유의점들
    • 15.13 더 읽을거리

5부 기초 자료 구조

  • 16장 비트마스크
    • 16.1 도입
    • 16.2 비트마스크를 이용한 집합의 구현
    • 16.3 비트마스크의 응용 예제
    • 16.4 문제: 졸업 학기 (문제 ID: GRADUATION, 난이도: 중)
    • 16.5 풀이: 졸업 학기
    • 16.6 더 읽을거리
  • 17장 부분 합
    • 17.1 도입
    • 17.2 문제: 크리스마스 인형 (문제 ID: CHRISTMAS, 난이도: 중)
    • 17.3 풀이: 크리스마스 인형
    • 17.4 더 공부할 거리
  • 18장 선형 자료 구조 (입문자 추천)
    • 18.1 도입
    • 18.2 동적 배열
    • 18.3 연결 리스트
    • 18.4 동적 배열과 연결 리스트의 비교
    • 18.5 문제: 조세푸스 문제 (문제 ID: JOSEPHUS, 난이도: 하)
    • 18.6 풀이: 조세푸스 문제
    • 18.7 더 읽을 거리
  • 19장 큐와 스택, 데크 (입문자 추천)
    • 19.1 도입
    • 19.2 큐와 스택, 데크의 구현
    • 19.3 스택과 큐의 활용
    • 19.4 문제: 짝이 맞지 않는 괄호 (문제 ID: BRACKETS2, 난이도: 하)
    • 19.5 풀이: 짝이 맞지 않는 괄호
    • 19.6 문제: 외계 신호 분석 (문제 ID: ITES, 난이도: 중)
    • 19.7 풀이: 외계 신호 분석
  • 20장 문자열
    • 20.1 도입
    • 20.2 문자열 검색
    • 20.3 문제: 재하의 금고 (문제 ID: JAEHASAFE, 난이도: 중)
    • 20.4 풀이: 재하의 금고
    • 20.5 접미사 배열
    • 20.6 문제: 말버릇 (문제 ID: HABIT, 난이도: 중)
    • 20.7 풀이: 말버릇
    • 20.8 더 읽을거리

6부 트리

  • 21장 트리의 구현과 순회 (입문자 추천)
    • 21.1 도입
    • 21.2 트리의 순회
    • 21.3 문제: 트리 순회 순서 변경 (문제 ID: TRAVERSAL, 난이도: 하)
    • 21.4 풀이: 트리 순회 순서 변경
    • 21.5 문제: 요새 (문제 ID: FORTRESS, 난이도: 중)
    • 21.6 풀이: 요새
  • 22장 이진 검색 트리 (입문자 추천)
    • 22.1 도입
    • 22.2 이진 검색 트리의 정의와 조작
    • 22.3 시간 복잡도 분석과 균형 잡힌 이진 검색 트리
    • 22.4 문제: 너드인가, 너드가 아닌가? 2 (문제 ID: NERD2, 난이도: 중)
    • 22.5 풀이: 너드인가, 너드가 아닌가? 2
    • 22.6 균형 잡힌 이진 검색 트리 직접 구현하기: 트립
    • 22.7 문제: 삽입 정렬 뒤집기 (문제 ID: INSERTION, 난이도: 중)
    • 22.8 풀이: 삽입 정렬 뒤집기
  • 23장 우선순위 큐와 힙 (입문자 추천)
    • 23.1 도입
    • 23.2 힙의 정의와 구현
    • 23.3 문제: 변화하는 중간 값 (문제 ID: RUNNINGMEDIAN, 난이도: 하)
    • 23.4 풀이: 변화하는 중간 값
  • 24장 구간 트리
    • 24.1 구간 트리: 구간에 대한 질문 대답하기
    • 24.2 문제: 등산로 (문제 ID: MORDOR, 난이도: 중)
    • 24.3 풀이: 등산로
    • 24.4 문제: 족보 탐험 (문제 ID: FAMILYTREE, 난이도: 상)
    • 24.5 풀이: 족보 탐험
    • 24.6 펜윅 트리: 빠르고 간단한 구간 합
    • 24.7 문제: 삽입 정렬 시간 재기 (문제 ID: MEASURETIME, 난이도: 중)
    • 24.8 풀이: 삽입 정렬 시간 재기
  • 25장 상호 배타적 집합
    • 25.1 도입
    • 25.2 문제: 에디터 전쟁 (문제 ID: EDITORWARS, 난이도: 중)
    • 25.3 풀이: 에디터 전쟁
  • 26장 트라이
    • 26.1 도입
    • 26.2 문제: 안녕히, 그리고 물고기는 고마웠어요! (문제 ID: SOLONG, 난이도: 중)
    • 26.3 풀이: 안녕히, 그리고 물고기는 고마웠어요!
    • 26.4 트라이를 이용한 다중 문자열 검색
    • 26.5 문제: 보안종결자 (문제 ID: NH, 난이도: 상)
    • 26.6 풀이: 보안종결자

7부 그래프

  • 27장 그래프의 표현과 정의 (입문자 추천)
    • 27.1 도입
    • 27.2 그래프의 사용 예
    • 27.3 암시적 그래프 구조들
    • 27.4 그래프의 표현 방법
  • 28장 그래프의 깊이 우선 탐색 (입문자 추천)
    • 28.1 도입
    • 28.2 문제: 고대어 사전 (문제 ID: DICTIONARY, 난이도: 하)
    • 28.3 풀이: 고대어 사전
    • 28.4 오일러 서킷
    • 28.5 문제: 단어 제한 끝말잇기 (문제 ID: WORDCHAIN, 난이도: 하)
    • 28.6 풀이: 단어 제한 끝말잇기
    • 28.7 이론적 배경과 응용
    • 28.8 문제: 감시 카메라 설치 (문제 ID: GALLERY, 난이도: 중)
    • 28.9 풀이: 감시 카메라 설치
    • 28.10 문제: 회의실 배정 (문제 ID: MEETINGROOM, 난이도: 상)
    • 28.11 풀이: 회의실 배정
  • 29장 그래프의 너비 우선 탐색 (입문자 추천)
    • 29.1 도입
    • 29.2 문제: SORTING GAME (문제 ID: SORTGAME, 난이도: 중)
    • 29.3 풀이: SORTING GAME
    • 29.4 문제: 어린이날 (문제 ID: CHILDRENDAY, 난이도: 상)
    • 29.5 풀이: 어린이날
    • 29.6 최단 경로 전략
    • 29.7 문제: 하노이의 탑 (문제 ID: HANOI4B, 난이도: 중)
    • 29.8 풀이: 하노이의 탑
  • 30장 최단 경로 알고리즘 (입문자 추천)
    • 30.1 도입
    • 30.2 다익스트라의 최단 경로 알고리즘
    • 30.3 문제: 신호 라우팅 (문제 ID: ROUTING, 난이도: 하)
    • 30.4 풀이: 신호 라우팅
    • 30.5 문제: 소방차 (문제 ID: FIRETRUCKS, 난이도: 중)
    • 30.6 풀이: 소방차
    • 30.7 문제: 철인 N종 경기 (문제 ID: NTHLON, 난이도: 상)
    • 30.8 풀이: 철인 N종 경기
    • 30.9 벨만-포드의 최단 경로 알고리즘
    • 30.10 문제: 시간여행 (문제 ID: TIMETRIP, 난이도: 중)
    • 30.11 풀이: 시간여행
    • 30.12 플로이드의 모든 쌍 최단 거리 알고리즘
    • 30.13 문제: 음주 운전 단속 (문제 ID: DRUNKEN, 난이도: 중)
    • 30.14 풀이: 음주 운전 단속
    • 30.15 문제: 선거 공약 (문제 ID: PROMISES, 난이도: 중)
    • 30.16 풀이: 선거 공약
  • 31장 최소 스패닝 트리
    • 31.1 도입
    • 31.2 크루스칼의 최소 스패닝 트리 알고리즘
    • 31.3 프림의 최소 스패닝 트리 알고리즘
    • 31.4 문제: 근거리 네트워크 (문제 ID: LAN, 난이도: 하)
    • 31.5 풀이: 근거리 네트워크
    • 31.6 문제: 여행 경로 정하기 (문제 ID: TPATH, 난이도: 상)
    • 31.7 풀이: 여행 경로 정하기
  • 32장 네트워크 유량
    • 32.1 도입
    • 32.2 포드-풀커슨 알고리즘
    • 32.3 네트워크 모델링
    • 32.4 문제: 승부 조작 (문제 ID: MATCHFIX, 난이도: 중)
    • 32.5 풀이: 승부 조작
    • 32.6 문제: 국책 사업 (문제 ID: PROJECTS, 난이도: 상)
    • 32.7 풀이: 국책 사업
    • 32.8 이분 매칭
    • 32.9 문제: 비숍 (문제 ID: BISHOPS, 난이도: 중)
    • 32.10 풀이: 비숍
    • 32.11 문제: 함정 설치 (문제 ID: TRAPCARD, 난이도: 상)
    • 32.12 풀이: 함정 설치
    • 32.13 더 공부할 거리

문제 풀이 (93)

* 목차에는 76 문제만 기술되어 있고, 실제로는 더 많습니다
* 저자님께서 만드신 페이지: https://algospot.com/wiki/read/JMBook_%EB%AC%B8%EC%A0%9C%EB%93%A4_%EB%A7%81%ED%81%AC



댓글 없음:

댓글 쓰기