[Python] 완전탐색 알고리즘

1. 완전탐색 알고리즘이란?

완전탐색은 가능한 모든 경우의 수를 확인하여 정답을 찾는 방법이다.

이 방법은 무식한게 한다는 의미로 'Brute Force'라고도 부르며, 직관적이여서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하고 기초적인 방법이다. 

 

Computer Science에서 문제 해결 알고리즘을 사용할 때는 기본적으로 2가지 규칙을 적용한다.

 

1. 사용된 알고리즘이 적절한가? (문제를 해결할 수 있는가?)

2. 효율적으로 작동하는가?

 

위 2가지 규칙에 대해서 생각할 때, 1번을 만족하는 확실한 방법이나 대부분의 경우 2번 때문에 이 방법이 사용되는데에 제한이 따른다. 따라서 완전탐색 기법을 사용할 때에는 그 문제에 대한 파악이 중요하다.

 

2. 완전탐색 기법을 활용하는 방법

완전탐색 기법으로 문제를 풀기 위해서는 다음을 고려하여 수행한다.

 

1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다.

2. 가능한 모은 방법을 다 고려한다.

3. 실제 답을 구할 수 있는지 적용한다.

 

여기서 2의 모든 방법에는 다음과 같은 방법들이 있다.

 

1. Brute Force 기법 : 반복/조건문을 활용하여 모두 테스트하는 방법

2. 순열(Permutation) : n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법

3. 재귀 호출

4. BFS, DFS를 활용하는 방법

 

3. 각 방식에 대한 설명

1. Brute Force 기법

반복/조건문을 통해 가능한 모든 방법을 단순히 찾는 경우를 의미한다. 

예를 들어, 위의 자물쇠 암호를 찾는 경우와 같이 0000-9999 모든 경우를 참조하는 경우이다.

 

2. 순열 (Permutation)

순열 : 임의의 수열이 있을 때, 그것을 다른 순서로 연산하는 방법

순서가 중요하다. 만약, 수열에서 숫자 [1, 2, 3]이 있다면, 이것을 순서 [1, 2, 3]과 순서 [2, 1, 3] 등과의 차이가 중요하다.

같은 데이터가 있는 순열이지만, 그 순서에 따라 의미가 있고 순서를 통해 연결되는 이전/다음 수열을 찾아낼 수 있는 경우를 계산할 수 있다.

 

만약 N개의 서로 다른 데이터가 있고 이를 순열로 나타낸다면 전체 순열의 가지수는 N!개가 된다.

최초에 N개 중, 1개가 올 수 있고 그 이후에는 N-1개, N-2개,....,1 개가 올 수 있으며 이를 모두 곱하면 N!이기 때문이다.

 

예를 들어 [1, 2, 3]을 사전 순으로 나열하는 순열이 있다고 가정했을 때 아래와 같이 나열할 수 있다.

 

[1 2 3]  # 최초 순열 _ 오름차순
[1 3 2]
[2 1 3]
[2 3 1]
[3 1 2]
[3 2 1]  # 최종 순열 _ 내림차순

 

최초/최종 순열을 보면 숫자가 오름/내림차순인 것을 확인할 수 있다. 

여기서 사전 순으로 순열의 규칙을 알아낼 수 있는데 N개의 데이터가 있고 1 ~ i 번째 데이터를 설정했을 때, i 번째 데이터 기준으로 최종 순열은 i + 1 부터 N까지가 모두 내림차순이라는 것이다. (최초 순열이면 i + 1 부터 N이 오름차순)

 

예를 들어 [1, 3, 2]를 보면, [3, 2]가 내림차순이기 때문에 이는 0번째 숫자가 1일 때의 최종순열이다.

그렇다면 이 다음 순열은 어떻게 구할 수 있을까?

 

i 번째가 고정이었고 i + 1부터 내림차순인 경우가 최종순열이므로 다음은 i 번째 부터 모두 오름차순이 되는 최초순열이 된다.

즉, i - 1까지는 변동이 없고 i는 i + 1 ~ N까지의 숫자 중 자신보다 크지만 가장 작은 숫자와 교환이 되며 i + 1 ~ N은 다시 오름차순이 되어야 한다.

그래서 [1, 3, 2] 다음의 순열은 [2, 1, 3]이다. ([1, 3, 2]에서 1은 2로 교체, [1, 3]은 오름차순으로 정렬)

 

이러한 규칙을 통해 이전/다음 순열을 구하거나 모든 순열을 완전탐색으로 구하는 로직을 구현할 수 있게 된다.

 

※ 순열 구하는 방법

순열을 구성하는 배열을 A라고 하고 i, j는 그 배열의 Index 값을 의미한다고 하자.

예를 들어 A = [7, 2, 3, 6, 5, 4, 1] 이고 i, j는 각각의 index 값이다. 

아래에서는 현재의 다음 순열을 구하는 로직을 기반으로 설명한다.


1. A[i - 1] <= A[i]를 만족하는 i 중, 가장 큰 값을 찾는다. (뒤에서부터 찾는 경우 A[i - 1] >= A[i] 중 가장 작은 i를 찾는다.)

    → 현재 i값을 기준으로 이후 값들이 모두 내림차순으로 되는 경우를 찾는다. (현재 기준 최종 순열을 찾음)

    → A 배열을 보면 A[i - 1] < A[i]가 되는 가장 큰 값은 6 (3번째)이다. 즉, i = 3이다.



2. j >= i 중, A[j] > A[i - 1] 을 만족하는 가장 큰 j의 값을 찾는다.

    → 현재 i = 3 기준으로 최종 순열이므로 i - 1 번째 숫자를 변경하여 최초순열을 찾아야한다.

    → A 배열을 기준으로 i - 1 번째 숫자는 3으로, 3보다 큰 경우는 6, 5, 4이고 그 중 j 값이 가장 큰 경우는 값 4이다.


3. A[i - 1]과 A[j]를 교체한다.

    → i - 1인 2번째 숫자 3과 j인 5번째 숫자 4를 변경한다. A = [7, 2, 4, 6, 5, 3, 1]이 된다.


4. i 이후의 순열을 모두 뒤집는다.

    → 최초 순열 상태로 만들어야하므로 i 번째부터는 오름차순으로 만들어야한다. A = [7, 2, 4, 1, 3, 5, 6]이 된다.

 

전체 N개의 숫자에 대해 각각 순열을 구하는 문제가 되므로 위 로직의 시간복잡도는 O(N!)이다.

제일 좌측에 숫자 N개가 올 수 있고 각 (N-1)!개의 순열이 있기 때문에 시간복잡도는 O(N * (N-1)!)이라서 O(N!)이 된다.

따라서 이 방법을 사용할 때에는 문제에서 주어진 N의 크기를 고려해야 한다.

 

# 순열 함수 사용하기

from itertools import permutations

# permutations(iterable, r)
# iterable의 원소들을 이용해 길이가 r인 순열 생성
# 리턴 값은 순열 튜플의 이터레이터이다.

data = 'ABCD'
result = permutation(data, 2)

for r in result:
   print(r)

 

# 조합 함수 사용하기

from itertools import combinations

# combinations(iterable, r)
# iterable의 원소들을 이용해 길이가 r인 조합을 생성한다.
# 리턴값은 조합 튜플의 이터레이터이다.

data = 'ABCD'
result = combination(data, 2)

for r in result:
   print(r)

 

3. 재귀

재귀는 말 그대로 자기 자신을 호출한다는 의미이다.

예를 들어, 총 4개의 숫자 중에서 2개를 선택하는 경우를 모두 출력한다고 가정해보자.

1 ~ 4까지 숫자가 있고 2개를 중복 없이 선택하는 모든 경우의 수를 출력한다고 할 때, 이를 반복문으로 표현한다면 다음과 같을 것이다.

 

for i in range(1, 5):
  for j in range(1+i, 5):
    print(i, j)

 

2중 반복문으로 해결하였지만 숫자 N개 중 M개를 고르는 경우라고 할 때, N과 M이 매우 큰 숫자라면 반복문을 사용하기에 한계가 있다.

 

이를 재귀함수를 활용한다면 자기 자신을 호출함으로써 다음 숫자를 선택할 수 있도록 이동시켜 전체 코드를 짧게 줄일 수 있다.

 

# 순열
def permutation(arr, r):
   
   # 순열을 저장할 배열
   result = []
   
   # 실제 순열을 구하는 함수
   def function(p,index):
      # n개의 숫자를 다 선택했다면 출력 후 더 이상 재귀를 돌지 않음
      # 탈출 조건 정의
      if len(p) == r:
         result.append(p)
         return
      
      for idx, data in enumerate(arr):
         if idx not in index:
            function(p+[data], index+[idx])
      
   function([], [])
      
   return result
  
for r in permutation([1, 2, 3, 4], 2):
   print(r)

 

여기서 중요한 점은

 

1. 재귀를 탈출하기 위한 탈출 조건이 필요하다.

이것이 없으면 n개를 모두 골랐음에도 더 숫자를 선택하기 때문에 선택된 숫자를 저장하는 배열에 범위 초과 오류가 나거나, 다른 자료구조를 쓴 경우 잘못된 출력이 나올 수 있고 무한 루프가 발생할 수 있다.

 

2. 현재 함수의 상태를 저장하는 parameter가 필요하다.

위에서 우리는 idx를 통해 어떤 숫자를 선택했는지, r을 통해 몇 개의 숫자를 선택할 것인지 전달하였다. 이것이 없다면 현재 함수의 상태를 저장할 수 없어 재귀 탈출 조건을 만들 수 없게 되거나 잘못된 결과를 출력하게 된다.

 

3. return 문

위의 함수는 단순 출력이지만 재귀를 통해 이후의 연산을 반환하고 이전 결과에 추가 연산을 수행하는 경우도 있을 수 있다.

따라서 문제해결을 위한 정확한 정의를 수행하여야 이것을 완벽히 풀 수 있다.

 

 

# 조합

def combination(arr, r):
   
   # 조합을 저장할 배열
   result = []
   
   # 실제 조합을 구하는 함수
   def function(c, index):
      # 탈츨 조건
      if len(c) == r:
         result.append(c)
         return
         
      for idx, data in enumerate(arr):
         # 중복되는 조합이 생성되지 않게 마지막으로 들어온 원소의 인덱스보다
         # 새로 추가하는 원소의 인덱스가 큰 경우만 조합을 생성한다.
            if idx > index:
               function(c+[data], idx)
    
   function([], -1)
    
   return result

for r in combination([1, 2, 3, 4], 2):
   print(r)

 

Dynamic Programming과 매우 흡사해 보인다. DP도 Top-Down을 사용 시 재귀를 통해 수행하는데, 기저 사례를 통해 탈출 조건을 만들고 현재 함수의 상태를 전달하는 parameter를 전달한다. return을 통해 필요한 값을 반환하여 정답을 구하는 연산 시에 사용한다.

 

완전탐색의 재귀와 DP의 차이점은 DP는 작은 문제가 큰 문제와 동일한 구조를 가져 큰 문제의 답을 구할 시에 작은 문제의 결과를 기억한 뒤 그대로 사용하여 수행속도를 빠르게 한다는 것이다.

그에 반해 완전탐색은 크고 작은 문제의 구조가 다를 수 있고, 이전 결과를 반드시 기억하는 것이 아니라 해결 가능한 방법을 모두 탐색한다는 차이가 있다. (DP는 일반적인 재귀 중 조건을 만족하는 경우에 적용 가능)

 

4. BFS, DFS 사용하기

그래프 자료 구조에서 모든 정점을 탐색하기 위한 방법이다.

BFS는 너비우선 탐색으로 현재 정점과 인접한 정점을 우선으로 탐색하고, DFS는 깊이우선 탐색으로 현재와 인접한 정점을 탐색 후 그 다음 인접한 정점을 탐색하여 끝까지 탐색하는 방법이다.

자세한 내용은 BFS와 DFS 포스팅을 참고하면 좋을 것 같다.