[알고리즘] 완전탐색: 브루트포스(brute force) 알고리즘

완전탐색: 브루트포스(brute force) 알고리즘

Brute: 무식한

Force: 힘

직역하면, 무식한 힘이라는 뜻으로 이름에 걸맞게 가능한 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다.

대부분 반복문과 조건문을 통하여 답을 도출한다.

 

브루트포스의 장점

• 알고리즘을 설계하고 구현하기 쉽다.
• 모든 경우의 수를 탐색하기 때문에 예외 없이 100%의 확률로 정답만을 출력한다.

브루트포스의 단점

• 메모리 효율면에서 매우 비효율적이다.
• 알고리즘의 실행 시간이 매우 오래 걸린다. -> 시간복잡도가 높다.

 

브루트포스 알고리즘의 사용 조건

1. 문제에서 달성하고자 하는 솔루션이 잘 정의 되어 있어야 한다. 

• 솔루션이 잘 정의되어 있지 않는 문제라면, 브루트포스를 사용한 솔루션이 올바른지의 여부를 확인할 수 없다.

2. 문제를 해결할 수 있는 풀이의 수가 제한되어 있어야 한다.

• 문제에서 고려해야 할 솔루션의 수가 한정되어 있어야 한다. 고려해야 할 솔루션의 수가 무한하거나 너무 크면 브루트포스 알고리즘은 효율적이지 않은 방법이다.

 

브루트포스의 종류

• 선형 구조: 순차 탐색
• 비선형 구조: 백트래킹, 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

* 비선형 구조는 추후 포스팅 예정

 

선형 구조 문제 해결방법

1. 주어진 문제를 선형 구조로 구조화 한다.

2. 구조화 된 문제 공간을 적절한 방법으로 해를 구성할 때까지 탐색한다. 

3. 구성된 해를 정리한다.

 

브루트포스 예제

분해합 - https://www.acmicpc.net/problem/2231

 

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M의 생성자라 한다. (예: 512는 520의 생성자 -> 512 + (5 + 1 + 2) = 520이기 때문에)

어떤 자연수는 생성자가 없을 수도 있지만, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때 N의 생성자들 중 가장 작은 생성자를 찾아 출력해야 한다.

 

알고리즘 설계

1. 0부터 N-1까지 모든 자연수를 하나씩 대입하여 탐색

2. 만약 탐색 도중 생성자를 찾으면 종료하고 해당 생성자를 출력

3. N을 넘길 때 까지 생성자를 찾지 못하면 0을 출력

 

코드

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
 
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); 
        
		int result = 0; // 생성자 초기화
 
		// 0부터 N-1까지 모든 자연수 M을 탐색
		for(int i = 0; i < N; i++) {
			int number = i;
			int sum = 0;	// 각 자릿수 합 변수 
			
			// 현재 숫자 i의 각 자릿수를 더함
			while(number != 0) {
				sum += number % 10;	
				number /= 10;
			}
			
			// i 값과 각 자릿수 누적합이 같을 경우 (생성자를 찾았을 경우) 
			if(sum + i == N) {
				result = i;
				break;
			}
		}
		System.out.println(result);
	}
}