[알고리즘-문제] 브루트포스

._.·2021년 2월 28일

브루트포스

알고리즘 공부

목록 보기

2/13

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

문제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;
}