알고리즘 완전탐색 Brute force search

완전탐색 알고리즘이란?

'모든 경우의 수를 전부 찾아서 답을 찾는 알고리즘' 을 뜻한다. 영어로는 Brute force Search 라고 한다. 가능한 모든 경우의 수를 다 해보는 것이다. 알고리즘을 풀때 가장 강력하고 확실한 방법이지만 그만큼 시간이 가장 오래 걸리는 탐색 기법이다

완전탐색 기법

• 단순 Brute force Search
• 비트마스크(Bitmask)
• 순열 (Permutation)
• BFS / DFS

연습 문제

문제 조건.

이 문제에서 첫번째로 생각해야 할 것은 약수를 어떻게 구할 것인지 생각해 본다. 약수는 1부터 자기자신까지 나누었을때 나누어 떨어지는 수를 약수라고 한다. 그리고 두번째 짝수인지 홀수인지 어떻게 구분할 것 인가. 이문제에서 두개만 생각하면 쉽게 풀수 있다.

문제 풀이.

• 입력값을 num으로 받고 약수의 개수를 세는 cnt 약수의 개수가 홀수인 숫자들의 개수를 담은 result를 선언.
• 이중for문을 이용해서 i % j 를 나누었을때 나머지가 0이면 cnt에 1을 더해줌.
• 두번째 for문이 끝나고 cnt를 2로 나누었을때 나머지가 1이면 홀수이니깐 result에 1을 더해줌
• 다 끝나면 result에는 약수의 개수가 홀수인 수들의 개수가 담겨있으니 result 출력.

문제 코드.

import java.util.Scanner;
public class Main{
    public static void main(String[] args){

       Scanner s = new Scanner(System.in);
       int num = s.nextInt();
       int cnt, result = 0;
       
       for (int i=1;i<=num;i++){
         cnt = 0;
         for (int j=1;j<=i;j++){
           if (i % j == 0) cnt++;
         }
         if (cnt % 2 == 1) result++;
       }
       System.out.println(result);
    }
}