알고리즘 개념
완전탐색이란?
- 모든 경우의 수를 전부 찾아서 답을 찾는 알고리즘.
- 가능한 모든 경우의 수를 다 해보기 때문에 문제를 풀 때 가장 강력하고 확실한 방법.
- 하지만, 그만큼 시간이 가장 오래 걸리는 탐색 기법.
자원만 충족해준다면 항상 100% 정확도가 보장되기 때문에 가장 확실한 방법이라고 불린다.
예) 0000 ~ 9999로 이루어진 임의의 비밀번호를 찾고 싶을 때, 가능한 모든 비밀번호의 수를 대입해보는 것이다.
→ 모든 조합 = 10^4 = 1초 안에 가능
완전탐색 기법의 종류
- Brute Force: for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법
- 비트 마스크: 이진수 표현을 자료구조로 쓰는 기법(AND, OR, XOR, SHIFT, NOT)
- 재귀 함수
- 순열: 서로 다른 n개의 원소에서 r개의 중복을 허용하지 않고 순서대로 늘어놓은 수
- BFS(너비우선탐색), DFS(깊이우선탐색)
- Backtracking
Backtracking이란?
DFS에 "가지치기"를 통해 가도 되지 않는 비효율적인 경로를 차단하고 효율적으로 탐색하는 완전탐색 기법.
DFS는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 이용해서 계속 이동하며 모든 곳을 방문한다.
하지만, 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할 수도 있다.
그렇다면 갈 필요없는 곳은 가지 않는 것이 더 효율적이므로 "가지치기"를 통해 잘라낸다.
