3-3편 무식하게 풀기 3

3. 최적화 문제

- 경우의 수 문제와 같이 답이 여러개인 문제에서 '어떤 기준'에 따라 '좋은' 답을 찾는 문제를 '최적화 문제(Optimization Problem)'

※ 최적화 문제를 해결하는 방법

- 완전 탐색

- 동적 계획법

- 조합 탐색

- 결정 문제로 치환

=> 완전 탐색은 최적화 문제를 풀기 위한 가장 직관적인 방법

예제. 문제 : CLOCKSYNC

https://algospot.com/judge/problem/read/CLOCKSYNC

1) 문제를 읽고 이해하기

- 시간 제한 10ms / 메모리 제한 2^16kb

- 테스트 케이스의 개수 <= 30

2) 문제 재정의

- 16개의 시계, 3, 6, 9 12 만 가리킬 수 있음

- 10개의 스위치로 시간 조작 가능

- 각각의 스위치는 3~5개의 시계와 연결되어 있어서 해당 스위치를 누르면 연결된 시계들이 +3 씩 움직임

- 모두 12시를 가리키기 위해 눌러야 할 최소 스위치의 횟수

- 불가능할 경우 -1 출력

3) 계획 세우기

계획1.

- 최소 스위치 횟수 이기에 bfs를 고민함.

- 스위치를 몇 번 눌러야 할지 정해지지 않았기에 모든 상태를 저장하고 하나의 상태를 방문할 때 마다 저장된 상태와 비교하려고 함.

- 시계 하나는 3, 6, 9, 12 4가지 상태를 나타낼 수 있으므로 2bit로 표현 가능.

  16개의 시계 이므로 32bit 즉, int 하나로 16개 시계의 한 가지 상태를 저장 할 수 있음

  하지만, 메모리가 너무 크고 시간 예측이 안됨.

  큐 0회 : 4byte

  큐 1회 : 0 ~ 9번 버튼을 각각 눌렀을 때 10가지의 상태 : 40byte

  큐 2회 : 큐 1회에서 각각 10가지 경우가 또 발생 하므로 : 400byte

  큐 3회 : 4,000byte

  ... 큐 1회를 돌 때마다 10배가 늘어나므로 65,536,000 byte < 4 * 10^N => N이 8이면 메모리 초과

계획2.

- 시계가 3, 6, 9, 12로 회전 하므로 하나의 시계가 4회 이상 돌아갈 필요가 없음.

- '0번 버튼 -> 1번 버튼' 이나 '1번 버튼 -> 0번 버튼' 이나 결과는 똑같음

   012012나 001122는 결과가 같음

- 즉, 각각의 버튼은 0 ~ 3회만 누르면 되고 순서에 상관없음.

- 버튼을 누르는 횟수의 경우의 수는 4, 총 버튼의 개수가 10이므로 모든 경우의 수는 4^10

4) 계획 검증하기

- '계획1'은 이미 메모리 초과

- '계획2'는 4^10 == 2^20 ≒ 1억번

5, 6) 계획 수행하기 및 회고하기

- 문제 풀이 원리 : 다시 되돌아 오는 특징과 버튼의 순서가 중요하지 않다는 점이 버튼을 누르는 횟수를 제한 시킴

- 사실 아직도 4번 이상 누를 필요가 없는지에 대해서는 확신이 없음

- 나중에 내가 다시 풀 수 있을까?

- 비슷한 문제를 찾아봐야 겠음. 전구인가 색칠하기 인가 한칸 누르면 인접 4칸 색이 바뀌는 문제가 있었던거 같은데

- 구현 시 배열이라면 길이를 확인 또 확인....

- "Run-Time Check Failure#2 - Stack around the variable was corrupted" 에러는 포인터로 지역변수를 넘겼을 때 실제로 선언된 사이즈를 넘어선 인덱스로 입력을 시도할 때 발생함.

소스코드

#include<iostream>
using namespace std;

#define INF 987654321

int b[10][5] = { { 0, 1, 2, 16, 16 },   // 0
				 { 3, 7, 9, 11, 16 },   // 1
				 { 4, 10, 14, 15, 16 }, // 2
				 { 0, 4, 5, 6, 7 },     // 3
				 { 6, 7, 8, 10, 12 },   // 4
			 	 { 0, 2, 14, 15, 16 },  // 5
				 { 3, 14, 15, 16, 16 }, // 6
				 { 4, 5, 7, 14, 15 },   // 7
				 { 1, 2, 3, 4, 5 },     // 8
				 { 3, 4, 5, 9, 13 } };  // 9
int ans;

void dfs(int *clock, int button, int cnt){	
	int i = 0;
	for (; i < 16; i++)
		if (clock[i] != 0)
			break;
	// 아 이거..... 15가 아니라 16이었군
	if (i == 16){
		ans = ans < cnt ? ans : cnt;
		return;
	}
	if (button == 10)
		return;

	for (int j = 0; j < 4; j++){
		dfs(clock, button + 1, cnt + j);
		// 4번 돌리니까 dfs를 호출 하기 전의 시계 상태로 돌아감
		// 4번 회전하면 호출 하기 전의 시계상태로 돌아가므로 이전 상태를 따로 저장할 필요가 없음
		for (int k = 0; k < 5; k++)
			if (b[button][k] < 16)
				clock[b[button][k]] = (clock[b[button][k]] + 3) % 12;
	}

	return;
}

int main(void){
	ios::sync_with_stdio(false);
	freopen("Text.txt", "r", stdin);
	int T;
	cin >> T;
	while (T--){
		// clock를 15로 선언함....이거때문에 "Run-Time Check Failure#2 - Stack around the variable was corrupted" 떠서 당황했네
		int clock[16];
		ans = INF;
		for (int i = 0; i < 16; i++){
			cin >> clock[i];
			clock[i] %= 12;
		}
		dfs(clock, 0, 0);
		cout << ((ans == INF) ? -1 : ans) << "\n";
	}
	return 0;
}

4. 많이 등장하는 완전 탐색 유형

1) 모든 순열 만들기

- 가능한 모든 경우 : N!

- 실제로 만드는 방법은 다른 블로그 많으니 참고

- C++ 은 next_permutation(), prev_permutation()이 있음

2) 모든 조합 만들기

- 재귀

- nCr => 1개를 뽑고 n-1Cr-1을 재귀

- 코드 6.2 참고

3) 2^n가지 경우 만들기

- 'Yes / No' 의 경우 => 재귀 2^N

- Bit Mask를 이용하면 for문 하나로 모든 경우를 다 돌 수 있음

- 알고리즘 문제 해결전략 1편 중 -

- 저작권 문제시 삭제하겠습니다 -