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

모든 값을 대입하는 방법

 

컴퓨터 과학에서 Brute Force는 시행착오 방법론을 말한다

암호학에서는 Brute Force Attack이라고 한다

이는 특정한 암호를 풀기 위해서 모든 값을 대입하는 방법을 말한다

 

쉽게 말해, 암호를 모르는 0-9 사이의 4자리 숫자로 된 자물쇠가 있다고 했을 때, 이 자물쇠의 비밀번호를 풀기 위해서 0000부터 9999까지의 모든 경우의 수를 대입하여 푸는 방법이다

 

Brute Force Algorithm의 의미

무차별 대입 방법을 나타내는 알고리즘

순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도

공간 복잡도와 시간 복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법

 

Brute Force Algorithm이 사용될 때

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

데이터 범위가 커질수록 비효율적이다

프로젝트의 규모가 커진다면 더 효율적인 알고리즘을 사용하자

 

어디서 사용할까?

• 순차 검색 알고리즘 (Sequential Search) : 배열 안에 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색
• 문자열 매칭 알고리즘 (Brute-Force String Matching) : 길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색
• 선택 정렬 알고리즘 (Selection Sort) : 전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 오름차순 또는 내림차순에 따라 교환하는 정렬 알고리즘
• 등