[파이썬(python) 알고리즘] 브루트 포스 / 투 포인터 기법

브루트 포스 (brute force)

• 가능한 모든 조합을 다 탐색 (답이 나올 때까지)
• 답을 무조건 찾을 수는 있으나, 답을 찾는 데에 비용이 너무 크다는 단점이 있음. (시간 복잡도가 크다. 탐색해야 할 것이 많다면 코테에서 타임아웃이 뜰 것)
• 대체적으로 완전 탐색의 시간 복잡도는 O(n!) or O(2^n)

Ex) 리트코드 15번 3Sum

 합이 0이 되는 3개의 수의 조합을 찾는다. 이때 brute force는 가장 간단한 방법. but, 3개이므로 배열에서 3번의 loop을 돌아야 하기 때문에 (double nested loop) 시간 복잡도가 O(n^3)임. 따라서 매우 비효율적인 방법이라고 할 수 있다. 또한 코드 가독성 또한 떨어짐. (아래 참고)

 

for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            for j in range(i+1,len(nums)-1):
                if j > i+1 and nums[j] == nums[j-1]:
                    continue
                for k in range(j+1, len(nums)):
                    if k > j+1 and nums[k] == nums[k-1]:
                        continue
                    tmp = nums[i] + nums[j] + nums[k]
                    if tmp == 0 :
                        res.append([nums[i], nums[j], nums[k]])

→ 비교대상만큼 for 문을 작성해야하므로 가독성이 떨어진다.

 

---

투 포인터 기법

1차원 배열에서 각 다른 원소를 가리키는 2개의 포인터(시작과 끝)를 조작해가면서 원하는 것을 얻는 형태 (두 개의 포인터가 만나면 break)

 

Ex) 리트코드 1번

배열의 원소 중 더해서 주어진 target값이 되는 2개의 수의 조합을 찾는다.

 

(입력) num = [2,7,11,15], target = 9

(출력) [2,7]

 

1) brute force 풀이

  간단하게 브루트 포스로 푼다면 2개의 수의 조합을 찾는 것이므로 2번의 반복문을 사용하면 된다. (nested loop)

 

for i in range(len(nums)-1):
	for j in range(i, len(nums)):
		if nums[i] + nums[j] == target:
			return [nums[i], nums[j]]

→ 간단하게 이런 식으로 풀이할 수 있을 것

두 번의 반복문을 사용하는 것이므로, 전체 배열을 두 번 탐색한다고 볼 수 있다.

 

 

2) 투포인터 기법

여기서 투포인터를 활용하면 좀 더 효율적인 풀이가 가능하다.

투 포인터를 활용하면 배열을 한 번만 탐색하기 때문에 이 경우에 시간복잡도는 O(n)이 될 것이다.

 

start, end = 0,0
while start < end:
	tmp = nums[start] + nums[end]
	if tmp == target:
			return [nums[start], nums[end]]
	elif tmp > target: # target보다 크니까 큰 값을 줄인다.
		right -= 1
	else: # target보다 작으니까 작은 값을 키운다.
		left += 1
	

 

위에 코드에서처럼 한 번의 탐색만으로 정답을 찾아낼 수 있다.

이 문제에서 투포인터는 기본적으로 left는 작은 값을, right는 큰 값을 가리킨다는 걸 전제로 하고 있다.

즉, 리스트의 정렬이 선행되면 좀 더 효율적인 문제풀이가 가능하다.

기본적으로 여러 문제에서 사용이 되고, 퀵정렬과 같은 정렬을 구현하는 데에도 사용이 된다.

 

cf.) 퀵정렬

퀵정렬은 분할정복 기법으로, 정렬되지 않은 리스트에서 pivot(중심축)을 기준으로 하나의 리스트를 pivot보다 작은 부분리스트와 pivot보다 큰 부분리스트로 분할하고, 각 부분리스트를 다시 퀵정렬하는 방식임.

이때 분할하는 데에 투포인터가 쓰임.

(정확히 여기서는 공간복잡도를 줄이는 방식으로 쓰이는 것 같네요. 자세한 건 아래 참고)

퀵정렬[Quick sort]이란?