1. 완전탐색이란?
- 모든 경우의 수를 고려하는 탐색 알고리즘
- 영어로는 Exhaustive Search라고 한다. 가능한 모든 경우의 수를 다 해보는 것이다. 알고리즘을 풀 때 가장 확실한 방법이지만 그만큼 가장 시간이 오래걸리는 기법이다.
ex) 4자리 암호를 풀기 위해 0000~9999까지 모두 시도해보는 것 ( 가장 확실하지만, 가장 오래걸린다 )
- 해당 기법을 문제해결 알고리즘에 사용 할 때, 2가지 규칙을 적용한다.
1. 사용된 알고리즘이 해당 문제를 해결하기에 적절한가?
2. 효율적으로 작동하는가?
대부분의 경우 2번에서 미충족된다.
다양한 문제를 이 기법으로 해결 하기에는 비효율적이라는 것이다.
따라서 완전탐색 기법을 사용 시 그 문제에 대한 파악이 중요!
2. 완전탐색 기법의 종류
1) 브루트 포스 (Brute Force)
- for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법
직역하면 '무식한 힘'으로 해석되며, 이 방법만으로는 대회나 코딩테스트 문제를 해결하긴 어려움.
2) 비트마스크
- 이진수 표현을 자료구조로 사용 (and, or, xor, shift, not)
각각의 원소가 포함되거나, 포함되지 않는 두가지 선택으로 구성되는 경우 유용하게 사용 가능
비트마스크로 무엇을 할 수 있을까?
- 정수로 집합을 나타낼 수 있다.
ex) {1, 3, 4, 5, 9} = 570 = 2^1 + 2^3 + 2^4 + 2^5 + 2^9
- 굳이 비트마스크를 쓰는 이유는? 공간적인 이유, 정수 하나로 배열을 대체할 수 있어서
3) 백트래킹
- 분할정복을 이용한 기법, 해를 찾아가는 도중 해가 될 것같지 않은 경우가 있다면 더 이상 가지 않고 돌아간다.
* 재귀함수 설계 시 고려해야 할 아주 중요한 개념 *
if(sum >= 50) return; 한 줄짜리 코드의 효율성은 엄청나다.
4) 재귀함수
- 함수 내에서 함수 자기 자신을 계속해서 호출
비트마스크와 마찬가지로 주로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택을 가질 때 이용된다.
5) 순열
- 서로 다른 n개의 원소에서 r개의 중복을 허용하지 않고 순서대로 늘어 놓은 수
6) DFS(깊이 우선 탐색) & BFS(너비 우선 탐색)
- DFS : 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동 (스택 또는 재귀함수로 구현)
1) 모든 노드를 방문하고자 하는 경우 이 방법 선택
2) 깊이 우선 탐색이 너비 우선탐색보다 더 간단함
3) 검색 속도 자체는 너비 우선 탐색에 비해 느림
- BFS : 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동(큐를 이용해 구현)
1) 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
2) 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법 선택
3. 완전탐색 기법 사용방향
1) 문제에서 가능한 경우의 수를 대략적으로 계산
2) 가능한 방법 다 고려 (위의 6가지 방법)
3) 실제로 답을 구할 수 있는지 생각
'Algorytm > 기초' 카테고리의 다른 글
| [Algorythm-기초] 그리디 (0) | 2022.12.06 |
|---|---|
| [Algorythm-자료구조] 해시 (0) | 2022.12.03 |
| [Alhgorythm-개념] 정렬 (0) | 2022.12.01 |
| [Algorythm-개념] 동적 계획법 (1) | 2021.09.28 |