문제 해결 전략 (p. 28)

1. 잘 알려진 문제의 변형 문제 (p. 28)#

최단 거리 문제 → 해결 방법이 매우 잘 알려져 있다. 이 방법을 익히면 모든 최단거리 문제를 풀 수 있을까?

변형 문제#

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

→ 이 문제들 중에는 최단 경로 문제를 응용해 풀 수 있는 것도 있고, 그럴 수 없는 것도 있다. 이들을 구분하려면 최단 경로 알고리즘을 단순히 알고 있는 것에 멈추지 않고 그 동작 과정과 원리를 완전히 이해하고 있어야 한다.

문제의 목적을 보고 적절한 접근 방법을 선택하기 위해선 어떤 문제가 최적화 문제인지, 경우의 수를 구하는 문제인지, 검색 문제인지 등을 분류하는 방법을 익히고, 각 알고리즘들이 어느 경우에 사용될 수 있는지 체계적으로 공부해야 한다.

2. 점진적 접근 방법 (p.31)#

사탕 나눠주기 문제#

N(N≤30)개의 사탕을 3명의 어린이에게 가능한 공평하게 나눠 주려고 함.

공평함의 기준은 받는 사탕의 총 무게가 가장 무거운 어린이와 가장 가벼운 어린이 간의 차이

사탕의 무게는 모두 20이하의 정수

가능한 최소 차이는 얼마일까?

가장 무식하게 생각 각 사탕마다 셋 중 어느 어린이에게 줄 지 결정 → $3^N$필요
각 어린이가 가진 사탕의 총량을 상태 공간으로 하는 BFS로 문제 풀기 어떤 어린이에게도 사탕이 없는 상태 (0,0,0)부터 사탕을 하나 줄 때마다 그 어린이기 가진 사탕의 양을 늘림. 사탕의 최대 무게는 20이므로, 각 어린이가 가진 사탕의 최대 값은 $20N$이므로 상태 공간의 크기를 $(20N+1)^3=601^3$(약 2억)으로 잡아야 함.
한 어린이가 받는 사탕 무게의 최대 크기는 $20N$보다 작음 최대 무게의 사탕을 가진 어린이가 최소 무게의 사탕을 가진 어린이보다 20보다 많이 차이가 난다면, 최대 무게의 사탕을 가진 어린이가 가장 무거운 사탕(무게 20)을 최소 무게의 사탕을 가진 어린이에게 넘겨줘도 공평함. 따라서 상태 공간의 크기는 $(20N/3 +20+1)^3=221^3$(약 1000만)으로 줄어듦.
(100,110,120) 상태와 (100,120,110)의 상태는 같은 것을 고려 오름차순으로 정렬된 상태만 고려하면 됨. → 탐색해야할 상태공간의 크기가 $1/6$로 줄어듦. (대략 200만)

3. 손으로 써보기 (p. 32)#

손으로 여러 간단한 입력을 써본다.

예를 들어 문제에 주어진 예제 입력을 직접 해결해 보는 것.

이 과정을 통해 보이지 않던 규칙을 찾을 수 있음.

4. 단순화 하기 (p. 32)#

주어진 문제의 좀 더 쉬운 변형판을 먼저 풀어 보기#

바둑판 위의 모든 바둑 돌들 간의 맨하탄 거리 합이 최소가 되게 하는 새로운 바둑 돌 두기 문제#

2차원 문제를 1차원으로 단순화 시킨다.

y축간의 최소거리는 x축 방향으로 이동하는것과 별개이므로 x축과 y축을 별개로 생각한다.

그런데 책에서는 이 문제를 ‘문제를 단순화 시키는 문제 해결전략의 예시’로 보여줬지만, 그 내용보다는 이 문제의 답이 중앙값에 있다는 아이디어가 더 중요해 보인다.

5. 그림 그리기 (p. 34)#

2개의 정수 쌍을 다루는 문제#

2차원 평면에 그려보거나, 직선 상의 구간들로 그려볼 수 있음.

6. 수식으로 표현 (p. 34)#

평문을 수식으로 표현

7. 문제 분해하기 (p. 35)#

8. 뒤에서부터 생각하기 (p. 36)#

문제: 사다리 타기

A→B 가는 것을 생각하는 건 어려우나, 반대로 B→A 가는 것을 생각하는건 쉬운 경우가 있다.

9. 순서 강제하기 (p. 37)#

순서가 없는 문제에서 순서를 강제하여 문제를 푼다.#

문제: 5x5 격자판에서 어떤 칸을 클릭하는 경우 해당 칸과 상하좌우 칸이 모두 상태가 toggle된다고 하자. (off면 on이 되고, on이면 off가 되는 식) 최소한의 클릭으로 모두 on상태를 만들려고 할 때, 최소 클릭 수 구하기.

■ 이 문제를 풀기 위해 깨달아야 하는 2가지

어떤 순서로 클릭을 하든 상관없음. 각 칸의 상태는 자신과 인접한 칸이 몇번 클릭되었는가에 따라 결정 됨.
한 칸을 2번 이상 클릭할 필요가 없음. 2번 클릭하게 되는 경우 이전 상태로 돌아오기 때문.

10. 정규화 (p. 39)#

문제: 원 덮기 문제

원 A와 여러 원들이 주어졌을 때, 원 A가 여러 원들을 모두 덮을 수 있는지 판단하는 문제

이 문제가 어려운 이유는 답이 될 수 있는 원 A의 중심좌표 후보가 무한개이다.

그래서 정규화를 통해 무한개의 모든 후보를 고려하는 대신 유한한 부분 집합만을 고려할 수 있도록 하는게 핵심이다.

정규화 기법을 사용하기 위해서는 어떤 답이 주어지더라도 이것을 특정 형태의 답으로 바꿀 수 있는 변형 과정을 찾아야 한다. 이 원 덮기 문제에서 사용할 변형 과정은 원 A가 여러 원들을 그냥 덮는 것이 아니라 두 원과 접한 상태로 덮는 것을 찾는 것이다. 달리 말해 답이 하나라도 존재한다면 두 개의 점선 원과 접한 답 또한 반드시 존재한다는 말이 된다. 따라서 이 문제는 입력에 주어진 모든 두 점선 원의 조합을 순회하며 이들과 접하는 A의 위치를 계산해서 풀 수 있다.