[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

[ Contents ]

 

 

1. 브루트 포스란?

 Brute(짐승 같은, 난폭한) + Force(힘, 폭력)의 합성어입니다. 무식하게 푸는 기법으로, '노가다'에 가까운 접근법입니다. 모든 경우의 수를 시험해보며 문제를 해결합니다.

 

 브루트 포스 접근방법은 일상에서도 많이 사용합니다. 예를 들어, 자물쇠 비밀번호 4자리를 맞추기 위해 0000부터 9999까지 모두 시험해보는 것도 대표적인 '브루트 포스' 방식입니다. 

 

 

 

2. 순열과 조합

백준 10819 차이를 최대로

 경우의 수를 계산하다보니, 순열과 조합 기본지식이 필요합니다. 단순히 순서가 있는건 '순열', 순서가 없는 건 '조합'이라는 정도만 상기하시면 됩니다. 복잡한 수식을 외우지 않더라도, 이미 라이브러리로 구현되어 있습니다. 각 언어에서 지원하는 라이브러리를 불러오셔서 쓰시면 됩니다. (라이브러리의 함수가 직접 구현한 것보다 빠릅니다)

 

 하지만, 코딩테스트에서는 라이브러리를 못 쓰게 하는 경우도 많죠. 간단하게만 수식을 알아보겠습니다.

순열(Permutation)

조합(Combination)

 순열(Permutation)은 서로 다른 n개 중 r개를 순서 있게 선택하는 경우의 수입니다.

 조합(Combination)은 서로 다른 n개 중 r개를 순서 없이 선택하는 경우의 수입니다.

 

 

중복 순열

중복조합

 중복순열과 조합은 이미 선택한 것도 다시 선택할 수 있는 경우의 수입니다. 예를 들면, 4자리 수의 자물쇠 비밀번호가 중복순열입니다. 1099, 9999 등 같은 숫자를 중복해서 사용할 수 있습니다. 

 계산해보면, 10^4 = 10000가지가 나옵니다. (0000~9999)

 

 

3. 장점과 단점

 모든 경우의 수를 계산하니, 정확도는 100%입니다. 하지만 그만큼 시간이 오래 걸립니다. 알고리즘에서 '시간 복잡도'는 매우 중요하죠. 그런데 브루트 포스 방식은 비효율의 끝판왕이라고 볼 수 있습니다. 브루트 포스 방식으로 코딩 문제를 풀면, 시간 초과가 빈번히 나옵니다.

 따라서 알고리즘을 배울수록 잘 안 쓰는 방식입니다. 전공자들 사이에서 '노가다' 기법이라고 불리며, 비아냥거리기 일쑤입니다.

 

 하지만 저는 브루트포스 접근법을 제일 먼저 고려합니다. 문제를 이해하기에도 좋고, 간단하게 풀 수 있는 쉬운 방법이기 때문입니다. 문제 해결의 가장 기초적인 방법이므로 다른 알고리즘의 효율성을 비교하는 데에도 많이 쓰입니다. 기초 중에 기초인 만큼, 꼭 알고 가셨으면 좋겠습니다.