2.1 완전 탐색 (BruteForce)

1. 완전탐색이란?

완전탐색은 가능한 모든 경우에 대해서 일일이 수행해보는 알고리즘을 말합니다.

 

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

 

예를 들어, 4자리의 암호로 구성된 자물쇠를 풀려고 시도한다고 생각해봅시다. 이 자물쇠가 고장난 것이 아니라면, 반드시 해결할 수 있는 가장 확실한 방법은 0000 ~ 9999까지 모두 시도해보는 것입니다.

(최대 10,000번의 시도로 해결 가능)

 

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

 

1. 사용된 알고리즘이 적절한가? ( 문제를 해결할 수 있는가 )
2. 효율적으로 동작하는가?

 

위 2가지의 규칙에 대해서 생각할 때, 1번은 만족될 수 있는 가장 확실한 방법이겠으나 대부분의 경우 2번의 경우 때문에 이 방법이 사용되는데는 제한이 따릅니다.

 

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

우선 완전탐색 기법으로 문제를 풀기 위해서는 다음과 같이 고려해서 수행합니다.

 

1) 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다.
2) 가능한 모든 방법을 다 고려한다.
3) 실제 답을 구할 수 있는지 적용한다.

 

여기서 2)의 모든 방법에는 다음과 같은 방법 등이 있습니다.

 

① Brute Force 기법 - 반복 / 조건문을 활용해 모두 테스트하는 방법
② 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
③ 재귀 호출
④ 비트마스크 - 2진수 표현 기법을 활용하는 방법
⑤ BFS, DFS를 활용하는 방법

 

 

3. 각 방식에 대한 설명

 

① Brute Force 기법

이 방법은 반복 / 조건문을 통해 가능한 모든 방법을 단순히 찾는 경우를 의미합니다. 예를 들어, 위의 자물쇠 암호를 찾는 경우와 같이 모든 경우를 다 참조하는 경우가 그러합니다.

 

② 순열(Permutation)

우선 순열이 무엇인지 이해해봅시다. 

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

 

즉, 순서가 중요합니다!

 

만약, 수열에서 숫자 [1, 2, 3]이 있다면, 이것을 [1, 2, 3]으로 보는 순서와 [3, 2, 1]로 보는 순서가 차이가 있음이 중요한 경우를 의미합니다.

 

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

 

그래서, 만약 N개의 서로 다른 데이터가 있고 이를 순열로 나타낸다면 전체 순열의 가지 수는 N!개가 됩니다. 최초에 N개 중 1개가 올 수 있고 그 이후에는 각각 N-1, N-2, ... , 1개가 올 수 있어 이를 모두 곱하면 N!이 되기 때문입니다.

 

[1, 2, 3]을 사전 순으로 나열하는 순열이 있다고 가정해봅시다.

 

그러면 아래와 같이 나열될 수 있을 것입니다.

 

 

위 내용과 같이 순열을 나열할 수 있는데, 최초 / 최종 순열을 보면 숫자가 오름 / 내림차순인 것을 알 수 있습니다.

(중복된 숫자가 있다면 비내림 / 비오름차순으로 된다.)

 

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

(반대로 최초 순열이면 i+1부터 N이 오름차순!)

 

예를 들어, 1 3 2를 보자. 이는 0번째 숫자가 1일 때의 최종 순열입니다. 왜냐하면 3 2는 내림차순이기 때문이다. 그렇다면 이 다음 순열은 어떻게 구할 수 있을까요?

 

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]가 되는 가장 큰 i는 6인 3번째(0부터 시작)이다. 즉, i=3이 된다.

2. j >= i 중, A[j] > A[i-1]을 만족하는 가장 큰 j의 값을 찾는다.
  → 현재가 최종 순열 상태이므로 i-1번째 숫자를 변경하여 최초 순열을 찾아야 한다.
      A배열을 기준으로 i-1번째 숫자는 3으로 3보다 큰 경우는 6, 5, 4이나 그 중 j 값이 가장 큰 경우는 4이다.

3. A[i-1]과 A[j]를 Swap한다.
   → i-1인 2번째 숫자 3과 j인 5번째 숫자 4를 변경한다. A 배열은 다음과 같이 변경된다.
      A={7, 2, 4, 6, 5, 3, 1}

4. i이후의 순열을 모두 뒤집는다.
   → 최초 순열 상태로 만들어야 하므로 i번째부터는 오름차순으로 만들어야 한다. A 배열은 다음과 같이 변경된다.
      A={7, 2, 4, 1, 3, 5, 6}

 

 

n = 4
perm = [1, 2, 3, 4]

def get_next_perm():
    i = n - 1
	
 	# 1번
    while i > 0 and perm[i - 1] >= perm[i]:
        i -= 1

    if i <= 0:
        return False

	# 2번
    j = i - 1
    while j < n - 1 and perm[j + 1] > perm[i - 1]:
        j += 1

	# 3번
    perm[i - 1], perm[j] = perm[j], perm[i - 1]

	# 4번
    j = n - 1
    while i < j:
        perm[i], perm[j] = perm[j], perm[i]
        i += 1
        j -= 1

    return True

while get_next_perm():
    print(*perm)

※ print(*perm)는 리스트의 각 원소를 공백으로 구분하여 출력하는 방법입니다.

 

위 로직의 시간복잡도는 어떨까요?

 

전체 N개의 숫자에 대해 각각 순열을 구하는 문제가 됩니다.

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

 

N!은 굉장히 높은 시간 복잡도를 갖습니다. N=10이면 되어도 약 360만 번의 연산이 수행되며 N=11이 되면 4억 번의 연산이 필요합니다.

 

따라서 이 방법은 항상 사용할 수는 없고, 문제에서 주어진 N의 크기를 고려해야만 합니다.

 

 

③ 재귀(Recursive)

재귀는 말 그대로 자기 자신을 호출한다는 의미입니다. 왜 자기 자신을 호출할 필요가 있을까요?

 

예를 들어, 총 4개의 숫자 중에 2개를 선택하는 경우를 모두 출력한다고 가정해봅시다. 1~4까지 숫자가 있고 2개를 중복 없이 선택하는 모든 경우의 수를 출력하고자 한다면, 이를 반복문으로 표현한다면 다음과 같을 것입니다.

 

for i from 1 to 4..
    chose i
    for j from i+1 to 4..
        chose j
        print i j

 

손 쉽게 2중 반복문으로 해결하였습니다. 그런데.. 만약 숫자 N개의 숫자 중 M개를 고르는 경우라고 할 때, N과 M이 매우 큰 숫자라면 어떨까요? 반복문을 수백, 수천 개를 써 내려갈 수는 없습니다.

 

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

 

lim = 100  # 1~100까지의 제한
n = 5      # 5개만 고른다.

def solve(chosen, curr, cnt):
    if cnt == n:
        print(*chosen)
        return
    
    for i in range(curr + 1, lim + 1):
        chosen[cnt] = i
        solve(chosen, curr, cnt + 1)

chosen = [0] * n
solve(chosen, 0, 0)

※ print(*chosen)는 리스트의 각 원소를 공백으로 구분하여 출력하는 방법입니다.

 

여기서 중요한 점!

⑴ 재귀를 탈출하기 위한 탈출 조건이 필요!
  ▶ 이것이 없으면 n개를 모두 골랐음에도 더 숫자를 선택하고자 하여  다른 자료구조나 언어를 쓴 경우 잘못된 출력이 나올 수 있고, 혹은 무한 루프가 발생할 수 있습니다!

 

⑵ 현재 함수의 상태를 저장하는 Parameter가 필요!
  ▶ 위에서 우리는 curr, cnt를 통해 어떤 숫자까지 선택했는지, 몇 개를 선택했는지 전달하였습니다. 이것이 없다면 현재 함수의 상태를 저장할 수 없어 재귀 탈출 조건을 만들 수 없게 되거나 잘못된 결과를 출력하게 됩니다!

 

⑶ Return문을 신경 쓸 것!
  ▶ Return문을 이용하지 않으면, 재귀를 통해 이후의 연산 결과를 반환 후 이전 결과에 추가 연산을 수행하는 경우도 있을 수 있습니다. 즉, 문제 해결을 위한 정확한 정의를 수행하여야 이것을 완벽히 풀 수 있습다.

 

잘 생각해보면 Dynamic Programming과도 매우 흡사해 보입니다. 그 또한 Top-Down을 사용 시 재귀를 통해 수행하는데, 기저 사례를 통해 탈출 조건을 만들고, 현재 함수의 상태를 전달하는 Parameter를 전달합니다.

 

또한 Return을 통해 필요한 값을 반환하여 정답을 구하는 연산 시에 사용하게 됩니다.

 

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

 

그에 반해 완전 탐색은 크고 작은 문제의 구조가 다를 수 있고, 이전 결과를 반드시 기억하는 것이 아니라 해결 가능한 방법을 모두 탐색한다는 차이가 있습니다.

 

④ 비트마스크(Bitmask)

비트마스크란 비트(bit) 연산을 통해서 부분 집합을 표현하는 방법을 의미합니다.

 

비트 연산이란 다음과 같은 것들이 있습니다.

 

And 연산(&) : 둘 다 1이면 1
OR 연산(|) : 둘 중 1개만 1이면 1
NOT 연산(~) : 1이면 0, 0이면 1
XOR 연산(^) : 둘의 관계가 다르면 1, 같으면 0
Shift 연산(<<, >>) : A << B라고 한다면 A를 좌측으로 B 비트만큼 미는 것이다.

 

그런데 우리는 1, 0만을 사용할 것이 아니라 각 모든 숫자를 비트 연산할 수 있어야 합니다. 모든 숫자는 2진수로 표현될 수 있기 때문에 2진수를 통해 비트연산을 수행할 수 있습니다.

 

만약, 13과 72를 2진수로 나타낸다면 어떨까요? 

 

13=1101(2)13=1101(2)
72=1001000(2)72=1001000(2)

 

그러면 13의 경우에는 부족한 앞의 3자리를 0으로 채우고 비트연산을 수행할 수 있습니다. 

 

 

비트 연산의 시간복잡도는 내부적으로 상수 시간 정도로 처리가 되어 O(1)이라고 보면 됩니다.

(그렇다고 프로그래밍 시 산술 연산을 비트 연산으로 모두 바꾸는 것은 오히려 비효율적입니다. 유지보수에도 좋지 않고 실제로 미미한 차이만 나기 때문입니다.)

 

비트 연산으로 집합을 나타내는 법

 

비트마스크는 정수로 집합을 나타내는 것이 가능합니다.

예를 들어 0~9 까지의 숫자로만 이루어지는 정수 집합이 있다고 할 때, 그 중 하나의 부분 집합이 A라고 해봅시다.

 

그럼 A = {1, 3, 4, 5, 9} 라고 가정하면, 이를 570이라는 하나의 숫자로 나타낼 수 있습니다.

 

즉, A=570

 

왜냐하면, 아래와 같은 표를 보면 각각의 숫자가 있는 경우 1, 없는 경우 0으로 표시할 수 있기 때문입니다.

숫자	9	8	7	6	5	4	3	2	1	0
비트	1	0	0	0	1	1	1	0	1	0

 

그러면, 저 비트를 하나의 이진수라고 본다면 1000111010(2)1000111010(2)와 같으므로 10진수로 해보면 570이 되기 때문입니다.

 

이 정수로 사용하게 되면 전체 저장 공간 또한 절약이 되고 정수이기 때문에 index로도 활용이 가능하므로 매우 큰 장점이 있습니다.

 

이 비트마스크로 집합을 나타낼 때는 0~N-1까지 정수로 이루어진 집합을 나타낼 때 사용됩니다.

 

1~N까지로 하면 1개의 비트가 더 필요하여 전체 공간이 2배가 됩니다.(시간도 2배가 됨) 그래서 0~N-1까지로 활용합니다.  (또한, 0이 없으면 연산을 더 변형해야 함.)

 

⑤ BFS, DFS 사용하기

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

 

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

 

 

 

너비 우선 탐색(BFS, Bread-First Search)

from collections import deque

# BFS
def BFS(graph, start, visited):
  # 큐(Queue) 구현을 위해 deque 라이브러리 사용
  queue = deque([start])

  # 현재 노드 방문 처리
  visited[start] = True

  # 큐가 빌 때까지 반복
  while queue:
    # 큐에서 하나의 원소를 뽑아 출력
    v = queue.popleft()
    print(v, end = ' ')

    # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True



visited =[False] * 9

# 각 노드가 연결된  정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
  [],                 # 1번 노드와 연결된 노드들
  [2, 3, 8],          # 2번 노드와 연결된 노드들
  [1, 7],             # 3번 노드와 연결된 노드들
  [1, 4, 5],          # 4번 노드와 연결된 노드들
  [3, 5],             # 5번 노드와 연결된 노드들
  [3, 4],             # 6번 노드와 연결된 노드들
  [7],                # 7번 노드와 연결된 노드들
  [2, 6, 8],          # 8번 노드와 연결된 노드들
  [1, 7]              # 9번 노드와 연결된 노드들
]

BFS(graph, 1, visited)
# 결과
1 2 3 8 7 4 5 6

재귀적으로 동작하지 않으며, 그래프 탐색의 경우, 어떤 노드를 방문했었는지 여부를 반드시 검사합니다.
(검사하지 않으면 무한루프)

 

BFS는 방문한 노드들을 차례로 저장하고 꺼낼 수 있는 큐를 사용(FIFO)하고 넓게 탐색합니다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용합니다.

 

깊이 우선 탐색(DFS, Depth-First Search)

# DFS

# 방문 정보를 리스트 자료형으로 표현
visited =[False] * 9

# 각 노드가 연결된  정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
  [],                 # 1번 노드와 연결된 노드들
  [2, 3, 8],          # 2번 노드와 연결된 노드들
  [1, 7],             # 3번 노드와 연결된 노드들
  [1, 4, 5],          # 4번 노드와 연결된 노드들
  [3, 5],             # 5번 노드와 연결된 노드들
  [3, 4],             # 6번 노드와 연결된 노드들
  [7],                # 7번 노드와 연결된 노드들
  [2, 6, 8],          # 8번 노드와 연결된 노드들
  [1, 7]              # 9번 노드와 연결된 노드들
]


def DFS(graph, v, visited):
  # 현재 노드를 방문 처리
  visited[v] = True
  print(v, end = ' ')

  for i in graph[v]:
    if not visited[i]:
      DFS(graph, i, visited)

# 현재 노드와 연결된 다른 노드를 재귀적으로 방문

DFS(graph, 1, visited)
# 결과
1 2 7 6 8 3 4 5

재귀적으로 동작(재귀, 스택)합니다. 그래프 탐색의 경우, 어떤 노드를 방문했었는지 여부를 반드시 검사합니다.
(검사하지 않으면 무한루프)

 

모든 노드 방문하고자 할 때 사용합니다. BFS 보다 간단하지만, BFS 비해서 검색 속도 느립니다. 

 

 

위의 방법들 중 상황에 따라 이용 가능한 방법을 활용하여 문제를 해결할 수 있는지 테스트하고 실제 답을 구해보는 훈련을 통해 문제 해결 역량을 기를 수 있습니다. 저 또한 노력할 생각입니다.

 

 

참고 블로그

 

https://hongjw1938.tistory.com/78

알고리즘 - 완전탐색(Exhaustive Search)

 

https://velog.io/@hyehyes/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89

[알고리즘] 완전탐색