알고리즘 완전탐색(브루트 포스)에 대해 알아보자

서론

 

오늘은 금요일이다. 몸이 많이 지치고 힘들지만, 글은 써야하니까. 특히 요즘 글을 제대로 못쓰기 때문에 주말에는 좀 더욱 열심히 써야한다. 내일은 파이썬 강좌를 마저 쓰도록 하겠다.

 

완전탐색(브루트 포스)이 뭘까?

 

완전탐색은 말 그대로 모든 경우의 수를 전부 닥치는대로 해보는 것이다. 실생활에서 예를 들자면, 자물쇠를 열어야하는데, 열쇠 꾸러미 중 맞는 열쇠가 뭔지 모른다면, 열쇠 꾸러미에 있는 모든 열쇠를 다해보는 것처럼. 무식하게 전부 다 대입해보는 방법이다. 만들기 쉽고 간단하지만, 그만큼 수행시간이 상당히 긴 알고리즘이다.

완전탐색을 하는 방법은 이렇게 있다.

• for if  사용하기
• 비트마스크
• 재귀함수
• BFS

그 중 가장 간단한 for if를 사용하는 방법을 알아보자.

 

예시

 

정렬되지 않은 배열 안에 입력 값 n 의 약수가 있는 지 찾고 있다면, 그것을 전부 더한 값을 출력하라.

 

#include<stdio.h>

int main(){
    int a[10] = {3,4,1,9,8,7,5,10,2,6};
    int n, sum = 0;
    scanf("%d", &n);
    for(int i=0; i<10; i++){
        if(n%a[i] == 0){
            sum += a[i];
        }
    }
    printf("%d", sum);
    
}

C로 짠 코드인데, 이건 구현문제 같기도하고, 브루트포스 같기도 하고.. 아무튼

배열을 처음부터 끝까지 돌리면서, n이 a[i]로 나눠지는 지 계속 검사하는 코드이다.

이렇게 머리부터 발끝까지 해보는 게 특징이다. 

 

 

다만 지금은 배열의 크기가 10이라 괜찮지만, 1000이 되고 10000000이 된다면? 

실행속도는 상당히 길어진다는 단점이 있다.