완전 탐색 (Brute Force)
1. 완전 탐색이란?
가능한 모든 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다.
'무식하게 푼다'라는 의미인 Brute-Force (브루트 포스)라고도 부른다.
알고리즘을 모르는 사람이 프로그래밍 문제를 푼다면, 당연히 가능한 모든 경우들을 다 구해서 그중에 만족하는 답을 찾아낼 것이고 이 과정 자체가 완전 탐색이다. 대신에 이 방식은 절대 답을 못 구하는 경우는 없으므로 나름 강력한 방법이다.
하지만, 알고리즘을 사용할 때는, 기본적으로 2가지 규칙을 적용한다.
1. 사용된 알고리즘이 적절한가? ( 문제를 해결할 수 있는가 ) -> 만족
2. 효율적으로 동작하는가? -> 제한이 따르는 경우가 있음 (시간복잡도 측면)
2. 완전 탐색 기법 활용 방법
1. 입력으로 주어지는 데이터(N)의 크기가 매우 작다.
보통 프로그래밍 문제들을 풀게 되면 N = 10만, 20만 같은 크기를 주는 경우가 많다. 하지만 대부분의 경우 완전 탐색 문제는 N의 크기가 매우 작다. 부분집합 문제나, 순열, 조합 같은 문제들은 완전 탐색으로 푼다면 기본적으로 시간 복잡도가 O(2^N)이나, O(N!) 이므로 당연히 N의 크기가 매우 작아야 한다.
2. 답의 범위가 작고, 임의의 답을 하나 선택했을 때 문제 조건을 만족하는지 역추적할 수 있다.
N의 크기가 작으면 답의 범위 또한 작을 확률이 높기 때문이다.
답의 범위가 아주 제한적인 경우에는, 임의로 답을 고정시켜놓고 주어진 조건들이 답에 적합한지 역으로 확인해보는 방법을 이용해볼 수 있다. 가능한 답을 모두 확인하는 과정에서 완전 탐색이 이용되는 것이다.
3. 여러 문제 조건 중 한 조건을 고정시키면 문제 풀이가 간단해진다.
2번과 비슷한 방법이지만 답을 고정시키는 것이 아니라, 주어진 조건을 고정시키는 약간의 차이점이 있다.
3. 완전 탐색 기법
완전 탐색 자체가 알고리즘은 아니기 때문에 완전 탐색 방법을 이용하기 위해서 여러 알고리즘 기법이 이용된다.
주로 이용되는 기법들은 다음과 같다.
1. 단순 Brute-Force
- 어느 기법을 사용하지 않고 단순히 반복/조건문 등 모든 방법들을 단순히 찾는 경우를 의미한다.
- 이는 아주 기초적인 문제에서 주로 이용되거나, 전체 풀이의 일부분으로 이용하며, 따라서 당연히 대회나 코테에서는 이 방법만을 이용한 문제는 거의 나오지 않는다.
2. 순열
- 순열은 임의 의 수열이 있을 때, 그것을 다른 순서로 연산하는 방법을 의미한다.
- 즉, 순서가 중요하다.
- (수열에서 숫자 [1, 2, 3]이 있다면, 이것을 [1, 2, 3]으로 보는 순서와 [3, 2, 1]로 보는 순서가 차이가 있음이 중요한 경우를 의미한다.)
- 순열의 경우의 수는 N!으로 완전 탐색을 이용하기 위해서는 N이 한자리 수는 되어야 함. (재귀함수 이용)
- 시간복잡도 O(N!)
3. 재귀 함수
- 재귀는 말 그대로 자기 자신을 호출한다는 의미이다.
- 포함이 되면 해당 원소를 넣어 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출하는 등의 방식
- ex) 피보나치 수열
- 시간 복잡도 O(N)
4. 비트마스크(Bitmask)
- 2진수를 이용하는 컴퓨터의 연산을 이용하는 방식이다.
- 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용이 가능하다.
5. BFS / DFS
- 이는 그래프 자료 구조에서 모든 정점을 탐색하기 위한 방법
- DFS는 깊이 우선 탐색으로 트리의 한 요소(정점)와 다음 수준(level)의 자식 노드를 따라가는 방향으로 탐색하는 방식
- BFS는 너비 우선 탐색으로 현재 정점과 인접한 모든 정점을 우선으로 탐색하는 방식
- 약간의 난이도가 있는 문제로 완전 탐색 + BFS/DFS 문제가 많이 나온다.
- 대표적인 유형으로 길 찾기 문제가 있다.
- 단순히 길을 찾는 문제라면 BFS/DFS만 이용해도 충분하지만, 주어진 도로에 장애물을 설치하거나, 목적지를 추가하는 등의 추가적인 작업이 필요한 경우에 이를 완전 탐색으로 해결하고 나서, BFS/DFS를 이용하는 방식이다.
- 지구 상에 존재하는 모든 친구 관계를 그래프로 표현하고 A와 B 사이에 존재하는 경로 찾을 때
- DFS : 모든 친구 관계 다 살펴야한다.
- BFS : A와 가까운 관계부터 탐색한다.
'알고리즘' 카테고리의 다른 글
[알고리즘] 탐욕법(Greedy) (0) | 2024.02.06 |
---|---|
[알고리즘] 완전탐색 예제 # 1 단순 브루트포스 (0) | 2024.02.05 |
[알고리즘] Hash (1) | 2023.12.06 |
[알고리즘] 브루트 포스(brute force) (0) | 2023.05.01 |
[BOJ] 2738 : 행렬 덧셈 (node.js) (0) | 2023.03.26 |