이번에 살펴볼 알고리즘은 주어진 숫자의 리스트에서 임의의 두 수의 합이 S와 같은 pair가 존재하는지 찾아보는 것입니다. 예를 들면, [1, 2, 5, 10]의 리스트에서 합이 7인 두 수가 존재하는지를 출력하는 것입니다. 이 예에서는 (2, 5)가 존재하죠?
그럼 이 문제를 어떻게 접근해서 풀 수 있을까요? 가장 간단하고 비효율적인 방법은 일일이 모든 pair를 잡아서 그 합을 계산해 보는 것입니다. 이 때 \[O\left({n \choose 2}\right)\approx O(n^2)\] 가 나오게 되서 꽤나 비효율적인 알고리즘이 됩니다. 그래도 기왕 말이 나왔으니 한번 구현해 봅시다.
def findSum_slow(L, s):
length = len(L)
# 각각의 가능한 모든 pair를 계산해보고 합과 일치하는 것이 있으면 True를 리턴
for i in range(length-1):
for j in range(i+1, length):
if L[i]+L[j]==s:
return True
return False잘 동작하는지 임의의 10개 수의 리스트를 만들어서 확인해 봅시다.
>>> import random
>>> L = [random.randint(1,50) for _ in range(10)] #1~50 사이의 임의의 수를 10개 발생시킵니다.
>>> print L
[1, 14, 6, 47, 42, 22, 7, 32, 27, 25]
>>> print findSum_slow(L, 100)
False잘 동작함을 확인할 수 있네요 :) 그럼 이제 어떻게 효율적으로 합이 S인 두 수를 찾아볼 수 있을까요? 이전에 쿠키 포장문제에서 설명드렸듯이 Sorting이라는 트릭을 활용하는 것입니다! 그럼 어떻게 sorting이 마법처럼 적용되는지 확인해 보겠습니다 :)
먼저 수의 리스트를 오름차순으로 정렬($O(n\log n)$)을 하고, 포인터를 처음과 끝에 둡니다. 두 수의 합을 구해보고 S와 같으면 바로 True를 리턴하고, 합이 S보다 크면 끝에 두었던 포인터를 하나씩 앞으로, 합이 S보다 작으면 처음에 두었던 포인터를 하나씩 뒤로 보내가면서 두 포인터가 만날때까지 검사를 합니다.($O(n)$) 결국 이 알고리즘은 \[O(n\log n)+O(n)\approx O(n\log n)\] 으로 획기적으로 효율적인 코드가 됩니다 :) 그럼 왜 이것이 가능할까요? 이것이 바로 정렬의 매력입니다. 처음과 끝에서 포인터를 놓고 시작했기 때문에, 처음에서 포인터를 뒤로 옮기는 것은 현재 합보다 다음으로 큰 합이 나오게 되고, 끝에서 포인터를 앞으로 옮기는 것은 현재 합보다 다음으로 작은 합이 나오게 됩니다!
맨 처음 예로 들었던 [1, 2, 5, 10]의 경우, 처음엔 1과 10을 이용해 11이라는 합을 만들어 비교를 하고, S보다 크게 되면 합을 줄여야 하기 때문에 포인터를 10에서 5로 옮겨서 1과 5로 합을 만듭니다. 그러면 11보다 작으면서 가장 가까운 합인 6이 나오게 되는 것입니다. 만약 6이 S보다 크면 이제는 1에서 포인터를 하나 뒤로 옮겨 2와 5로 합을 만들면 7로써, 6보다 크면서 가장 가까운 합을 얻을 수 있게 됨으로써 list를 한번만 훑어도 충분히 해가 존재하는지를 파악할 수 있는 것입니다 :)
이제 마지막으로 코드를 짜서 효율성을 비교해 봅시다 :)
def findSum_fast(L, s):
L.sort() #먼저 정렬을 시킵니다.
i, j = 0, len(L)-1 #리스트의 처음과 끝으로 포인터를 놓고,
#두 포인터가 만날때까지 계속 반복하면서
while i < j:
SUM = L[i]+L[j]
if SUM==s: #합과 같으면 True 리턴
return True
elif SUM>s: #합보다 크면 끝의 포인터를 하나 줄이고,
j -= 1
else: #합보다 작으면 처음의 포인터를 하나 올립니다.
i += 1
return False
>>> print findSum_fast(L, 100)
False앞서 만든 리스트로 결과를 확인해 보니 잘 동작하네요 :) 그럼 이제 마지막으로 효율성을 비교해 봅시다~
from time import time
>>> L = []
>>> for _ in range(100): #100개의 test case를 만들 것입니다.
>>> L.append([random.randint(1,100) for _ in range(1000)]) #각 test case는 1000개의 1~100 사이의 수를 갖고 있습니다.>>>
>>> t0 = time()
>>> for i in range(100):
>>> findSum_slow(L[i], 500)
>>> print "걸린시간 : %.2e" % (time()-t0)>>>
걸린시간 : 5.95e+00
>>> t0 = time()
>>> for i in range(100):
>>> findSum_fast(L[i], 500)
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 5.57e-02얼마 크지도 않은 리스트인데도 100배나 시간 차이가 나는 것을 확인할 수 있습니다! 무시무시하겠죠?? ^^