[Algorithm] Brute Force

오늘 알아볼 알고리즘은 브루트 포스(Brute Force)라는 알고리즘이다.

사실, 학교 알고리즘 시간에 이 단어를 들어본 적은 없다. 하지만, 최근 모 기업에서 코딩테스트를 보고 관련된 문제가 나와서 한번 정리해봐야겠다는 생각을 했다.

 

브루트 포스의 사전적 의미

- 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법.
브루트 포스 공격(brute force attack) 또는 키 전수조사(exhaustive key search), 무차별 대입 공격(無差別代入攻擊) 등으로도 부른다. 흔히 수학 문제를 원시적으로 푸는 방법인 '수 대입 노가다'의 학술적 버전이다. 주로 암호학에서 연구되는 방법이나, 다른 알고리즘 분야에서도 사용되고 있다.

 

쉽게 말하면, 그냥 가능한 모든 경우의 수를 대입하는 알고리즘이다. 그러므로 시간이 굉장히 오래 걸리기도 하고, 자원이 많이 드는 비효율적인 알고리즘이라고도 할 수 있다. 하지만, 비효율적임에도 불구하고 정확도가 100%가 나온다는 점에서 가장 확실한 방법이라고 할 수 있다. 또한 브루트포스의 장점은 거의 완벽하게 병렬작업을 할 수 있다. 그래서 GPGPU, 병렬프로그래밍을 이용하여 문제를 해결하는 시간을 줄일 수 있다.

 

이건 이제 사전적인 의미이고, 코딩테스트에 나오는 브루트포스를 어떻게 해결해야 하는가? 에 대해 좀 궁금해졌다. 그럼 간단하게 문제를 하나 선택해서 직접 풀어봐야 할 것 같다.

 

선택은 최대한 간단한 문제로 해서 하려고 백준에서 뒤져봤다.

그래서 고른 문제는 정답률 67퍼센트인 1476번 날짜 계산 문제이다.

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.

출력

첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.

예제 입력 1 

1 16 16

예제 출력 1 

16

예제 입력 2 

1 1 1

예제 출력 2 

1

예제 입력 3 

1 2 3

예제 출력 3 

5266

예제 입력 4 

15 28 19

예제 출력 4 

7980

 

내가 보기에 여기 나오는 준규는 외계인이다. 팔이 4개가 달려있을지도 모른다. 뭐 이건 둘째치고 해결 방법에 대해서 고민해보자.

이 문제는 굉장히 쉬운 편이다. 어떤 식으로 풀면 되냐? 자. 순서를 한번 말해본다.

 

한턴 지날 때마다 우리 지구의 년도 카운트인 year카운트와 e,s,m카운트는 1씩 증가하고, e,s,m은 15, 28, 19가 될 때, 각 e,s,m 카운트는 1부터 시작한다. 이 때, e,s,m 카운트에 대해서 나눴을 때에 모두 나머지가 0이 될 경우 끝내버리면 된다.

코드로 나타내면 이렇다.

 

int main()
{
int e, s, m;
cin >> e >> s >> m;
// 1. e,s,m 입력받는다.

int eCount = 0, sCount = 0, mCount = 0;
int year = 0;

while (true)
{
if (eCount == e && sCount == s && mCount == m)
{
break;
}
else
{
year++;
eCount++;
sCount++;
mCount++;
if (eCount > 15)
{
eCount = 1;
}
if (sCount > 28)
{
sCount = 1;
}
if (mCount > 19)
{
mCount = 1;
}
}
}

cout << year << endl;

return 0;
}

 

정말 말 그대로 모든 경우의 수에 대해 조사하는 알고리즘이다. 물론 이 문제는 굉장히 간단한 문제이기에 이렇게 풀 수 있고, 좀 더 어려운 유형의 경우 훨씬 많이 생각해야 한다. 그래서 나도 못풀었다..(ㅜㅜ) 좀 더 연습해서 더 어려운 것도 풀 수 있도록 계속 연습해야겠다.