[스터디]종만북(프로그래밍 대회에서 배우는 알고리즘 전략)

Note: 전체목차를 다룰 수 없어 필요하다고 생각하는 부분만 발췌하여 요약합니다.

1부 문제 해결 시작하기

1장 문제 해결과 프로그래밍 대회

1.3 이 책을 읽는 방법

입문자를 위한 권장사항

가장 중요하고 기초적인 주제만을 우선 소화한 뒤 다시 읽으며 빈 곳을 메꾸는 커리큘럼입니다.

장번호	장제목
2	문제 해결 전략
3	코딩과 디버깅
4	알고리즘의 시간 복잡도 분석
6	무식하게 풀기
7	분할 정복
8	동적 계획법
18	선형 자료 구조
19	큐와 스택, 데크
21	트리의 구현과 순회
22	이진 검색 트리
23	우선순위 큐와 힙
27	그래프의 표현과 정의
28	그래프의 깊이 우선 탐색
29	그래프의 너비 우선 탐색
30	최단 경로 알고리즘

1.6 더 읽을 거리

책소개를 다루므로 공부가 끝난 뒤 관심이 있다면 챙겨볼 것.

2장 문제 해결 개관

이 장에서는 문제 해결 과정을 여러 단계로 나누어 보고 각 단계를 더 잘하기 위한 여러 기술들을 소개합니다.

[중요]2.2 문제 해결 과정

문제 해결 연구의 고전 『How to solve it』에서는 문제 해결 과정을 다음과 같이 네 단계로 나누어 소개한다.

1. 문제를 이해한다.
2. 어떻게 풀지 계획을 세운다.
3. 계획을 수행해서 문제를 해결한다.
4. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

이를 약간 변경하여 프로그래밍 문제를 해결하는 과정은 아래처럼 요약할 수 있다.

1. 문제를 이해한다.
2. 문제를 익숙한 용어로 재정의한다.
3. 어떻게 해결할 지 계획을 세운다.
4. 계획을 검증한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고 개선할 방법이 있는지 찾아본다.

1단계: 문제를 읽고 이해하기

모든 사람이 공통적으로 하는 실수가 있다면 문제를 잘못 읽는 것입니다. 이러한 실수는 치명적일 수 있으므로 문제 설명을 공격적으로 읽으며 문제가 원하는 바를 완전히 이해하는 과정이 반드시 필요합니다.

이후 단계에 대한 설명은 불필요하다고 생각되므로 패스합니다.

if: 문제를 풀지 못할 때

일정 시간이 지나도록 고민해도 답을 찾지 못할 떄는 다른 사람의 소스코드나 풀이를 참조한다는 원칙을 세우고 이를 지키는 것이 좋습니다. 그렇지만 다른사람의 소스를 참조할 땐 반드시 복기를 동반해야 합니다.

Note: 꼭 위의 절차를 따르라는 뜻은 아닙니다. 숙련자는 모든 단계를 생략하지도 따라하지도 않으며 경험에 따라 의식하지 않고 이와 유사한 단계를 거쳐 문제를 해결합니다.

2.3 문제 해결 전략

어려운 문제일수록 다양한 방법을 시도해 보면서 답안을 찾아야 합니다. 이번 장에서는 우리가 사용할 수 있는 가장 일반적인 전략들을 몇 가지 소개하고 이들의 사용예를 들어보도록 합니다. 이 기술들은 책의 연습문제에서 적극적으로 사용되므로 답안을 읽을 때 어떤 방법을 사용했는지 눈여겨보면 좋습니다.

직관과 체계적인 접근

직관을 발달시키기 위해서는 결국 얼핏 보기엔 막막한 문제들을 해결하며 차곡차곡 경험을 쌓아가야 합니다.

체계적인 접근을 위한 질문들

1. 비슷한 문제를 풀어본 적이 있던가?

기존에 접했던 문제가 온전히 경험이 되려면 그 원리를 완전히 이해하고 변형할 수 있어야 합니다. 예를 들어 철도망 위에서 두 도시를 잇는 가장 짧은 경로를 찾는 문제를 풀었다고 합시다. 이를 푸는 많은 표준 알고리즘이 있으므로 해당 코드를 외우고 나면 이제 모든 최단거리 문제를 풀 수 있을거라고 생각하기 쉽습니다. 그렇지만 아래의 문제는 최단경로 문제를 응용해서 풀 수 있을 수도 없을 수도 있습니다.

• 한 도시를 두 번 방문하지 않으면서 가장 긴 경로를 찾는 문제
• 기차를 네 번 이하로 갈아타면서 가장 짧은 경로를 찾는 문제
• 역 간 운행 거리 중 가장 긴 구간이 가장 짧은 경로를 찾는 문제
• 역 간 운행 거리 중 가장 짧은 구간이 가장 긴 경로를 찾는 문제

이들을 구분하려면 알고리즘을 완전히 이해하고 응용할 수 있어야 합니다. 꼭 형태가 비슷하지 않더라도 문제의 목표가 같은 경우 또한 이런 사례에 속합니다. 예를 들어 어떤 사건의 발생 확률이나 경우의 수를 계산하는 문제들은 대부분 동적 계획법으로 해결할 수 있지요.

1. 단순한 방법에서 시작할 수 없을까?

시간과 공간 제약을 생각하지 않고 문제를 해결할 수 있는 가장 단순한 알고리즘을 만드는 것을 뜻합니다. 물론 단순한 방법으로 모든 문제가 풀릴리는 없습니다. 그러나 이를 점진적으로 개선하거나 새로운 알고리즘이 얼마나 빨라졌는지 개선되었는지 재는 용도로 유용하게 사용할 수 있습니다.

예를 들어, N(N<=30)개의 사탕을 세 명의 어린이에게 공평하게 나누어주려고 합니다. 공평함의 기준은 받는 사탕의 총 무게가 가장 무거운 어린이와 가장 가벼운 어린이 간의 차이로 합시다. 사탕의 무게는 모두 20이하의 정수이빈다. 가능한 최소 차이는 몇일까요?

이 문제의 가장 단순한 해법은 사탕을 나누어 주는 모든 방법을 하나씩 만들어 보는 것입니다. 각 사탕마다 셋 중 어느 어린이에게 나누어 줄지 결정한다고 하면 3^N, 즉 최대 205조개의 방법을 만들어 보게 됩니다…. 사실 우리는 엄청나게 많은 수를 중복으로 세고 있습니다. 실제로 받은 사탕이 다르더라도 무게가 같다면 답은 같다는 사실을 모두 무시했기 때문입니다.

따라서 모든 방법을 만들어 보는 완전탐색 대신 각 어린이가 가진 사탕의 총량을 상태 공간으로 하는 너비 우선 탐색으로 문제를 풀 수 있습니다.이 때 각 상태는 세 어린이가 가진 사탕의 양을 표현하는 세 개의 정수 입니다. 즉 모든 어린이가 사탕을 가지고 있지 않다면 (0, 0, 0)입니다. 이 경우 실제로 가진 사탕이 다르더라도 그 무게가 같은 경우 하나의 상태로 취급해 중복을 제거할 수 있습니다. 이 상태 공간의 크기는 사탕의 무게가 최대 N이며 갯수가 20개이므로 최대 (601)^3 = 약 2억인 배열입니다.

2억이면 대략 시간내에 탐색할 수 있지만 더 최적화 할 수 있습니다. 사탕을 가장 많이 받은 어린이와 가장 적게 받은 어린이의 차이가 20이상이었다고 가정해봅시다. 이 때 가장 많이 받은 어린이가 가장 적게 받은 어린이에게 사탕 하나를 주어도 더 공평한 답을 얻을 수 있습니다. 따라서 차이가 20이상 나는 경우 절대로 최적의 답이 아니라는 것을 알 수 있으므로 (20N)/3 + 20 넘게 사탕을 받은 경우는 무시해도 됩니다. 따라서 실제로 할당할 배열은 ((20N)/3 + 20)^3 = 220^3 대략 1000만으로 줄어듭니다.

더! 줄일수 있습니다. 세 어린이 중 누가 사탕을 가장 많이 받았는지는 중요하지 않기 때문입니다. 즉, (200, 190, 180)과 (180, 190 200)은 똑같습니다. 따라서 또 배열의 수는 1/6으로 줄어듦을 알 수 있으며 우리는 처음에 생각한 배열크기이 약 1억분의 1로 줄어들게 했습니다.

1. 내가 푸는 과정을 수식화할 수 있을까?

예를 들어 문제에 주어진 예제 입력을 직접 해결해 보는 것입니다. 자신이 문제를 해결한 과정을 공식화해서 답을 만드는 알고리즘이 어떤점을 고려해야 하는지를 알게 기 떄문입니다.

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 더 읽을거리