완전 탐색의 접근방법과 사용할 수 있는 방법들

완전 탐색의 개요와 접근 방법

완전 탐색(Brute Force)의 개념은 말 그대로 모든 가능성을 계산하고 정답을 찾는 유형의 문제이다.

일반적인 완전탐색은 접근법만 알면 매우 쉬워져 까다롭게 만들 경우에 구현 문제도 같이 섞여 들어오는 경우도 있다.

 

우선 문제가 완전 탐색인가를 확인하기 위해서는 다음을 확인해보면 좋다.

• 계산해야할 입력 데이터의 길이나 범위 N의 값이 작다
  • 모든 경우의 수를 찾는 방법이기 때문에 해당 경우의 수를 찾는데 시간이 꽤 소요되므로 1~2초 정도의 시간제한이 있는 문제라면 입력 데이터의 길이나 범위가 작을 수 밖에 없다.
• 그리디로 해결해보려고 할 경우에 최적해를 찾을 마땅한 방법이 떠오르지 않는다.
  • 말 그대로 그리디로 해결해보려고 하면 최적해를 찾기 매우 힘들거나 방법이 잘 보이지 않고, 반례가 몇 개씩 존재하는 경우가 나온다.
• 문제의 본질적 내용이 순열 및 조합을 사용하여 순서쌍으로 계산하는 과정이 보인다.
  • 모든 "경우의 수" 에 대하여 계산하는 것이므로 경우의 수를 만드는 것 자체에 순열 또는 조합이 들어갈 수 있다.

보통 문제를 판단할 때 필자의 경우에는 1, 3번을 중점적으로 살펴본다. 2번은 박아봐야 알지만, 1, 3번은 문제 자체를 읽어보는것만 해도 어느 정도 감이 잡힐 수 있기 때문이다.

 

접근 방법

• 완전 탐색의 문제는 반드시 모든 경우의 수를 만들 수 있는 방법이 문제에 주어져 있다. 따라서 문제를 천천히 읽어보며 경우의 수를 만드는 방법이 어떤 것인지를 확인해야 한다.
• 일반적으로 순열과 조합이 꽤 많이 사용된다. 물론 대놓고 순열과 조합을 써라는 문제들은 잘 없고, 샘플 테스트 케이스나 문제 지문의 설명에서 순열이나 조합을 쓰는 것을 암시적으로 알려준다.
• 모든 경우의 수를 뽑아낼 경우에 해당 경우들을 하나씩 검증해 가며 답이 맞는가를 확인하면 끝나는 문제로 검증 자체는 크게 어렵지 않다. 따라서 모든 경우의 수를 어떻게 내놓을 수 있는가가 해당 유형의 문제 풀이에 가장 큰 영향을 미치는 요소이다.

 

사용할 수 있는 방법들

• 일반적으로 PS에 사용되는 언어인 C++/C, Python의 경우에는 순열과 조합을 라이브러리로 사용 가능하게 해놓았다. (Java는 제공해주지 않는다...)
• C++/C의 경우에는 STL로 지원하며 Python의 경우에는 itertools 모듈에 있는 Permutations와 Combinations가 있다. 필자는 Python을 사용하므로 itertools의 Permutations, Combinations를 사용할 것이다.

 

아래는 순열을 사용한 경우의 수 산출 방식이다.

from itertools import permutations

N = int(input())
data = [x for x in range(1, 6)]

per = permutations(data, N)

for element in per:
    print(element)

해당 코드는 N을 표준 입력으로 받아 1~5까지의 수 중 N개를 뽑는 모든 경우의 수를 출력한다.

만약 수를 저렇게 list로 표현하고 싶지 않고 간략히 하고 싶을 경우, data가 아닌 range(1, 6)으로 해도 무방하다.

 

permutations의 경우엔 모든 경우의 수를 계산하여 tuple로 변환한 뒤, permutations 자체 타입으로 넘겨주기 때문에 사용에 용이하게 하기 위해선 list로 변환하여 조작하는것이 좋다.

 

다음은 조합을 사용한 경우의 수 출력이다.

from itertools import combinations

N = int(input())
data = [x for x in range(1, 6)]

per = combinations(data, N)

for element in per:
    print(element)

사용법은 동일하다. 반환 형식도 동일하다.

 

문제들 중 일반 순열이나 조합을 사용하지 않는 경우가 있다. 보통 중복을 허용하는 문제들이 그러한데 중복을 허용하는 문제의 경우에도 itertools로 해결이 가능하다

중복 순열의 경우에 product가 존재하고, 중복 조합의 경우 combinations_with_replacement가 존재한다. 아래는 사용 코드이다.

from itertools import product
from itertools import combinations_with_replacement

N = int(input())
data = [x for x in range(1, 6)]

pro = product(data, repeat=N)
comb = combinations_with_replacement(data, N)

for element in pro:
    print(element)

product의 경우 permutations와는 다르게 repeat라는 매개변수에 N을 넣음으로서 전체 중복순열을 만들어 낸다.

이후에는 해당 함수를 사용하여 얻은 데이터들을 하나씩 조회하여 답이 맞는지 확인함으로서 문제를 해결할 수 있다.