[알고리즘] 브루트 포스(Brute Force) 이해하기

[ 목차 ]

1. 정의

  
2. 예시

 

3. 정리

▶ 브루트포스(Brute Force) : 무식한 힘

• 영어 단어 그대로 무식하게 모든 경우를 탐색하는 완전탐색 알고리즘 (브루트포스 ≒ 완전탐색)
• 완전탐색은 보통 반복문과 조건문을 이용하여 진행
• 무식하게 하나씩 다 찾으니까 당연히 시간복잡도가 매우 큼
• 이전에 알아본 DFS, BFS 및 순차탐색을 이용하여 브루트포스 알고리즘을 구현할 수 있다.

 

◈ 순차탐색을 이용한 브루트포스 (예시)

• 순차탐색을 이용하기 위해서는 데이터가 선형구조를 이루어야한다.
• 선형구조로 이루어진 데이터를 순차탐색하며 계산을 수행하고 결과값을 도출한다.

예시로 백준의 1198번 : 삼각형으로 자르기 문제를 가지고 와보았다.

 

삼각형으로 자르기

 

2차원 좌표평면에서 다각형의 점의 좌표들을 입력받아, 도형을 잘랐을때 제일 커다란 삼각형의 넓이를 구하는 문제이다.

 

우선, 입력받은 다각형의 여러 점들은 선형 구조를 이룬다. (시계방향 순서로 2차원 좌표가 주어짐)

따라서 맨 처음 점부터 점 3개를 고를수있는 모든 경우의 수를 순차탐색하고, 각 경우의 삼각형의 넓이중 최댓값을 찾아 출력한다.

 

#include <stdio.h>
#include <math.h>

#define MAX_N 35

// 점의 좌표를 저장하는 구조체
typedef struct {
    int x, y;
} Point;

// 삼각형의 넓이를 계산하는 함수
double calculate_area(Point p1, Point p2, Point p3) {
    return fabs(p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y)) / 2.0;
}

int main() {
    int N;
    Point points[MAX_N];
    double max_area = 0;

    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &points[i].x, &points[i].y);
    }

    // 삼각형을 만들어 가면서 최대 넓이 찾기 (브루트 포싱)
    for (int i = 0; i < N - 2; i++) {
        for (int j = i + 1; j < N - 1; j++) {
            for (int k = j + 1; k < N; k++) {
                double area = calculate_area(points[i], points[j], points[k]);
                if (area > max_area) {
                    max_area = area;
                }
            }
        }
    }
  // 최대오차 10의 -9제곱을 맞추기 위해 소수점 9자리까지 출력
    printf("%.9f\n", max_area);
    return 0;
}

 

※for 반복문이 총 3번 사용되므로 O(n^3)의 시간복잡도를 가진다

 

▶출력 결과

 

 

 

맞춤

 

 

 

 

◈DFS,BFS를 이용한 브루트포스(예시 없음)

• 지난 1회차에 배운 DFS, BFS 를 이용하여 브루트포스를 구현할 수 있다.
• DFS와 BFS는 그래프적 구조의 탐색에 용이하여 그래프의 모든 지점들을 순회하며 작업을 수행한다.
• 브루트 포스에서는 특히 BFS가 용이하며, DFS는 사실 브루트포스보다는 백트래킹에 용이하다.

안타깝게도 예제를 찾지 못해, BFS를 이용한 풀이는 해볼 수 없었다(...)

 

 

 

---

 

 

 

▶정리

• 브루트 포스는 무식하게 모든 경우의 수를 탐색하는 완전탐색 알고리즘
•  DFS, BFS 및 순차탐색 알고리즘을 이용하여 구현이 가능하나, 찾아본 결과 순차탐색을 이용한 풀이가 가장 보편적.
• 순차탐색을 이용한 브루트포스 구현은 데이터가 선형구조이어야 함.