완전 탐색, 백트래킹
·
Develop/Algorithm
완전 탐색 (brute force, exhausitive key search)완전 탐색은 모든 경우의 수를 탐색하는 알고리즘입니다. (즉, 노가다)경우의 수란? 순열 또는 조합을 의미합니다.그래서 완전 탐색은 보통 조합/순열 + 로직(DFS/BFS) 로 이루어져 있습니다. 그럼 언제, 완전탐색을 사용해도 될까요? 아주 명확하고 간단하게 정리하면 다음과 같습니다.시간복잡도가 1억 미만일 때! 즉, 대략 총 계산 횟수가 1억 미만이면 완전탐색으로 풀면 됩니다. (대부분 시간 제한이 1초이므로)그러나 1억 이상인 경우에는? 다른 방법이 떠오르지 않으면 완전 탐색을 사용하긴 하되, 의심하긴 해야합니다. 완전탐색의 구현 방법 2가지 (반복문 vs 재귀함수)만약 2가지 방법 모두로 풀 수 있다면, 무조건 반복..