[알고리즘] 완전 탐색, 브루트 포스 정의 | 종류 | 장단점 | 예시 (feat. Node.js Brute-Force-Search)

차근차근 인공지능, 인프준

 

 

 

 

 

 

 

 

 

 

들어가며

알고리즘은 어떤 문제를 해결하기 위한 동작들의 절차입니다. 공간 복잡도와 시간복잡도를 고려해서 무조건 가장 빠르고 효율적인 알고리즘을 사용하면 되지 않을까라는 생각을 할 수 있겠지만 해결하는 문제에 따라서 효율적인 알고리즘이 달라집니다.

 

그렇기 때문에 알고리즘의 성능과 평가 방법에 대해서 아는 것이 중요하지만 다양한 알고리즘 종류들에 대해서도 알고 있어야 해결하고자 하는 문제를 적절한 방법으로 처리할 수 있게 됩니다. 오늘은 알고리즘의 필수 개념 중 한 가지인 완전 탐색 알고리즘, 브루트 포스 서치에 대해서 알아보려 합니다.

 

 

 

 

 

빅오 표기법:Big-O Notation 정의/특징/복잡도/종류/비교/예제

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

 

완전 탐색, Brute Force Search 란?

완전 탐색과 브루트 포스의 이름에서 유추할 수 있듯이 이 알고리즘의 방법은 발생 가능한 모든 경우의 수를 전부 탐색하면서 조건에 맞는 답을 찾아내는 방법입니다. 이 알고리즘의 대표적인 장점은 모두 확인하기 때문에 100%의 확률로 정답만을 출력한다는 것입니다. 하지만 확실하게 확인하는 만큼 시간이 오래 걸리는 탐색기법입니다.

 

💡 Brute: 무식한, 짐승 같은 + Force: 힘 - 무식하게 풀기

 

 

 

 

---

 

 

 

 

완전 탐색의 종류

구조로 나누어보면 선형 구조를 전체적으로 탐색하는 방법인 순차 탐색과 비선형 구조를 전체적으로 탐색하는 방법인 DFS / BFS가 대표적인 탐색 방법입니다.

 

1. 브루트 포스, Brute Force

브루트 포스는 반복문과 조건문을 사용하여 가능한 모든 방법을 단순하게 찾는 기법을 말합니다.

 

예를 들어 3자리로 구성된 자물쇠를 풀어야 한다면 000부터 999까지 모든 경우의 수를 입력하는 기법이라고 생각하면 이해하기 쉽습니다. 확실하게 정답을 찾을 수 있지만 정말 단순하고 무식한 방법이기에 시간이 오래 걸리게 됩니다.

 

 

2. 비트 마스크, Bit Mask

비트 마스크는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하는 방식입니다. 이진수를 활용하기 때문에 문제에서 확인해야 하는 경우가 A 또는 B와 같이 두 가지 선택으로 구성되는 경우를 확인하기에 유용한 방법입니다. 

 

 

3. 백트래킹, Backtracking

백트래킹은 답을 찾는 과정에서 이 경로가 답이 아니라고 판단되면 버리고 다른 경로를 탐색하는 방법입니다. 이 방법을 가지치기(Pruning)라고 표현하는데 불필요한 가지를 처내면서 답을 찾아내서 붙은 이름입니다.

 

보통 반복문의 횟수를 줄일 수 있어 효율적이지만 최악의 경우에는 여전히 완전 탐색을 하기 때문에 경로를 찾아 가지치는 방법이 효율성을 결정하게 됩니다.

 

 

4. 순열, Permutation

순열은 완전 탐색의 대표적인 유형으로 서로 다른 n개의 원소에서 r개를 중복 없이 골라 순서대로 나열하는 것(정렬이 되어있음)입니다. 자세한 설명과 비슷한 개념, 예시코드를 작성했던 이전 포스팅을 아래 첨부하겠습니다.

 

 

[Python] 누적합 / 순열 / 조합 (feat.itertools module)

 

 

5. 재귀 함수, Recursion Function

재귀 함수는 자기 자신을 답을 찾을 때까지  반복적으로 참조하는 함수를 의미합니다. 직관적이고 간단하다는 장점이 있지만 자기 자신을 반복적으로 호출하는 과정에서 종료조건이 포함되거나 만족하지 못하면 무한루프에 빠질 수 있다는 위험성이 있으므로 종료조건을 고려해서 작성해야 합니다.

 

 

6. 깊이우선탐색, DFS / 너비우선탐색, BFS

먼저 깊이 우선 탐색( DFS, Depth-First Search )은 최대한 깊게 내려간 뒤, 더 이상 내려갈 곳이 없을 경우 옆으로 이동하는 방식입니다. 스택 또는 재귀함수로 구현합니다.

 

다음으로 너비 우선 탐색 ( BFS, Breadth-First Search )은 최대한 넓게 이동한 다음, 더 이상 이동할 곳이 없을 때 아래로 이동하는 방식입니다. 큐를 이용해서 구현합니다.

 

두 방식 모두 그래프를 탐색하는 방법이며 모든 노드를 검색하기 때문에 시간 복잡도는 동일합니다. DFS와 BFS는 코딩 테스트에서 높은 빈도로 나오기 때문에 자세한 설명과 비교 그리고 예시에 대해서 따로 포스팅을 작성해보려 합니다.

 

 

 

 

---

 

 

 

 

완전 탐색의 장단점

장점

• 알고리즘을 구현하는 것이 상대적으로 쉽습니다.
• 복잡한 알고리즘 없이 빠르게 구현이 가능합니다.

 

단점

• 알고리즘의 실행 시간이 상대적으로 오래 걸립니다.
• 모든 경우의 수를 탐색하기에 메모리를 비효율적 사용합니다.

 

 

 

 

---

 

 

 

 

완전 탐색 예시

첫 번째로 1부터 1억까지의 합을 완전 탐색으로 구한다면 반복문으로 1부터 1억까지 돌면서 값을 누적하여 답을 찾아내게 됩니다. 등차수열의 합 공식을 사용하게 되면 쉽게 해결할 수 있는 문제이기에 이것을 완전 탐색으로 답을 찾는다면 공간적, 시간적으로 비효율적인 방법으로 구하게 됩니다.

 

 두 번째로 위에서 간단히 예시를 들었던 자물쇠의 경우입니다. 만약 7자리의 비밀번호 자물쇠가 있다면 완전 탐색으로 비밀번호를 구하기 위해서는 0000000부터 9999999까지 하나씩 확인하며 결과를 찾게 됩니다. 분명 언젠가 정답을 찾아내겠지만 최악의 경우 엄청난 시간을 필요로 하게 됩니다.

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

 

 

 

Reference

은연일체님의 블로그, Yesjjin99님의 블로그