[알고리즘] 완전탐색 기본 (Python)

출처 : https://www.youtube.com/watch?v=V_Z77_klksI

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

컴퓨터의 빠른 계산능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 알고리즘 

 

- 완전탐색 알고리즘 = Brute-force 알고리즘(무식하게 풀기)

- 즉, 무식하게 모든 경우의 수를 다 따져가며 정답을 찾는 방식이다. 하지만 직관적이며 이해하기 쉽고 문제의 정확한 결과를 얻을 수 있는 가장 기초적인 방식이다. 

 

예시를 한번 살펴 보자

 

4자리의 암호로 구성된 자물쇠를 풀려고 시도한다. 이 때, 자물쇠가 정상적으로 작동한다면 반드시 해결할 수 있는 문제이다. 0000~9999까지 모든 경우의 수를 다 입력할 수 있기 때문이다. 물론 사람의 손으로 작동시킨다면 아주 오랜 시간이 걸릴 것이다. 하지만 우리에게는 위대한 발명품이 있다. 바로 연산속도가 매우 빠른 컴퓨터 ! 

 

이렇게 컴퓨터의 속도를 믿고 10,000번의 탐색을 모두 진행하는 것이 바로 완전 탐색이다. 

 

 

 

2. 완전 탐색 기법 

완전 탐색은 그 자체로 알고리즘이 아니다. 그렇기에 이 완전 탐색을 이용하기 위해서 여러 알고리즘 기법들이 사용된다. 

 

- 순열

- 백트래킹

- BFS/DFS

- 재귀함수

- 단순 Brute-Force

 

완전 탐색은 N의 크기가 작을 때, 주로 이용된다. 

 

 

3. 완전 탐색과 시간복잡도 

완전 탐색은 '어떻게 푸느냐' 보다 '얼마나 걸리냐'가 더 중요한 문제이다. 따라서 시간복잡도의 계산이 중요한 알고리즘이다. 

완전탐색의 시간복잡도는 O(N)이다. 

 

보통 1억번의 연산 = 1초

O(N) : 1억
O(N logN) : 5백만
O(N**2) : 1만
O(N!) : 11 ( 11!= 약 4천만 , 12! = 약 5억 ) 

 

 

4. 완전 탐색의 2가지 규칙 적용 

 - 사용된 알고리즘이 적절한가 ?

      ( = 문제를 해결할 수 있는가 ? )

 - 효율적으로 동작하는가 ?

      (= 완전 탐색 기법 사용 시 , 그 문제에 대한 파악이 필요하다. )

 

완전탐색은 앞서 말했듯이 시간에 대한 탐구가 중요하다. 그렇기에 2번째 규칙을 중요시 한다. 

그렇기에 완전 탐색의 구현과정도 가장 먼저 시간 복잡도에 대한 계산을 한 후 진행한다. 

완전 탐색의 구현과정
1. 가능한 가짓수를 계산해본다. 이때, 입출력 제한이 중요하다. 
2. 어떤 식으로 구현할 지 생각해본다. 
  - 단순 for문을 사용할 것인지, 순열을 사용할 것인지, 재귀, 백트래킹 등등.. 
3. 답을 구하고 제출한다. 

 

 

5. 기본코드 

한국항공대학교 알고리즘 학회 KOALA 영상을 참고하여 작성하였습니다. 
https://www.youtube.com/watch?v=j7rvq0chfh0

  01) 단순 for문 

P . 포커 카드 N장 중 2장을 골라 두 장의 합이 M에 최대한 가까운 합을 구하시오 

n,m = map(int,input().split())
arr= [*map(int,input().split())]
ans = 0
for i in range(n):
    for j in range(i+1 , n):
        sumCard = arr[i] + arr[j]
        if abs(sumCard-m) < abs(ans-m):
            ans = sumCard
print(ans)

if ) n 이 10만 이상인 경우 -> 1초 제한문제에서는 시간 초과 (n장 중 2 장 = nC2)

 

 

  02) 순열 

P . N개의 정수로 이루어진 순열 중 사전순으로 M번째 위치한  순열은 ?

from itertools import permutations as pm
n,m = map(int,input().split())
arr= [*map(int,input().split())]
print(*sorted([*pm(arr)])[m-1])

** 순열의 모든 가짓수 -> N!