[Algorithm] Brute Force 브루트 포스

알고리즘이라고 하기도 뭐 합니다.

암호학에서는 전수조사 (Exhaustive Key Search) 라고도 부르며, 무차별대입(공격) 이라도 부릅니다.

 

---

 

Brute Force 브루트 포스

수학적으로 계산 노가다하는 행위를 학술적으로 부르는 개념이라고 합니다.

시간과 자원이 정말정말 풍부하다면, (비효율적이기도 하지만! 이라고 역접을 써서 설명할 수 있겠네용 ㅎㅎ)

이론적으로 가능한 모든 수를 대입하므로 정확도 100%를 보장합니다.

 

1번 컴퓨터는 000~099 까지, 2번 컴퓨터는 100~199 까지... 이런식으로 병렬식으로 처리할 시 무서워질 수도 있습니다.

(밑에는 암달의 법칙 (Law) 에 대한 설명으로, 병렬화에 대한 설명과 연관지어 떠올리실 수 있어용)

https://ko.wikipedia.org/wiki/%EC%95%94%EB%8B%AC%EC%9D%98_%EB%B2%95%EC%B9%99

암달의 법칙 - 위키백과, 우리 모두의 백과사전

 

모든 조합을 확인하는 단순 숫자 비밀번호 조합 찾기 등에서 유용하지만,

미로 탈출은 DFS/BFS 가 더 효율이 좋고, Sorted 된 데이터에선 이진탐색이 더 좋겠습니다.

 

코드 예시

어떠한 두 수를 더했을 때, target 값과 같은 값이 나오는 조합이 무엇인지 찾는 코드입니다.

int[] nums = { 1, 2, 3, 4, 5 };
int target = 6;

for (int i = 0; i < nums.Length; i++) {
    for (int j = i + 1; j < nums.Length; j++) {
        if (nums[i] + nums[j] == target) {
            Console.WriteLine($"target sum of {nums[i]} and {nums[j]} is {target}");
        }
    }
}

 

이중 for 문으로 시간복잡도는 O(n^2) 입니다. (HashSet 을 사용하면 O(n) 에 가능할 지도?)

 

위 처럼 데이터 크기가 작으면 큰 문제 없겠지만, 경우의 수가 많아지면 그만큼 시간이 지수함수적으로 늘어날 것입니다.

그래서 효율을 위해 대부분 수학적 알고리즘이 다양하게 존재하는 듯 합니다.

 

---

 

이번 포스트는 그냥 '무지성 반복문으로 순회하는 코드를 뭐라고 부를까?' 라는 궁금점에 작성하게 되었어요.

저도 평소에 무지성 반복문 코드를 많이 사용해 왔는데, 좀 더 머리를 굴러보며 고민하는 시간을 더 가져야 겠군용.

그럼 오늘도 좋은 하루 되세요~ ϵ(っꈍᗜꈍς)϶