210205[algorithm]Bruteforce

브루트포스란?

암호학에서의 bruteforce attack이 아닌,

알고리즘적인 차원에서 bruteforce란 다음과 같다.

• brute : 무식한, force : 힘

• 컴퓨터의 강력한 연산속도로 가능한 모든 경우의 수를 탐색하면서 요구 조건에 충족되는 결과를 가져온다.

• 선형구조를 전체적으로 탐색하는 순차 탐색,

• 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 등이 가장 기본적인 도구이다.

문제 적용 방법

• 주어진 문제를 선형구조로 구조화한다.
• 구조화된 문제 공간을 적절 한 방법으로 해를 구성할 때까지 탐색한다.
• 구성된 해를 정리한다.

예제

• 10의 약수의 합을 구하기

• 10의 약수가 될 수 있는 모든 수 ⇒ 정수겠죠?

  { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} → 문제의 해가 될 수 있는 수를 선형으로 구성하였다.

• 자료가 선형이므로, 순차탐색으로 첫 원소부터 마지막 원소까지 탐색한다.

• 만약 해당 인덱스가 10에 나누어 떨어진다면 약수이기 때문에, 결과값에 더해준다.

• 최종적으로 1, 2, 5, 10이 더해져서 18이 된다.

가능한 모든 경우의 수를 구할 때나, 수학적 공식을 세우기 어려울 때 사용한다.
단, Bruteforce 알고리즘은 때에따라 시간복잡도가 엄청나게 증가할 수 있다.
그 점에 유의하여 코드를 짜야한다.

다음은 BOJ bruteforce문제를 풀다가 시간초과가 났었던 문제이다.

BOJ 12971번

풀이

• 주어진 조건대로 하면 알고리즘을 짜는 건 아주 쉽다.
• 하지만 아무생각 없이 제출하면, 시간초과가 걸린다.
• 당연하게도, N이 10억까지 도는 것을 확인해야 하기 때문이다.
• 그렇다면, 이 10억까지 체크하지 않기 위해서는 어떻게 해야할까?
• 다음과 같이 생각해보자.
  • N : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...
  • 다음은 N % x 값을 나열해 보겠다.
  • 2 : 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...
  • 3 : 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 ...
  • 5 : 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1...
  • 눈치가 빠르다면 알아챘을텐데, N을 각 수로 나눈 나머지 값에는 "주기성"을 띈다!!!
  • 한번 나왔던 것은 무조건 다시 나온다.
  • 2의 주기 2, 3의 주기 3, 5의 주기 5 를 다 곱하면 30이 나온다.
  • 즉, 2와 3과 5의 최소공배수이자 모두의 주기는 30이라는 뜻이다.
  • 따라서, 0 ~ 30 , 30 ~ 60, 60 ~ 90 ... 각 범위에 따른 결과값은 무조건 같을 수 밖에없다! (주기니까!)
  • 그렇기 때문에, 0 ~ 30 이후로 한번 더 맞는게 있나 없나 살펴보는 것은 무의미한 짓이다.
  • 따라서, 0 ~ 30 까지만 찾아보고, 만약에 찾고자 하는 값이 없으면 10억, 100억, 10000억까지 찾아봐도 절대 안나올 것이다.
  • 이 방식으로 경우의 수를 10억에서 P1 P2 P3 로 확 줄일 수 있다.
  • 참고로 각 P1, P2, P3 ≤ 300 이기 때문에 아무리 커봤자 270000이라는 10억에 비하면 하찮은 수 까지만 비교하면 된다.

코드

#include <iostream>

using namespace std;

int main(void)
{
	int p1, p2, p3, x1, x2, x3;

	cin >> p1 >> p2 >> p3 >> x1  >> x2 >> x3;
	int N;
	for (N = 1; N <= p1 * p2 * p3; N++) 
	{
		if (N % p1 == x1 && N % p2 == x2 && N % p3 == x3)
		{
			cout << N << endl;
			return (0);
		}
	}
	cout << "-1" << endl;
}