완전탐색(Brute Force)

완전탐색은 어떤 문제에 대해, 해가 될 수 있는 정답 후보 집합을 결정하고, 그 집합의 모든 원소를 순회하며 조건에 만족하는 원소를 해로 확정하는 방법이다. 대부분의 문제를 이 방식으로 풀 수 있으나, N이 작아야 한다.

• 목적
  • 문제를 최대한 쉽게 풀자
  • 컴퓨터의 연산속도를 이용하자
  • 아무리 느리더라도 답은 정확하게 구해보자
• 문제풀이의 흐름
  1. 모든 문제에 대해 느린 정답 만들기
  2. 통과되지 않는 문제 $\rightarrow$ 최적화 $\Rightarrow$ 문제풀이의 시작점!

모든 정답 후보를 골라서 계산해보고 맞는 후보를 출력

tip

for 정답 후보 모두 살펴보기:
	for ...
		for ...
			# 각 후보를 확인하기

두 자리를 정하여 완전탐색

// 정답의 후보 탐색
for (int i = 0; i < n; i++) {
	for (int j = i + 1, j < n; j++) {
		// 후보가 정답의 조건을 만족하는지 확인
	}
}

2차원 배열에서의 완전 탐색

$n \times n$ 개에서 잡을 수 있는 시작점

1, 3 $\Rightarrow$ 행 n개, 열 n-2개 2, 4 $\Rightarrow$ 행 n-1개, 열 n-3개

배열 기록 후 구간 정하기

• 배열 자체가 주어지지 않는 경우
• 주어진 값들을 적절히 배열로 표현 후 탐색하기

모든 구간 정하기

모든 길이에 대해 구간 탐색

자리마다 숫자 정하기

범위 내 모든 숫자 탐색

물체 하나를 정하여 완전탐색

• 시간복잡도 : $O(N^2 R)$
• 최적화

n = 5
r = 100
arr = [...]

for i in range(n):  # 제거
	cnt = [0 for j in range(r+1)]
	for j in range(n):  # 색칠
		if j == i: continue

		x, y = arr[j]
		for  k in range(x, y+1):
			cnt[k] += 1

• 제거 : 시간복잡도가 줄지 않음

• 색칠

  • 미리 색칠해놓기
  • 제거되었을 때 빼보기
  • $O(NR)$

• 좌표평면 위의 특정 구역

  • 최적화?
    • x좌표, y좌표별로 정렬
    • 최대 최소별로 포인터 두고 처리
    • $O(N\log N)$ 으로 줄일 수 있다

탐색 범위가 명시된 경우의 완전 탐색

TIP : 숫자에서 자릿수 추출

a = (i // 10000) % 10
b = (i // 1000) % 10
c = (i // 100) % 10
d = (i // 10) % 10
e = (i // 1) % 10
....

혹은

2345 % 10    [5]
2345 // 10
234 % 10     [5, 4]
234 // 10
23 % 10      [5, 4, 3]

....

탐색 범위가 불명확한 경우의 완전 탐색

가능한 탐색 범위를 완전 탐색

• 최적화? 경계선만 보기

머리 아픈 문제를 풀어내는 가장 단순한 방법

$\Rightarrow$ 모든 가능한 해 찾아보기

독서실의 거리두기

• 최적화 아이디어
  1. 먼저 초기값에 대한 거리, 1의 앞뒤 마지막 위치 구해두기
     • ex) [-1, -1, 2, 3, ....], [..., 12, 12, -1]
  2. 누구 한 명을 추가했을 때 생기는 추가 거리와 기존 closest_dist 와 비교, 업데이트

관심을 둘 대상에 대한 선택

ex. 선분 겹침 문제

1에서 포함되는 선분 몇 개? 2에서 포함되는 선분 몇 개? .... N에서 포함되는 선분 몇 개?

최대/최소간의 차이가 정해져 있는 경우

• 풀이 1
  • 2 이하가 되는 상태를 찾아보기
  • 최종 상태 숫자들을 a, b으로 바꾼다 (범위 정하기)
  • 비용을 비교하며 정답을 찾는다.