알고리즘 - 완전 탐색 기법(1) (Brute - Force)

 

완전 탐색 기법 이란?

 

 

 

• 완전 탐색 기법은 가능한 경우의 수를 전부 나열하여 해답을 찾는 방식이다.

 

• 직관적이고 구현이 간단하다는 점이 장점이지만 계산해야 할 배열의 요소나 원소의 수가 조금만 증가해도 시간복잡도가 기하급수적으로 증가한다. 

 

---

 

 

완전 탐색 알고리즘의 종류

 

 

1) 단순 Brute - Force

 

 

• 반복문과 조건문의 반복으로 결과값을 찾는 단순한 방식.

 

• 배열의 요소를 고려하지 않고 반복문을 반복하기에 시간복잡도가 상당히 비효율적일 확률이 높음.

 

 

 

2) 백트래킹 (Backtracking)

 

• 현재의 상태에서 가능한 모든 해를 탐색하면서 조건에 맞지 않으면 탐색을 조기에 중단하여 불필요한 탐색을 줄이는 형태의 알고리즘이다.

 

• 함수를 재귀적으로 호출하고 이 절차를 반복하는 특징이 있다.  

 

• 분할 정복*을 이용한 기법이다.

 

분할 정복 이란?

• 분할 : 해결할 문제를 여러 개의 작은 부분으로 나눈다.
• 정복 : 나눈 작은 문제를 각각 해결한다.

 

 

 

C# 예제

 

 

 static void Main(string[] args)
 {
     int[] arr = { 1, 2, 3, 4 };
     List<int> current = new List<int>();
     FindSubsets(arr, 0, current);
 }

 

public void FindSubsets(int[] arr, int index, List<int> current)
{
    // 현재 부분집합 출력
    Console.WriteLine(string.Join(" ", current));

    // 배열의 끝까지 탐색한 경우
    if (index == arr.Length)
    {
        return;
    }

    for (int i = index; i < arr.Length; i++)
    {
        // 현재 원소를 부분집합에 추가
        current.Add(arr[i]);
        // 다음 원소를 포함하는 부분집합 탐색
        FindSubsets(arr, i + 1, current);
        // 백트래킹: 현재 원소를 부분집합에서 제거
        current.RemoveAt(current.Count - 1);
    }
}

 

 

 

 

예제 설명

 

 

• 배열의 부분집합을 찾는 코드이며 FindSubsets를 재귀적으로 반복 호출한다.
• index 가 배열의 길이 만큼 탐색, 즉 끝까지 탐색하면 종료한다.

 

• for문은 현재 index부터 배열의 끝까지 원소를 검사한다.
• current.Add로 현재의 원소 arr[i] 를 부분집합 리스트에 추가한다.
• FindSubsets 를 i + 1, 즉 다음 원소를 포함하는 부분집합을 탐색하도록 호출한다.
• 재귀 호출이 끝나면 current 부분 집합 리스트에서 현재의 원소를 제거해서 다음 원소를 탐색하게 한다.(백트래킹) 

 

 

 

 

 

 

3) 순열 (Permutation)

 

 

 

• 임의의 수열이 주어졌을때 이 주어진 요소들을 모든 가능한 순서로 배열하는 방법이다.

 

• 배열 [1, 2, 3]의 순열은 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] 을 나타낸다.

 

 

 

C# 예제

 

 

 

static void Permute(int[] nums, int start, int end, List<List<int>> result)
{
    // start와 end가 같으면 한 개의 순열이 완성된 것
    if (start == end)
    {
        // 현재 배열 상태를 결과 리스트에 추가
        result.Add(new List<int>(nums));
    }
    else
    {
        // start부터 end까지 각 요소를 현재 위치(start)와 교환
        for (int i = start; i <= end; i++)
        {
            // 요소 교환
            Swap(ref nums[start], ref nums[i]);
            // 다음 위치에 대해 재귀 호출
            Permute(nums, start + 1, end, result);
            // 이전 상태로 되돌리기 위해 다시 교환 (백트래킹)
            Swap(ref nums[start], ref nums[i]);
        }
    }
}

static void Swap(ref int a, ref int b)
{
    int temp = a;
    a = b;
    b = temp;
}

 

 

 

 

예제 설명

 

 

 

• Permute는 Start와 End가 같으면 완성된 순열이니 이때 결과를 리스트에 추가한다.
• 각 요소의 위치를 Start부터 End까지 교환하며 다음 위치에 대해 또 다시 재귀호출한다.
• 재귀 호출 후에는 다시 원래 상태로 되돌리기 위해 교환을 수행한다.

 

 

 

4) 조합 (Combination)

 

 

• 주어진 집합에서 순서에 상관없이 일부 요소를 선택함. (서로 다른 n개의 원소중에 r개를 고름)

 

• 예를 들어, {1, 2, 3}에서 2개의 요소를 선택하는 조합은 {1, 2}, {1, 3}, {2, 3}임.

 

static void Main(string[] args)
{
    int[] arr = { 1, 2, 3, 4 };
    int length = 3;
    List<int> combinationList = new List<int>();

    Combinations(arr, length, 0, combinationList);
}

 

  public void Combinations(int[] arr, int length, int startIndex, List<int> combinationList)
  {
      if (combinationList.Count == length)
      {
          Console.WriteLine(string.Join(", ", combinationList));
          return;
      }

      for (int i = startIndex; i < arr.Length; i++)
      {
          combinationList.Add(arr[i]);
          Combinations(arr, length, i + 1, combinationList);
          combinationList.RemoveAt(combinationList.Count - 1);
      }
  }

 

 

 

 

예제 설명

 

• if (combinationList.Count == length) 현재 조합의 길이가 목표 길이와 동일한지 확인한다.
• startIndex 부터 배열 끝까지 숫자 조합을 위한 for문을 반복함.
• 리스트에 원소를 추가 한 뒤 다음 원소를 추가 하기 위한 재귀 호출.
• 마지막에 추가한 원소를 제거함 (다음 for문 준비)

 

 

 

사진 출처 : https://www.scholarhat.com/tutorial/datastructures/brute-force-algorithm-in-data-structures

Brute Force Algorithm in Data Structures: Types, Advantages, Disadvantages

https://www.geeksforgeeks.org/

GeeksforGeeks | A computer science portal for geeks