완전탐색 - 기초

완전탐색이란? 🤔

모든 경우의 수를 다 해보는 방법
영어로 Brute-Force(무식하게 풀기)라고도 한다.

• 순열
• 백트래킹
• BFS

구현 과정 📌

1. 가능한 모든 가짓수를 계산해본다.
   입력, 출력 제한이 중요함

2. 어떤 식으로 구현을 할 지 생각한다.
   단순 for문 사용, 순열, 재귀(백트래킹) 등이 있다.

3. 답을 구하고, 제출해 본다.

시간 계산 ⌛️

완전 탐색 방법은 무식한 방법으로 사람은 편하지만 기계는 힘들다.
→ 적용하기 전에 시간은 우리가 계산해 주어야한다.

💡 1억번의 연산 = 1초
O(N) : 1억
O(NlogN) : 5백만
O(N^2) : 1만
O(N!) : 11

기본 문제 📁

🪄 단순 for문

포커 카드 N장 중 2장을 골라 두 장의 합이 M에 최대한 가까운 합을 구하는 문제
N장 중 2장 고르기 → nC2

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)

Q. n이 10만 이상이라면?
A. 1초 제한인 문제에서는 시간 초과

🪄 순열

N개의 정수로 이루어진 순열 중 사전순으로 M번째 위치한 순열을 구하는 문제
모든 순열의 가짓수 → N!

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

itertools 모듈의 permutations을 사용한다.
→ 입력값 순서대로 값을 유지하니 정렬이 필요하다.

Q. n이 12 이상이라면?
A. 12! = 479,001,600으로 1초 제한인 문제에서는 시간초과

🪄 백설 공주와 일곱 난쟁이

9개의 정수가 주어졌을 때, 합이 100이 되는 7개의 정수를 찾는 문제
(단, 항상 답이 유일한 경우만 입력으로 주어짐)

arr = [int(input()) for i in range(9)]
for a in range(9):
	for b in range(a+1, 9):
		if sum(arr) - arr[a] - arr[b] == 100:
			for i in range(9):
				# if i != a or i != b:
				if i not in [a, b]:
					print(arr[i])

아홉난쟁이 중에서 가짜 난쟁이 2명을 찾아야하기 때문에,
중첩 for문으로 가짜 난쟁이 2명을 a, b로 두고 찾으면 문제가 해결된다.

🪄 모든 순열

N자리 순열을 사전순으로 순서대로 출력하는 문제
itertools 모듈의 permutations을 사용하면 N자리 순열을 출력할 수 있다.

from itertools import permutations as pm
n = int(input())
arr = [i+1 for i in range(n)]
for ans in pm(arr):
	print(*ans)

순열이 아닌 조합을 구하고 싶다면 combinations
중복조합을 구하고 싶다면 combinations_with_replacement

🪄 추첨상 사수 대작전! (Easy)

임의의 정수들이 주어졌을 때, 나머지 두 정수를 알아내 식을 완성하는 문제
(a,c) 조합의 개수는 최대 1만개이므로 완전탐색으로 문제를 풀 수 있다.

m, Seed, X1, X2 = map(int, input().split())
for a in range(100):
	for c in range(100):
		if X1 == (a * Seed + c) % m:
			if X2 == (a * (a * Seed + c) % m + c) % m:
				print(a, c)
				exit()

가능한 답이 여러 개라면, 그 중 아무거나 하나를 출력해도 되기 때문에 exit()로 종료한다.