[알고리즘] 완전 탐색(Brute-force)

Jay·2021년 4월 17일
0

알고리즘-Concept

목록 보기
12/15
post-thumbnail

완전 탐색

  • 컴퓨터의 빠른 계산 능력을 활용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방식
  • 무식하게 풀어서 Brute-Force

"10개의 정수 원소로 이루어진 수열이 존재한다.
이 수열에서 두 원소를 선택해서 구한 합의 최대값을 구하시오"

위의 질문에 대한 방법은 결국 모든 경우를 다 구한 후 최대값을 구하는 것이다.
10C2=45개의 경우를 모두 구한 후, 최대값을 찾게 된다.

그러나, 위의 예시는 45개이기에 충분히 해결 가능하다.
하지만, 원소의 개수가 10만개 이상이라면? 경우의 수가 어마어마하다.
(물론, 저런 경우, 제한 된 시간에 구하지 못하기에 가장 큰 원소와 두번째 큰 원소를 찾아 더하면 답이 된다.)

그래서 완전 탐색 문제인지를 잘 파악하는게 중요하다

여러 알고리즘 기법

  • 단순 브루트 포스
  • 비트마스크
  • 재귀함수
  • 순열
  • BFS/DFS

기본적으로 완전 탐색은 N의 크기가 작을 떄 이용 되기에 보통 시간 복잡도가 지수승이나, 팩토리얼 형태로 나올 때 많이 사용된다.

실제 사용하려면?

1. 입력으로 주어지는 N의 크기가 매우 작다.
N=10만, 20만 인 경우도 많다. 하지만 대부분의 경우 완전 탐색 문제는 N의 크기가 매우 작다. 순열, 조합 같은 문제들은 완전 탐색으로 푼다면 기본적으로 시간복잡도가 O(2^N)이나 O(N!)이므로 당연히 N의 크기가 매우 작아야 한다.

2. 답의 범위가 작고, 임의의 답을 선택했을 때 문제 조건을 만족하는 지 역추적이 가능하다.
N의 크기가 작으면 답의 범위 또한 작을 확률이 높다.

Reference

profile
developer

0개의 댓글