브루트 포스는 모든 경우의 수를 다 해보는 것

문제1) 일곱 난쟁이 [2309]

9명의 난쟁이들 중, 7명의 합이 100이 되는 7명의 난쟁이들 찾기.

시간복잡도: O(N2), 경우의수: 9C2 = 36 -> 따라서 그냥 다 해봐도된다~

전 코드)

void print(int* arr, int fake, int fake2) {
	int arr2[7];
	int j = 0;
	for (int i = 0; i < 9; i++){
		if ((arr[i] != arr[fake]) && (arr[i] != arr[fake2])) {
			arr2[j] = arr[i];
			j++;
		}
	}
	for (int i = 0; i < 7; i++) {
		sort(arr2, arr2 + 7);
		cout << arr2[i] << "\n";
	}
}

int main() {
	int a[9];
	int sum = 0;
	int c_sum = 0;

	for (int i = 0; i < 9; i++) {	// 난쟁이의 키 입력받기
		scanf("%d", &a[i]);
		sum += a[i];
	}

	for (int i = 0; i < 8; i++) {   // 모든 경우의 수
		for (int j = 1 + i; j < 9; j++) {
			c_sum = a[i] + a[j];
			if (sum - c_sum == 100) {
				print(a, i, j); // 찾은 경우, 출력하는 함수 호출
				return 0;
			}
		}

	}
	return 0;
}

코드의 비효율점)

• 출력하는 함수를 따로 만든것 (굳이 인것같다)
• 찐 일곱난쟁이를 저장하기 위한 새로운 배열(arr2)을 생성한것 (배열을 새로 생성한 이유는 정렬하기 위함이었는데, 이는 찐난쟁 판별 전에 미리 정렬하는 방법이 있다)
• 새로운 인자(c_sum)를 생성한것 (이건 공간차지가 크지 않으므로, 큰 실수는 아니다만 간단한 경우에는 굳이 새로 생성할 필욘 없는거 같다)
• for문 내 바로 return을 쓴것 (flag를 넣어서 찾은경우 flag를 올려주고, 그럼 for문 탈출이 좀더 매끄러운듯하다)

수정코드)

/* 2309번 일곱난쟁이 */
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

int main() {
	int a[9];
	int sum = 0, flag = 0;

	for (int i = 0; i < 9; i++) {	// 난쟁이의 키 입력받기
		scanf("%d", &a[i]);
		sum += a[i]; 
	}
	sort(a, a + 9);
	for (int i = 0; i < 8; i++) {   // 모든 경우의 수
		if (flag == 1) break;
		for (int j = 1 + i; j < 9; j++) {
			if (flag == 1) break;
			if (sum - (a[i] + a[j]) == 100) {
				flag = 1;
				for (int k = 0; k < 9; k++) {
					if (k != i && k != j)
						cout << a[k] << "\n";
				}
			}
		}

	}
	return 0;
}

문제2) 사탕게임 [3085]

시간 내 풀지못하여 백준 답안을 참고하였다.

코드)

/* 3085번 사탕게임 */
#include <iostream>
#include <stdio.h>
#include <vector>
#define N 50
using namespace std;

int check(vector<string> &ca, int n) { // 모든 행과 열을 조사하여 연속하는 수의 최대값을 구함
	int max_cnt = 0;
	for (int i = 0; i < n; i++) {
		int cnt = 1;
		for (int j = 0; j < n-1; j++) {
			if (ca[i][j] == ca[i][j+1])  cnt++;
			else {
				cnt = 1;
			}
			max_cnt = max(cnt, max_cnt);
		}
		cnt = 1;
		for (int j = 0; j < n-1; j++) {
			if (ca[j][i] == ca[j + 1][i])  cnt++;
			else {
				cnt = 1;
			}
			max_cnt = max(cnt, max_cnt);
		}
	}
	return (max_cnt);
}

int main() {
	int n;
	cin >> n;

	// 입력 받기
	vector<string> c(n);
	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}

	int m_candy = 0, ans = 0;
	for (int i = 0; i < n; i++) { // 모든 행, 열에 대하여 swap => check함수를 호출하여 최대연속수 리턴
		for (int j = 0; j < n; j++) { // 행
			if (i < n - 1) {
				swap(c[i][j], c[i + 1][j]);
				m_candy = check(c, n);
				ans = max(m_candy, ans);
				swap(c[i][j], c[i + 1][j]);
			}
			if (j < n - 1) { // 열
				swap(c[i][j], c[i][j + 1]);
				m_candy = check(c, n);
				ans = max(m_candy, ans);
				swap(c[i][j], c[i][j + 1]);
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

코드의 효율)

• check 함수를 따로 만들어, 간단하게 코드작성
• swap 함수
• 행과 열에 대하여 따로따로 작성하여 보기 편함
• vector 사용하여 편리

기억 할 것)

• vector 사용법 숙지할것
  https://velog.io/@soddong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-c-vector

문제3) 날짜계산 [1476]

문제를 풀기 전, 이게 브루트포스로 풀수 있는 문젠지 판단하는 것이 중요하다.
따라서 이문제의 경우의 수를 생각해보면,
1<=E<=15, 1<=S<=28, 1<=M<=19 이므로 모든 경우의 수는 152819 이다. 딱봐도 모든 방벙을 시도 가능하다.

기억 할 것)

• 늘 꼼꼼하게 접근 할것! 나의 경우, mod를 사용하기 위해서는 1을 빼주어야 하는데 이를 빼먹었다... 잘 생각할 것!

문제4) 리모콘 [1107]

이 문제는 풀다가 결국 방향을 못잡아 못풀었다.
이 문제처럼, 방법을 알수없는 경우가 브루트포스 사용!

문제를 풀때 중요한 것은 알고리즘의 단계를 분류하는것!
따라서 이문제의 경우,
1. 가장 가까운 채널 이동 (번호로)
2. 목표 채널까지 이동 (+/-로)

문제5) 테트로미노 [14500]

하... 5번은 다시 검토한 문제.....ㅠㅠㅠㅠㅠ
브루트포스 문제는 진짜 꼼꼼of꼼꼼할 필요가 있다.
기억 할 것)

• 배열에 모든 케이스를 (dx, dy)식으로 미리 저장하는 방식이 굉장히 유용했다.
• 브루트포스는 그냥 처음부터 끝까지 모두 훑는다! 라고 생각하기