완전 탐색 알고리즘(Brutal-Force Algorithm)

완전 탐색 알고리즘(Brutal-Force Algorithm)

 무차별적으로 대입하는 방법을 나타내는 알고리즘이다. 즉 모든 가능성을 시도하여 문제를 해결한다. 따라서 데이터 크기가 커질수록 비효율적이다.

 

완전 탐색 알고리즘을 사용하는 경우

• 프로세스 속도를 높이는 데 사용할 수 있는 다른 알고리즘이 없을 때
• 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때

완전 탐색 알고리즘의 한계

 문제의 복잡도에 매우 민감하다. 문제가 복잡해질수록 기하급수적으로 많은 자원(시간, 컴퓨팅 자원)을 필요로 하게 된다.

 

완전 탐색 알고리즘을 활용하는 알고리즘

• 순차 검색 알고리즘(Sequential Search)
• 문열 매칭 알고리즘(Brutal-Force String Matching)
• 선택 정렬 알고리즘
• 버블 정렬 알고리즘
• 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)
• 동적 프로그래밍 - DP(Dynamic Programming)