Brute-Force Algorithm

완전 탐색 알고리즘

Brute-Force Algorithm

Brute + Force는 근성으로 노가다를 통해 답을 찾는다.

즉, 모든 가능성을 시도해보며 값을 찾는 방법이다. 예를 들면 4 digit 자물쇠가 있다고 할 때 자물쇠로 만들 수 있는 모든 경우의 수를 자물쇠가 풀릴 때까지 무식하게 하나하나 시도해보는 것과 같다.

모든 경우의 수를 다 확인하기 때문에, 시간 복잡도나 공간 복잡도를 신경 쓰지 않고, 최악의 시나리오가 오더라도 컴퓨터 성능에 의존해 '결과만 일단 찾아보자' 할 때 사용할 수 있는 방법을 의미한다.

Brute-Force 알고리즘은 크게 다음의 2가지 상황에서 사용한다.

요약하면, 완전 탐색 알고리즘은 더 적절한 해결 방법을 찾기 전에 시도하는 방법이다. 하지만 데이터의 크기가 커질수록 매우 비 효율적이기 때문에 큰 프로젝트를 한다면 더 효율적인 알고리즘으로 사용해야 할 것이다.

위에 적었듯이, Brute-Force 알고리즘은 꼼꼼하게 하나하나 모든 경우의 수를 체크해서 정확도 부분에서는 좋지만,
해당 문제의 시간적 + 공간적 복잡도에 굉장히 민감하다는 한계가 있다.

그렇기 때문에, 일반적으로 현재 문제의 규모가 현재 자원 (시간 / 컴퓨팅 자원 등)으로 충분히 감당 가능할 경우에 완전 탐색을 사용하게 된다.

완전 탐색은 그래도 많은 곳에서 사용하고 있고 나도 개념을 모르는 상태에서 썼을 수도 있다. 예를 들면, 반복문으로 배열의 범위를 줄이지 않고 배열 안의 값을 하나하나 찾아 비교한 케이스가 있다 (선형 탐색)

선형 탐색(Linear Search Algorithm)
- 배열 안에 특정값을 찾기 위해 모든 인덱스를 순회

문열 매칭(Brute-Force String Matching)
- 길이가 n인 전체 문자열이 길이가 m인 문자열 패턴을 포함하는지 탐색

선택 정렬(Selection Sort)
- 전체 배열을 탐색하여, 현재 요소보다 크거나 작은 요소를 오름차순 또는 내림차순에 따라 교환하여 정렬

버블 정렬(Bubble Sort)
- 선택 정렬과 비슷한 개념 / 인접한 원소끼리 비교해 교환하는 방식

BFS, DFS
- Tree 자료구조의 완전 탐색 - Exhausive Search(BFS, DFS)

Dynamic Programming
- 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 활용해서 효율적으로 답을 구함
- 답을 재활용