[CS기초] 완전 탐색(Brute Force)

완전 탐색 (Brute Force) 개요

완전 탐색은 가능한 모든 경우의 수를 탐색하여 정답을 찾아내는 알고리즘인데요. 직관적이고 단순하지만, 경우의 수가 많아지면 시간 효율이 나빠질 수 있습니다.

 

완전 탐색의 종류

단순 브루트 포스 (Brute Force)

• 가능한 모든 방법을 단순하게 시도하는 기법
• 반복문과 조건문을 활용해 모든 경우를 하나씩 검사
• ex) 비밀번호를 0000~9999까지 하나씩 대입하여 찾는 방식

백트래킹 (Backtracking)

• 되돌아가면서 모든 경로를 탐색하는 기법.
• 탐색 중 해당 경로가 조건에 맞지 않으면 탐색을 중단하고 되돌아가 다른 경로를 탐색한다.
• 불필요한 탐색을 줄이기 때문에 단순 브루트 포스보다 효율적
• ex) N-Queen 문제, 미로 찾기

순열 (Permutation)

• 서로 다른 n개의 원소에서 r개를 순서를 고려하여 나열하는 기법
• 모든 가능한 순서를 탐색해야 할 때 사용됨
• ex) 여행 경로 문제(TSP), 암호 해독

깊이 우선 탐색(DFS) / 너비 우선 탐색(BFS)

• DFS (Depth-First Search) : 한 방향으로 탐색을 쭉 진행하다가 막히면 되돌아가 다른 방향을 탐색하는 기법
• BFS (Breadth-First Search) : 시작점에서 가까운 노드부터 차례대로 탐색하는 기법
• 그래프 탐색에서 모든 노드를 탐색해야할 때 자주 사용됨
• ex) 최단 경로 찾기, 그래프 연결 요소 탐색