브루트포스 알고리즘 = 전체 탐색 기법

브루트포스(brute force)

무식하게 모든 가능한 경우의 수를 탐색하면서 요구 조건에 충족되는 결과를 가져오는 알고리즘이다.

 

좋은 점은 100%의 확률로 정답만을 출력할 수 있다.

 

 

- 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상할 수 있는 모든 영역을 전체 탐색한다.

- 선형 전체를 탐색하는 순차 탐색

- 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색과 너비 우선 탐색이 가장 기본적인 도구다.

 

 

 

알고리즘 구성방법

1. 주어진 문제를 선형 구조로 구조화한다.
2. 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.
3. 구성된 해를 정리한다.

 

 

 

10의 약수의 합을 구하기

package bruteforce;

import java.util.Scanner;

public class Divisorsum {
	public static void main(String[] args) {
		// 10의 약수의 합 구하기
		// 브루트포스 알고리즘의 방법
		
		// 1. 10의 약수가 될 수 있는 모든 자연수를 구조화한다.
		Scanner sc = new Scanner(System.in);
		
		int[] div = new int[sc.nextInt()];
		int thenum = sc.nextInt();
		
		for (int i=0;i<div.length;i++) {
			int n = sc.nextInt();
			div[i] = n;
		}
		
	//	int[] div = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
		// 문제의 해가 될 수 있는 자료를 우선 선형으로 구성.
		
		// 구조화된 자료가 선형 구조이므로, 순차 탐색을 통해서 첫 번째 원소부터
		// 마지막 원소까지 탐색한다.
		// 원소로 10을 나누었을 때 나누어 떨어지면 그 원소를 10의 약수라고 하므로
		
		// 약수의 합 초기화
		int sum = 0; 
		
		for(int i=0; i<div.length;i++) {
			if(thenum%div[i] == 0) {
				sum += div[i];
				
			
			}
			
			
			
		}
		System.out.println(sum);
		
	}
	
}

위와 같이 입력했을 때 18이라는 값을 얻을 수 있다.

 

1. 입력받은 값을 배열로 저장한다.

2. 합계 정보를 담을 변수를 만들고 초기화한다.

3. 타겟숫자를 나누었을 때 나머지 값이 없는 값을 모두 더하는 for문을 구성하고

4. for문 이후에 출력한다.