6장: 무식하게 풀기 - 2 (165p ~ 173p)

<최적화 문제>

1. 최적화 문제

• 최적화 문제(Optimization problem): 문제의 답이 하나가 아니라 여러 개이고, 그중에서 어떤 기준에 따라 가장 '좋은'답을 찾아내는 문제들을 통칭해 최적화 문제라고 한다.
• ex) n개의 원소중 r개를 골라서 무게의 합을 최대화 하는 문제 etc

2. 여행하는 외판원 문제

• 그래프에서 모든 점을 다 거쳐가는 사이클을 구성하는 거리가 최소가 되도록 하는 사이클을 구하기
• 정점이 9개의 경우 9!=362,880으로 시간 안에 해결할 수 있으므로 재귀 호출을 통해 해결할 수 있다.

3. 문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중)

• 열여섯 개의 시계가 있다. 이 시계들은 모두 3의 배수 시를 가리키고 있는데 모두 12시로 맞추고자 한다. 9개의 스위치가 있고 각 스위치를 누를 때마다 연결된 시계들의 시축이 3칸 움직인다고 한다. 모든 시계를 12시로 돌리기 위해 최소한 스위치를  몇 번 눌러야 할지 계산하는 프로그램을 작성하시오.
• 스위치를 누르는데 순서는 상관 없으며 스위치를 4번 누르면 다시 원래대로 돌아오므로 4^9번의 개산으로 해결이 가능하다. 즉 각 스위치를 0~3번 누르는 것으로 완전탐색하면 구할 수 있다.

 

<많이 등장하는 완전 탐색 유형>

1. 모든 순열 만들기

• 서로 다른 N개의 원소를 일렬로 줄 세운 것을 순열(permutation)이라고 한다.
• 순열은 next_permuatation()함수를 통해 간단히 생성할 수 있다.

2. 모든 조합 만들기

• 서로 다른 N개의 원소 중에서 R개를 순서 없이 골라낸 것을 조합(combination)이라고 한다.
• nCr의 경우의 수로 해결 가능하다. 전해준 배열에서 없는 원소를 또 하고 하는 방식으로 구현할 수 있다.

3. \(2^{n}\)가지 경우의 수 만들기

• n개의 질문에 대한 답이 예/아니오 중의 하나라고 할 때 존재할 수 있는 답의 모든 조합의 수는 \(2^{n}\)가지이다. 이는 n비트 정수로 표현하면 재귀 호출을 사용하지 않고 1차원 for문 하나로 이 조합들을 간단하게 모두 시도할 수 있다.