[알고리즘] 브루트 포스(Brute Force)

브루트 포스란?

브루트 포스 알고리즘은 완전 탐색이라고 하는데 의미로는 다음과 같다.
컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 모두 나열하여 답을 찾는 방법을 의미한다.
브루트 포스의 사전적의미로는 brute = 무식한, force = 힘의 뜻으로 '무식하게 푼다' 라고도 한다.
당연히 가능한 모든 경우들을 다 구해서 그중에 만족하는 답을 찾아내는 과정이 완전 탐색이다. 이 방식은 답을 못구하는 경우가 없기에 강력한 방법이다. 완전 탐색 자체가 알고리즘은 아니고 이 방법을 이용한 알고리즘 기법들은 여러가지가 있다.

• Brute-Force
• Bitmask
• 재귀 함수
• Permutation
• BFS/DFs

브루트 포스의 적용

단순히 반복문과 조건문을 활용해서 모든 case를 만들어 답을 구하는 방법으로 기초적인 문제를 다룰때 쓰인다. 또는 전체 풀이의 일부분을 차지한다.

문제 해결방법은 다음과 같다.
1.주어진 문제를 선형 구조로 구조화 한다.
2.구조화된 문제공간은 알맞은 해를 구할때까지 탐색한다.

[백준]1436 영화감독 숌

---

본인은 코드의 길이의 비해 시간을 생각보다 많이 쓰게된 문제였다. 문제에서 "적어도 3개 이상 6이 연속으로 들어가는 수"를 해결할 수 있다면 이 문제는 끝이다.

해결 방법
1. 가장 작은수 666부터 시작한다.
2. int형 값을 String 으로 변환하여 문자열 안에 "666"이 포함되는지 확인한다.
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 i = 666;
        while(true){
            if(Integer.toString(i).contains("666"))
                N--;
            if(N == 0)break;
            i++;
        }
        System.out.println(i);
    }
}

위에 코드에서 i값을 1씩 증가시키면서 N값을 만족하는 값을 찾을때 까지 반복분을 도는 것에서 브루트 포스의 특징을 찾아볼 수 있었다.