[알고리즘] 완전탐색 알고리즘

[알고리즘] 완전탐색 알고리즘

 

내가 가장 아이디어를 떠올리지 못하는 알고리즘 중 하나이다.

시간 복잡도를 고려하다 보니 O(n^2) 시간 알고리즘이 답일까 하는 의문 때문이고 쉽다는 편견이 있어 완탐 문제를 많이 안풀어 정답률이 낮은 편이다.

이번 포스팅을 통해서 완탐 알고리즘의 방법을 정리해보려 한다.

 

1. 완전탐색 이란

이름 그대로 완전히 탐색한다는 뜻으다. 즉 가능한 경우의 수를 모두 확인하며 정답을 가지는 바업ㅂ이다.

전체를 모두 확인한다 해서 영어로는 Brute-Force 라고 한다.

대표적으로 000-999 숫자 3개를 조합한 자물쇠의 비밀번호를 풀때 모든 경우의 수를 체크하는 방법이 있을 것이다.

 

이 알고리즘의 특징은 반드시 해를 찾는다는 것이고, 단점은 시간 복잡도가 매우 높아질 수 있다는 것이다

대표적인 알고리즘을 확인해보자

2. 알고리즘 종류

◼ 단순 Burte - Force

특별한 알고리즘 없이 조건문 과 반복을 통해서 모든 경우의 수를 파악하는 방법

 

◼ 비트 마스크

이진 상태만 존재하는 경우에 사용 가능하다.

n개인 집합의 모든 부분 집합을 구해라 라는 문제에서 원소가 포함되는지 아닌다 .0,1 로 구분하여 배열에 저장하는 방식으로 해결 가능

 

◼ 재귀함수

비트 마스크와 같이 원소가 이진 선택을 하는 경우에 사용하는 경우

부분집합 문제로 생각해보자

만들고자 하는 부분집합을 타겟S 라고 할떄 타겟S = {} 인 빈 집합에서 각 워소에 대해서 해당 원소가 포함되면 타겟S에 넣고 재귀 함소 아니면 현재 타겟S를 넣고 재귀함수를 수행하는 것이다.

 

◼ 순열

완탐에서 가장 흔하게 나오는 알고리즘 유형

N개의 데이터에서 순서를 가진 m개의 데이터를 뽑는 경우

순열로 원소를 하나씩 채워 가는 방식이고 Python에서는 itertools 의 permutation 으로 사용 가능

 

◼ BFS/DFS

깊이 우선, 너비 우선 탐색으로 코딩테스트 유형에서 가장 빈번하게 제출되는 유형 중 하나이다.

보통 완전 탐색 + BFS/DFS 형식의 문제가 많이 나온다.

단순 길찾기가 아닌 주어진 문제에 장애물 또는 목적지 추가 작업이 생길때 탐색으로 완탐 후 BFS/DFS를 이용한다.

이 알고리즘은 아래 포스팅을 하였으며 완탐+BFS는 추후 해결방법론을 정리하여 포스팅 할 예정이다

2024.03.20 - [알고리즘] - DFS/BFS 탐색 알고리즘

3. 예시

단순하게 완탐만 수행하는 경우에서는 쉽지만 난이도가 올라가면 완탐을 떠올리기 쉽지 않은 문제가 있다.

일반적인 특징 으로는 입력데이터가 크기가 작고, 답의 범위가 작거나 하나의 답이 전체 문제의 답안 조건을 만족하는 경우에 해당한다.

 

◼ 예시 문제

백준  - 블랙잭

 

이 문제에서 떠올릴 아이디어는 순열을 활용한 완탐이다.

N개의 카드를 딜러가 제시하고 M 보다 작으면서 M에 가까운 수를 구하는 것이다.

즉 순열로 N개의 카드에서 3개를 선택하는 모든 경우의 수를 탐색한다.

그리고 그 모든 경우의 수 중 M에 가장 가까운 수를 선택하는 것이다.

✅ 정답 코드

import itertools
import sys

n,m = map(int,sys.stdin.readline().split())
cards = list(map(int,sys.stdin.readline().split()))

card_pers = list(itertools.permutations(cards,3))

max_value = sys.maxsize
result = 0
for card_per in card_pers:
    sum_value = sum(card_per)
    diff = m - sum_value
    if (diff <= max_value) and diff >= 0:
        max_value = diff
        result = sum_value
print(result)