완전 탐색(Brute-force)

목차

• 완전 탐색(Brute-force)
• 예시

완전 탐색(Brute-force)

• 완전 탐색 또는 브루트포스(Brute-force)는 문제의 모든 가능한 경우를 직접 탐색하여 해결하는 방법을 의미합니다.
• 문제를 해결할 때, 먼저 문제에서 주어진 범위를 토대로 시간복잡도를 계산합니다. 그 후, 해당 시간복잡도가 문제에서 제시한 제한시간을 초과하지 않는지 확인합니다.
• 파이썬에서는 대략적으로 1초에 2000만 번의 연산을 처리할 수 있다고 가정하며, 이를 기준으로 완전 탐색을 사용할지의 여부를 결정합니다.
• 완전 탐색으로 풀 수 있는 문제임에도 불구하고 문제를 보고 어떤 알고리즘들을 적용할 수 있을까 생각하다가 막히는 경우가 있을 수 있습니다. 그래서 저 같은 경우는 문제를 읽고 먼저 완전 탐색을 생각해 보고 시간을 줄일 수 있는 부분들을 찾아가는 방식으로 문제를 해결하는 편입니다.

예시

• [백준 2503] 숫자 야구
  • 이 문제를 완전탐색이 아닌 방식으로 문제를 생각하다보면은 아이디어를 생각하다가 시간이 다소 걸릴 수 있는 문제입니다. 
  • 하지만 완전 탐색을 생각하고 문제로 들어가게 된다면, 바로 해결할 수 있는 문제입니다.
  • 질문의 개수는 최대 100개이고, 숫자는 총 999까지 가능하므로 1000개(실제로는 중복되는 숫자와, 0이 들어가면 안 되기 때문에 이보다 더 작습니다.)입니다. 따라서 완전탐색으로 충분히 해결할 수 있는 시간복잡도를 가지는 문제입니다.
  • 코드
    

    • n = int(input())
      
      arr = [list(map(int,input().split())) for _ in range(n)]
      
      answer = 0
      
      def check_strike_ball(candidate,check_num):
          strike, ball = 0,0
          for i in range(3):
              for j in range(3):
                  if candidate[i] == check_num[j]:
                      if i==j:
                          strike+=1
                      else:
                          ball+=1
          return strike, ball
      
      
      for num in range(1000):
          str_num = str(num).zfill(3)
      
          if len(set(str_num))<3 or "0" in set(str_num):
              continue
          
          flag = True
          for check_num, s, b in arr:
              check_num = str(check_num)
              strike,ball = check_strike_ball(str_num,check_num)
              if s!=strike or b!=ball:
                  flag=False
                  break
          if flag:
              answer+=1
      print(answer)