브루트 포스 알고리즘 (brute force), 백트래킹 (Backtracing) 알고리즘

브루트 포스 알고리즘 (brute force)

완전탐색 알고리즘
가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과를 가져오는 알고리즘

https://steemit.com/kr-dev/@gyeryak/easyalgo-2-bruteforce

- 구현이 쉬운 편
- 시간적으로 매우 비효율적
- 알고리즘은 항상 최적해를 구할 수 있음

활용

- 선형구조: 순차탐색
- 비선형구조: 백트래킹(backTracking), 맹목적 탐색(BFS, DFS)

 

백트래킹 (Backtracing) 알고리즘

되추적이라는 뜻으로 이전 단계로 거슬러 올라가 다른 가능성을 찾아보는 방법
모든 가능성을 찾아보는 것은 맞지만 그중에서도 가능성이 있는 것만 찾는 가지치기(Pruning) 기법을 사용

*가지치기 : 조건을 맞출 수 없는 경우, 해당 경우를 제외 시키는 방법

브루트포스, 백트래킹, DFS 차이

브루트 포스 알고리즘 = 모든 가능한 경우를 전부 해보는 방식의 알고리즘
백트래킹 = 탐색을 진행하고 조건에 맞지 않는 부분을 제외하면서 진행하는 방식의 알고리즘
DFS = 트리를 완전 탐색하는 한가지 방법