완전 탐색 ( Exhaustive Search )

❓ 완전 탐색이란?

 

완전 탐색은 가능한 모든 해결 방법을 체계적으로 탐색하여 문제를 해결하기 위한 일반적인 접근 방식 또는 기술이라고 말할 수 있습니다.

완전 탐색이라는 특정 알고리즘이 따로 존재하는 것은 아니고, 이 접근 방식을 가지는 여러 종류의 알고리즘들의 큰 분류라고 할 수 있습니다.

 

---

👾 종류

 

브루트 포스 ( Brute Force )

최적의 해결 방법을 찾기 위해서 가능한 모든 해결 방법을 확인하는 단순하고 직접적인 방식입니다.

단순히 조건문과 반복문을 이용할 수 있고, 좀 더 체계적으로는 순열과 조합의 접근 방식도 있습니다.

 

---

재귀 ( Recursion )

재귀는 특정 조건이 충족될 때까지 함수가 반복적으로 자신을 호출하는 프로그래밍 기술입니다.

 

재귀 함수에서 함수는 일단 충족되면 재귀 호출을 중지하고 값을 반환하는 조건인 기본 사례를 먼저 확인합니다.

기본 사례가 충족되지 않으면 함수는 일반적으로 문제의 크기를 줄이거나 더 작은 하위 문제로 세분화하여 수정된 입력으로 자체 호출합니다.

 

재귀는 동일한 유형의 더 작은 하위 문제로 나눌 수 있는 문제를 해결하는 데 유용합니다.

재귀를 사용하여 해결할 수 있는 문제의 예로는 트리 데이터 구조 순회, 퀵 정렬과 같은 정렬 알고리즘, 숫자의 계승 계산 등이 있습니다.

 

---

DFS( Depth-First Search, 깊이 우선 검색 ) / BFS( Breadth-First Search, 넓이 우선 검색 )

DFS는 주어진 노드에서 시작하여 각 분기를 따라 가능한 한 멀리 탐색한 후 역추적하는 그래프 탐색 알고리즘입니다.

DFS에서는 스택을 사용해서 방문했지만 아직 탐색하지 않은 노드를 추적하고, 모든 노드를 방문할 때까지 알고리즘을 계속 진행합니다.

 

BFS는 주어진 노드에서 시작하여 다음 단계의 노드로 이동하기 전에 인접한 모든 노드를 탐색하는 그래프 탐색 알고리즘입니다.

BFS에서는 큐를 사용하여 방문했지만 아직 탐색하지 않은 노드를 추적하고, 모든 노드를 방문할 때까지 알고리즘을 계속 진행합니다.

 

DFS와 BFS의 주요 차이점은 그래프에서 노드를 탐색하는 순서입니다.

DFS는 각 브랜치를 깊숙이 탐색하여 그래프를 탐색하는 반면, BFS는 다음 레벨로 이동하기 전에 주어진 레벨의 모든 노드를 탐색하여 그래프를 탐색합니다.

 

---

비트마스크 ( Bitmask )

비트마스크 알고리즘은 요소 집합의 가능한 모든 조합을 효율적으로 반복하기 위해 컴퓨터 프로그래밍에 사용되는 기술입니다.

하위 집합, 순열 또는 조합과 관련된 문제를 처리할 때 특히 유용합니다.

 

비트마스크 알고리즘의 기본 아이디어는 집합의 각 요소를 이진수의 비트로 나타내는 것입니다.

ex) {A, B, C} 길이가 3인 이진수를 사용하여 이 세트의 각 부분 집합을 나타낼 수 있습니다.

여기서 각 비트는 부분 집합에 있는 요소의 존재 또는 부재를 나타냅니다. → 부분 집합 {A, C}는 이진수 101로 나타낼 수 있습니다.

 

비트마스크 알고리즘을 사용하여 집합의 가능한 모든 하위 집합을 반복하려면 길이가 n인 모든 이진수를 반복하면 됩니다.

여기서 n은 집합의 크기이며 어떤 비트가 1로 설정되어 있는지 확인합니다. 각 이진수에 대해 다음을 수행합니다. 그런 다음 세트 비트에 해당하는 요소만 포함하여 세트의 해당 서브세트를 생성할 수 있습니다.

 

비트마스크 알고리즘은 필요한 모든 하위 집합 또는 집합 조합을 반복해야 하는 문제를 처리할 때 특히 유용합니다.

그렇지 않으면 필요한 중첩 루프 및 조건문의 수를 크게 줄일 수 있기 때문입니다.