(C++)알고리즘 탐구 5. 브루트 포스 (1/2) (풀이, 알고리즘 분석)

참고도서 : 파이썬 알고리즘 인터뷰 . 박상길 .  책만 . 2020
참고도서에서 언급하는 알고리즘 주제를 참고하여  C++로 풀어보는 것을 목표로 합니다. 

알고리즘을 공부하면서도 소프트웨어적 설계를 추가합니다. 답을 내는 코드를 짜는게 아니라 각각이 모듈이 되어 서로 맞물려 동작하는 코드를 짜는 것을 목표로합니다. (그래서 다른 글보다 코드가 깁니다.)

참고로 상위 레벨의 코드를 볼 수록
using namespace std; 라는 코드가 보이지 않아, 없이 진행합니다.

---

브루트 포스

모든 조합을 일일히 확인해보는 무차별 대입 방식입니다.

문제집: 브루트포스 (연습) (scbsoccer)

다음의 문제집의 문제를 풀어봅니다. 브론즈와 실버 정도의 레벨을 풀면서 브루트 포스 알고리즘의 원리를 깨닫도록 하자.

 

문제는 난이도 순으로 풀어보도록 합니다.

9094번: 수학적 호기심 (acmicpc.net)

9094번: 수학적 호기심

 

뭔지 모르지만 주어진 수식에 결과값을 내고, 이게 정수인가를 판정하는 문제입니다.

문제를 이해하는게 좀 난해하네요.. 그냥 만들어버립시다.

 

solution 함수를 하나 만듭시다.

그러면 인풋으로 a와 b를 받고 수식을 풀어내는 함수가 필요할 것입니다. 

여기서 정수 여부를 판정하고 count하고  int를 반환합시다.

 

그래서 처음에는 이렇게 짜보았다.

int solution(int n, int m) {
	double integer;
	int count = 0;
	for (int a = 2; a < n; a++) {
		for (int b = 1; b < a; b++) {
			integer = ((double)a * (double)a + (double)b * (double)b + (double)m) / ((double)a * (double)b) % 1;
			if (integer == 0)
				count++;
		}
	}
	return count;
}

그랬더니 이런 오류를 뱉었다. double형은 나머지를 구할 수가 없다니..

그래서 생각난 방법은 실수 - 정수로 나머지가 있으면 count++ 하자

int solution(int n, int m) {
	double integer;
	int count = 0;
	for (int a = 2; a < n; a++) {
		for (int b = 1; b < a; b++) {
			integer = ((double)a * (double)a + (double)b * (double)b + (double)m) / ((double)a * (double)b);
			if (integer - (int)integer == 0)
				count++;
		}
	}
	return count;
}

int main() {
	int t; std::cin >> t;
	int n, m;
	while (t--) {
		std::cin >> n >> m;
		std::cout << solution(n, m) << "\n";
	}
	
}

결과는 맞게 나온다. 체점하러가자..

 

그러면 남들을 이를 어떻게 풀었고, 브루트 알고리즘이 어떻게 적용된걸까?

for (int a = 2; a < n; a++) {
		for (int b = 1; b < a; b++) {
			integer = ((double)a * (double)a + (double)b * (double)b + (double)m) / ((double)a * (double)b);
			if (integer - (int)integer == 0)
				count++;
		}
	}

이 부분에서 모든 정수쌍을 확인했다. 이게 브루트 알고리즘이다.

 

다른 사람의 풀이를 보니

너무 어렵게 생각을 했었다. 결국 

이 값의 나머지가 0이 아니면 정수가 아니다.

int solution(int n, int m) {
	double integer;
	int count = 0;
	for (int a = 2; a < n; a++) {
		for (int b = 1; b < a; b++) {
			if ((a * a + b * b + m) % (a * b) == 0)
				count++;
		}
	}
	return count;
}

다음처럼 변환하면 정답이 나온다.

 

---

다음 문제를 보자.

2858번: 기숙사 바닥 (acmicpc.net)

2858번: 기숙사 바닥

빨간색이 방을 둘러싸고 있으며, 중앙에는 갈색으로 채워진다.

빨간색과 갈색이 주어질때 이를 어떻게 구할 수 있을까?

수학적인 방법을 찾을 수 있지만, 브루트 뭐시기 알고리즘을 써서 구해보자.

 

갈색의 개수는 결국 가장자리의 개수로

3 X 3 에서 8개, 4 X 3 에서 10개를 가진다.

그러면 그림을 그려보자.

색을 잘못그렸는데, 가장자리가 빨간색이다.

가장자리는 2*L + 2 * (W-2) 이다. 

가장자리는 2*L + 2 *(W-2) 이다. 

그러면 내부 = L * W - 가장자리 로 구할 수 있다.

 

 

그러면 이를 이제 한 번 구현을 해보자.

solution함수에는 brown과 red를 입력받고 

W 와 L을 return 하자 

파이썬의 경우에는 두 가지 값을 반환시킬 수 있다. (타입지정이 없어서)

 

그래서 그냥 vector를 return 시켜도 된다. 아니면 배열을 리턴시켜도 좋다.

우선 뼈대와 main 함수는 어렇다

#include <iostream>
#include <vector>

std::vector<int> solution(int brown, int red) {
	
}

int main() {
	int brown, red;
	std::cin >> brown >> red;
	for (auto& i : solution(brown, red)) {
		std::cout << i << " ";
	}
}

 

어찌 되었든 brown 과 red 값을 더한 값이 W * L 보다 높을 수 없다. 그러므로 이에 맞게 코드를 짜야한다.

 

우선 solution 함수는 다음과 같다

std::vector<int> solution(int red, int brown) {
	std::vector<int> answer;
	int W = 1;

	while (true) {
		int L = 1;
		if (W * L > brown + red)
			break;

		while (true) {
			if (W * L > brown + red)
				break;

			if ((2 * L + 2 * (W - 2)) == red && (W * L) - (2 * L + 2 *(W - 2)) == brown) {
				answer.push_back(L);
				answer.push_back(W);
				return answer;
			}
			L++;
		}
		W++;
	}
}

vector를 리턴한다. 그래서 위에서 설명한 알고리즘을 넣었으며, 결과는 맞게 나온다.

정답 

 

다른 사람의 코드를 보면서 알아보자.

hidercpp 님의 코드이다.

#include <iostream>

int main(){
    using namespace std;
    int n, m;
    cin >> n >> m;
    m += n;
    n = (n + 4) / 2;
    for (int i = n - 1; i > 0; i--){
        if (i * (n - i) == m){
            cout << i << ' ' << n - i << '\n';
            return 0;
        }
    }
    return 0;
}

밤이라 머리가 안도는건가..

나중에 알아보겠습니다.

 

 

---

3040번: 백설 공주와 일곱 난쟁이 (acmicpc.net)

3040번: 백설 공주와 일곱 난쟁이

9개의 수 중에서 합이 100이되는 7개를 찾으라는 것이 결국 이문제가 요구하는 것이다.

그리고 입력은 현재 개행문자로 받아지고 있음으로 cin을 for문으로 돌려야한다.

일단 9개의 숫자를 모두 더하고 빼는 것이 시간상으로 빠를 것이다.

그러면 벡터를 참조하는 solution 함수를 만들자. 그리고 벡터로 반환하지 말고, 아예 삭제를 해버리자.

그러면 함수의 역할은 명확하니 main함수와 뼈대를 만들자

만들고 보니 sum을 그냥 함수로 보내주면 for문을 하나 줄일 수 있다.

#include <iostream>
#include <vector>

void solution(std::vector<int> &v, int sum) {

}

int main() {
	std::vector<int> v;
	int t = 9;
	int sum = 0;
	int temp;

	while (t--) {
		std::cin >> temp;;
		v.push_back(temp);
		sum += temp;
	}
    
	solution(v, sum);
	for (auto& i : v ) {
		std::cout << i << "\n";
	}
}

근데, void로 하면 브루트 포스 알고리즘이 모두다 돌아야한다. 찾으면 return 할 수 있게 bool 타입이라도 주자.

#include <iostream>
#include <vector>

bool solution(std::vector<int> &v, int sum) {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (i != j){
				if (sum - v[i] - v[j] == 100) {
					if (i < j) {
						v.erase(v.begin() + i);
						v.erase(v.begin() + j-1);
					}
					else {
						v.erase(v.begin() + i);
						v.erase(v.begin() + j);
					}
					 
					return true;
				}
			}
		}
	}
	return false;
}

int main() {
	std::vector<int> v;
	int t = 9;
	int sum = 0;
	int temp;

	while (t--) {
		std::cin >> temp;;
		v.push_back(temp);
		sum += temp;
	}
	solution(v, sum);
	for (auto& i : v ) {
		std::cout << i << "\n";
	}
}

일단 터미널상에서는 맞게 나온다.

 

다른 사람의 코드를 보고 싶어도 이 주제는 for문이 복잡해서 참고를 못하겠다.