완전 탐색
브루트-포스 알고리즘
브루트 포스 알고리즘은 검색 대상이 되는 원본 문자열의 처음부터 끝까지 차례대로 순회하며 문자들을 일일이 비교하는 방식의 고지식한 알고리즘이다. 비교하고자 하는 문자열과 패턴을 한 칸씩 이동하면서 비교하여 일치 여부를 확인한다.
브루트-포스 알고리즘 비교 과정
T : 원본 문자열, P : 찾고자 하는 문자열 패턴
- T, P 모두 첫 문자부터 비교를 시작하므로 검색 인덱스를 맨 처음 인덱스로 설정한다.
- 각각의 검색 인덱스부터 하나씩 문자를 비교한다.
① 비교 문자가 같으면 T, P 인덱스 모두 뒤로 한 칸씩 이동합니다.
② 비교 문자가 다르면 T의 인덱스는 한 칸 뒤로 이동하고, P의 인덱스는 맨 처음 인덱스로 돌아갑니다. - 다시 2번 과정부터 검색이 끝날 때까지 반복합니다.
브루트-포스 알고리즘 시간복잡도와 장단점
- 시간 복잡도 : O(mn)
- 찾으려는 문자열 패턴의 길이 m, 총 문자열의 길이 n
- 장점 : 구현이 쉬운 편이고, 100%의 확률로 정답을 출력한다.
- 단점 : 모든 자료를 탐색하므로 시간적으로 매우 비효율적이다.
브루트-포스 알고리즘 구현
def bruteForce(p, t):
i = 0 # t의 검색 인덱스
j = 0 # p의 검색 인덱스
while i < len(t) and j < len(p):
if t[i] != p[j]:
i -= j
j = -1
j += 1
j += 1
if j == len(p):
return i - len(p)
else:
return -1백트래킹
- 모든 가능한 경우의 수를 탐색하는 알고리즘
백트래킹은 트리 자료구조에서 그래프 탐색의 변형된 모습이다. 대부분의 백트래킹 알고리즘은 깊이 우선 탐색(Depth First Search)의 형태를 가지고 있다. 모든 경우의 수를 탐색하는 깊이 우선 탐색과는 다르게 백트래킹은 유망하지 않다고(non-promising) 판단된 노드는 배제한다.(purning) 즉, 해당 노드가 유망한지(promising) 검사하여 해가 될 수 있는 경우에만 자식노드를 탐색하는 것이다.
- 특정한 집합(set)에서 어떤 기준(criterion)을 만족하는 원소들의 순서(sequence)를 선택하는 알고리즘
또한 백트래킹은 각 원소들을 순서대로 방문(DFS)하면서 기준을 만족하는지(promising) 검사한다. 따라서 수열이나 순열과 조합을 구하는 문제를 푸는 방법이 될 수 있다.
백트래킹 기법
-
상태 공간 트리(State Space Tree)
백트래킹은 상태공간트리를 갖는다. 상태공간이란 해답을 탐색하기 위한 탐색 공간이며, 상태공간트리는 탐색 공간을 트리 형태의 구조로 암묵적으로 해석한 것이다. 암묵적으로 해석한 것이기 때문에 일반적인 배열을 트리라고 생각하고 접근하면 된다. -
깊이 우선 탐색(DFS)
깊이 우선 탐색은 이름 그대로 그래프의 최대 깊이까지 탐색 한 후 이전 분기점으로 돌아가 탐색을 이어가는 탐색 방법이다. 너비 우선 탐색(Breadth First Search)은 이와 반대로 시작 정점과 인접한 모든 정점을 우선 방문하는 탐색 방법이다.
백트래킹 구현
void backtracking(int index){
if(index==n){ # 탈출 조건
return;
}
if(isPromising()){
visited[index] = true; # 상태변화
backtracking(index+1); # 재귀호출
visited[index] = false; # 상태복구
}
}
bool isPromising(int index){ # 유망함수
if(non-promising)
return false;
if(promising)
return true;
}완전 탐색 관련 백준 문제 Github 링크
백준 완전탐색 관련 문제
