[Algorithm] 완전탐색(Exhaustive Search)에 대해 쉽게 알아보자

💡 완전탐색

알고리즘 문제를 해결하는 데 가장 간단하고 쉬운 방법이 무엇일까? 답은 가능한 경우를 다 해보는 것이다. 이게 무슨 알고리즘이야? 할 수 있겠지만, 이것도 알고리즘에 일종이다. 전산학에서는 이를 무식하게 푼다라는 뜻의 Brute-force라 하고, 전체를 확인한다고 해서 완전 탐색 알고리즘(exhaustive search algorithm)이라고 한다. 

** ☝🏻 그렇다면 완전탐색은 대체 언제 쓰이는건가요?

사실, 알고리즘 대부분의 문제들은 시간 초과등의 이유로 완전 탐색으로 풀리지 않습니다. 하지만 어려운 알고리즘을 생각할 필요 없이 완전 탐색으로 풀리는 문제도 있으며, 가끔 어려운 완전 탐색 문제도 존재합니다. 따라서, 완전 탐색 알고리즘을 문제 풀이 도구로 항상 염두해두고 있어야합니다.

💡 완전탐색의 종류

완전탐색의 종류에는 그 쓰임새에 따라 단순 중첩 for문, 재귀, DFS/BFS, 백트래킹 등이 존재한다.