[알고리즘 패러다임 - 1] Brute Force

Brute Force (완전 탐색)

문제의 해가 될 수 있는 모든 경우의 수를 탐색하는 방식

문제를 푸는데 있어, 그 문제의 해가 될 수 있는 모든 경우의 수를 파악하는건 매우 중요하다. 필자는 문제를 풀 때 먼저 완전 탐색으로 풀 수 있는지 확인하고, 모든 경우의 수를 머릿속으로 생각하는 편이다. 만약 완전 탐색으로 시간 내에 풀지 못하면 문제의 조건에 따라서 DP, 그리디, 이진 탐색, 적절한 자료 구조를 사용해 최적화한다. 완전 탐색 시 재귀 호출을 사용하면 모든 경우의 수를 만드는 코드(순열, 조합··)를 쉽게 작성할 수 있기에 매우 유용하다.

 

경우의 수는 문제의 해 후보이며, 문제에 따라 다양한 상태를 가진다. (경로 문제의 경우 경로라는 상태를, 4x4 슬라이딩 퍼즐게임인 경우 퍼즐 맵을 상태로 가질것이다.)

 

[동작 방식]

1. 경우의 수를 완성시키기 위해 조각 하나를 선택해 상태의 일부로 설정
2. 나머지 상태를 완성시키기 위해 재귀 호출
3. 상태 값이 하나밖에 남지 않았거나 하나도 남지 않았으면 경우의 수를 완성시켰으므로 기저 사례(재귀 함수 종료조건)로 처리

아래는 4개의 수의 순열을 구하는 과정을 위 동작 방식에 맞추어 그림으로 나타낸 것이다. f₀와 같이 수행해야 할 작업과 작업을 적용할 자료의 조합을 문제라 하며 f₁과 같이 기저 사례에 도달하도록 원래 문제의 인자가 간단하게 조작된 문제를 원래 문제의 부분 문제라 한다.

Brute Force 동작 방식