Brute Force Search (완전탐색)

정의

모든 경우의 수를 다 계산하는 탐색 방식이다.

반드시 정답을 찾아낼 수 있어 강력하지만(force) 많은 시간과 공간을 소요하는 무식한(brute) 알고리즘에 해당한다.

언제 사용하는가?

데이터의 크기가 크지 않을 때에 사용한다.

모든 경우의 수를 다 따져보는 것 이외에는 방법이 없는 경우 사용한다.

예시 - 1 찾기

2차원 배열에서 하나의 1을 제외한 모든 요소가 0이라고 하자. 이 1의 위치를 찾으려면?

data = [
	['0', '0', '0', '0'],
	['0', '1', '0', '0'],
  ['0', '0', '0', '0']
]

for i in range(data):
		for j in range(data[0]):
				if data[i][j] == '1':
					print(i, j)
					break

중첩 반복문을 이용하면 모든 경우의 수를 다 고려하는 완전탐색 알고리즘을 쉽게 이용할 수 있다.

그러나 시간복잡도가 O(N^m) 형태로 나타나기 때문에 수의 범위가 클 때에는 지양해야 한다.

Last updated