[알고리즘] Brute Force Algorithm(전수 조사 알고리즘)

Brute Force Algorithm(전수 조사 알고리즘)

모든 경우를 다 조사해보는 방법이다.

처음부터 끝까지 계산을 해나가며 해답을 찾는데, 이는 경우의 수가 제한적일 경우에만 사용 가능하다.

하지만 컴퓨터가 계산을 해나가기 때문에 생각보다 범위가 크다.

 

Brute Force의 종류

선형 구조 - 순차 탐색

비선형 구조 - DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

 

순차 탐색이 흔히 말하는 Brute Force라고 생각이 된다.

DFS와 BFS는 후에 따로 설명을 하겠다.

전수 조사 방법

전수 조사는 보통 재귀적으로 구현한다.

하지만 모든 재귀는 반복문을 이용해 동일한 기능을 구현할 수 있으므로, 반복문을 통해서도 구현이 가능하다.

 

가능한 모든 경우의 수를 전부 조사하는 방법이라 단순한 접근이지만,

모든 경우를 다 조사하는 프로그램을 작성하는 것이 간단하지 않을 수도 있다.

더 효율적인 방법이 있다면 굳이 전수 조사를 사용할 필요가 없다.

 

전수 조사 예제

백준에 있는 문제를 참고해보자.

https://www.acmicpc.net/problem/17614

17614번: 369

N을 입력했을 때 N까지 박수를 몇번 치는지 세는 문제이다.

박수의 수를 세기 위해서는 1부터 N까지를 보며 3, 6, 9의 숫자가 몇번 나왔는지 보면 된다.

예제입력1의 13을 보면 3, 6, 9, 13일 때 박수를 치므로 4번 박수를 치게 된다.

 

이를 코드로 짜보면 다음과 같이 된다.

자바를 사용해 코드를 쓰겠다.

int clap = 0;
for(int i=1; i<=n; i++) {
    int temp = i;
    while(temp != 0) {
        if(temp % 10 == 3 || temp % 10 == 6 || temp % 10 == 9) clap++;
        temp /= 10;
    }
}