Algorithm | Brute Force & Backtracking

Brute Force

 브루트 포스(Brute Force)는 완전 탐색이라고도 불리는 알고리즘이다. 말 그대로 모든 경우의 수를 전부 체크해보는 알고리즘이다. 탐색 알고리즘 풀이 시 가장 간단하게 사용할 수 있으나 시간이 최대로 발생하게 된다. 

 

 보통 for문 / if문을 활용하는 방법과 재귀 함수를 이용하는 방법이 있다. 

Backtracking

 백트래킹(Backtracking)은 깊이우선 탐색(DFS)를 기반으로 하는 일종의 트리 탐색 알고리즘이다.

Algorithm | DFS & BFS

 백트래킹은 어떤 노드의 유망성을 점검하고 유망하지 않으면 그 노드의 부모 노드로 돌아간 후 다른 자손의 노드를 탐색한다. 즉, 스택에 자식 노드를 넣기 전에 유망한지 확인하고 스택에 추가한다. 유망성 점검을 통해 가지치기가 일어나게 되어 원시적으로 모든 경우의 수를 확인하는 알고리즘은 아니다.

 

 가지치기를 통해 불필요한 DFS 호출을 줄여 시간을 단축시킬 수 있다.

---

Reference

 

· [알고리즘] 백트래킹 - https://heekim0719.tistory.com/284