[알고리즘] 완전 탐색 (Brute Force)

🕯️ 개념

가능한 경우의 수를 모두 조사해서 정답을 찾는 방법

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

[종류]

1. Brute Force : 반복/조건문을 통해 가능한 모든 방법을 단순히 찾는 경우
2. 백트래킹 (Backtracking) : 현재 상태에서 가능한 후보군으로 가지를 치며 탐색하는 알고리즘. 분할 정복을 이용한 기법으로, 재귀함수를 이용하고 해를 찾아가는 도중 해가 될 것 같지 않은 경로가 있다면 더 이상 가지 않고 되돌아간다.
3. 순열 (Permutation) : 임의의 수열이 주어졌을 때 그것을 다른 순서로 연산하는 방법
4. 비트 마스크 (Bit Mask) : 2진수를 이용하는 컴퓨터의 연산을 이용하는 방식. 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용 가능
5. 재귀함수
6. DFS/BFS

 

---

👩‍💻 코드

• 순열

from itertools import permutations

permutations(arr, n)

 

---

⏰ 시간복잡도

주로 O(N!), O(2^N)이다.

 

---

💭 언제 필요해?

1. 입력으로 주어지는 데이터(N)의 크기가 매우 작다.
2. 답의 범위가 작고, 임의의 답을 하나 선택했을 때 문제 조건을 만족하는지 역추적할 수 있다.
3. 여러 문제 조건 중 한 조건을 고정시키면 문제 풀이가 간단해진다.

 

---

👑 예제

[프로그래머스 - 소수 찾기]

import math
from itertools import permutations

def is_prime_num(n):
    if n == 1 or n == 0:
        return False
    
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False

    return True

def solution(numbers):
    numbers = list(numbers)
    answer = 0
    
    perm = []
    for i in range(1, len(numbers)+1):
        perm += list(permutations(numbers, i))
        
    nums = [int(''.join(i)) for i in perm]
    nums = list(set(nums))
    
    for i in nums:
        if is_prime_num(i):
            answer += 1
    
    return answer

 

[프로그래머스 - 카펫]

# 내 풀이
import math

def get_divisor(num):
    divisors = []
    length = int(math.sqrt(num)) + 1
    
    for i in range(1, length):
        if num % i == 0:
            divisors.append(i)
            divisors.append(num//i)

    divisors.sort(reverse = True)
    return divisors

def solution(brown, yellow):
    answer = []
    entire = brown + yellow
    
    divisor = get_divisor(entire)
    l = len(divisor)
    n = l//2
    
    for i in range(n):
        if divisor[l-i-1] > 2 and (divisor[i]-2) * (divisor[l-i-1]-2) == yellow:
            answer = [divisor[i], divisor[l-i-1]]
    
    return answer

# 예시 풀이
def solution(brown, yellow):
    for i in range(1, int(yellow**(1/2))+1):
        if yellow % i == 0:
            if 2*(i + yellow//i) == brown-4:
                return [yellow//i+2, i+2]

 

[백준 - 2309 : 일곱 난쟁이]

• 내 코드 (brute force)

  from itertools import permutations
  
  arr = [int(input()) for i in range(9)]
  
  for i in list(permutations(arr, 7)):
  
      if sum(list(i)) == 100:
          answer = list(i)
          answer.sort()
  
          for i in answer:
              print(i)
              
          break

 

[백준 - 1182 : 부분수열의 합]

• 내 코드 (brute force)

  import sys
  from itertools import combinations
  
  input = sys.stdin.readline
  n, s = map(int, input().split())
  arr = list(map(int, input().split()))
  
  answer = 0
  
  for i in range(n):
      combi = list(combinations(arr, i+1))
  
      for j in combi:
          if sum(list(j)) == s:
              answer += 1
  
  print(answer)

• 재귀와 백트래킹을 이용한 코드

  import sys
  input = sys.stdin.readline
  n, s = map(int, input().split())
  arr = list(map(int, input().split()))
  cnt = 0
  
  def subset_sum(idx, sub_sum):
      global cnt
  
      if idx >= n:
          return
  
      sub_sum += arr[idx]
  
      if sub_sum == s:
          cnt += 1
      
      # 현재 arr[idx]를 선택한 경우의 가지
      subset_sum(idx+1, sub_sum)
  
      # 현재 arr[idx]를 선택하지 않은 경우의 가지
      subset_sum(idx+1, sub_sum - arr[idx])
  
  subset_sum(0, 0)
  print(cnt)

 

[그 외 백준 추천 문제들]

• 2231 : 분해합
• 3085 : 사탕 게임
• 10448 : 유레카 이론
• 2503 : 숫자 야구
• 1018 : 체스판 다시 칠하기