[Algorithm] BruteForce

0. 정의

BruteForce란, '무식하게 풀어본다'는 말 그대로, 모든 가능한 경우의 수를 하나하나 늘어놓아 가며 그 답을 구하는 알고리즘이다. 다른 말로는 완전 탐색(Exhaustive Search) 이라고도 한다. 

사람이 일일이 손으로 나열해 가며 풀기에는 그 경우의 수가 너무 방대하나, 컴퓨터라면 충분히 계산할 수 있기 때문에 어찌 보면 컴퓨터의 성능을 가장 잘 활용할 수 있는 방법이다. 가장 아름답지 못해 보이는 풀이법이 가장 컴퓨터의 순수성과 닿아 있는 방법이라고 할 수 있다.

 

1. 접근법

for, while문 등의 방법을 통해 접근할 수도 있고, 주로 재귀호출(recursive call)을 사용해 접근한다. 재귀호출을 사용할 때는 반드시 Base case를 올바르게 설정하여 무한 재귀호출의 늪에 빠지지 않도록 주의해야 한다.

 

2. 시간 복잡도

 이번에 책을 통해 다시 공부하면서 새로이 알게 된 부분이자, 이미 대강 알고 있던 알고리즘도 다시 공부하면서 포스팅을 하자고 마음먹는 계기가 된 부분이다. 

 BruteForce는 가능한 모든 경우의 수를 탐색하기 때문에 input 수와 문제 해결에 걸리는 최대 시간이 정비례한다. 때문에 나는 BruteForce 알고리즘의 시간 복잡도는 Big-O notation으로 나타내었을 때 O(n)이라고 알고 있었으나, 이는 사실이 아니다. 

 가령 십자말 풀이 퍼즐에 n글자짜리 특정 단어가 있는지를 BruteForce로 찾는다고 하자. 십자말 풀이에서 '인접 칸'은 최대 8칸이다.(전후좌우 및 4개의 대각선 방향) 이 경우 n글자짜리 글자를 찾기 위해서는 각 node(한 글자) 마다 최대 인접 8칸에 대해 재귀호출을 하는 것을 n-1회 하여야 한다. 따라서 이 경우에 time complexity는 O(8^n)이다. 

 따라서 시간 복잡도에 관해서는, BruteForce 알고리즘의 경우 문제 해결에 걸리는 시간이 input 크기에 정비례하기에  주어진 input 크기와 제한 시간에 따라 해당 알고리즘을 사용할 수 있는지 없는지를 파악하는 능력을 길러야 할 것이다.

 

3. 대표 유형

- Permutation

- Combination

- 2^n 가지 경우의 수 조합 생성

 

* 참고 도서: 구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2020, 145~172p