[알고리즘] 완전 탐색

완전탐색이란

완전탐색은 가능한 모든 경우의 수를 전부 체크해서 정답을 찾는 방법입니다. 

무식하게 문제를 푼다는 의미로 "Brute Force" 라고도 부릅니다. 

 

완전탐색은 시간복잡도가 주로 O(N^2) 이상이기 때문에, 입력의 개수(N)에 따른 시간 계산을 면밀히 해주어야 합니다. 

 

완전탐색 알고리즘 유형

1. Brute Force 기법 : 반복 / 조건문을 활용해 모두 테스트하는 방법
2. 순열(Permutation) : n개 중 r개의 원소를 중복 허용 없이 나열하는 방법. 
3. 재귀(Recursive) 
4. 비트마스크(Bitmask) : 2진수 비트 연산을 통해 부분 집합을 표현하는 방법
5. BFS, DFS : 그래프 자료구조에서 모든 정점을 탐색하기 위한 방법

 

예시문제

[Brute Force 기법 사용]

https://www.acmicpc.net/problem/2304

2304번: 창고 다각형

코드 보기

import sys
input = sys.stdin.readline

N = int(input())
pl = [0 for _ in range(1001)] # 가능한 모든 x 좌표에 대해 기둥의 높이를 저장
maxH = 0
maxL = 0
for _ in range(N):
  L, H = map(int, input().split())
  if maxH < H: 
    maxL, maxH = L, H
  pl[L] = H

# 모든 x 좌표를 돌며 조건에 따라 면적을 구해나간다 : 완전탐색!!

res = 0
curr = 0
# 왼쪽 그룹
for i in range(maxL+1):
  curr = max(curr, pl[i])
  res += curr
curr = 0
# 오른쪽 그룹
for i in range(1000, maxL, -1):
  curr = max(curr, pl[i])
  res += curr

print(res)

 

[Brute Force 기법 사용]

https://www.acmicpc.net/problem/2563

2563번: 색종이

코드 보기

import sys
input = sys.stdin.readline

board = [[0 for _ in range(100)] for _ in range(100)] 
size = 0

N = int(input())
arr = []
for _ in range(N):
  x, y = map(int, input().split())
  for i in range(x, x+10):
    for j in range(y, y+10):
      board[i][j] = 1

# 100*100개의 좌표를 모두 탐색하여 검은색 영역을 구함 : 완전탐색!! 

for i in range(100):
  for j in range(100):
    size += board[i][j]

print(size)

 

[순열 사용]

https://www.acmicpc.net/problem/2503

2503번: 숫자 야구

코드 보기

import sys
import itertools
input = sys.stdin.readline

all_case = list(itertools.permutations([1,2,3,4,5,6,7,8,9], 3))
N = int(input())
for _ in range(N):
  num, s, b = map(int, input().split())
  num = list(str(num))
  remove_cnt = 0

  # 9P3의 모든 케이스와 num을 대조하여 Strike, Ball을 계산 : 완전탐색!! 
  
  for i in range(len(all_case)):
    s_cnt = b_cnt = 0
    i -= remove_cnt
    
    for j in range(3):
      num[j] = int(num[j])
      if num[j] in all_case[i]:
        if j == all_case[i].index(num[j]):
          s_cnt += 1
        else:
          b_cnt += 1

    if s != s_cnt or b != b_cnt:
      all_case.remove(all_case[i])
      remove_cnt += 1

print(len(all_case))