이번에 알아볼 알고리즘은 간단한 예제 문제를 통해 설명하겠습니다.
소개팅을 하고자 하는 N명의 사람들이 있습니다. N명의 사람들에게 짜장면에 대한 호감도를 정수로 표시해 달라고 했습니다. 이 때 우리는 가장 비슷한 짜장면에 대한 호감도를 가지고 있는 사람 2명을 골라서 소개팅을 시켜주려고 합니다. 이 2명의 호감도는 얼마나 가까울까요?
물론 동성끼리 만나는 불상사는 없다고 가정합시다 ^^;; 결국 이 문제는 임의의 pair에 대해서 pair간 차이의 절대값이 가장 작은 pair를 찾아 그 차이값을 출력하는 문제가 되겠습니다. 가장 직관적으로 생각할 수 있는 것은, 모든 pair에 대해서 차이를 구하고 그 minimum 값을 찾는 것입니다.
# 짜장면에 대한 호감도는 scores에 기록되어 있습니다.
def findMinDiff(scores):
mindiff = abs(scores[0]-scores[1])
for i in range(len(scores)-1):
for j in range(i+1, len(scores)):
mindiff = min(mindiff, abs(scores[i]-scores[j]))
return mindiff
>>> findMinDiff([4,9,1,32,13])
3결과는 잘 찾아내네요 ^^ 하지만 문제는 따로 있습니다. 이렇게 모든 pair를 구한다면 결국 N개 중에 순서에 상관없이 2개를 선택하는 \[O\left(N\choose{2}\right)\approx O(N^2)\] 의 complexity를 가지게 됩니다.
from time import time
import random
scores = [random.randint(1,1000) for _ in range(1000)] # 1~1000까지의 임의의 정수들을 1000개 발생시킵니다.
>>> print scores[:5] #시범적으로 처음 5개만 출력해 봅시다.
[223, 787, 858, 358, 440]
t0 = time()
>>> print findMinDiff(scores)
>>> print "걸린시간 : %.2e" % (time()-t0)
0
걸린시간 : 1.85e-01하지만 이보다 스마트한 방법이 있습니다.
방법은 이러합니다. 먼저 호감도를 정렬합니다.(여기선 오름차순으로 정렬한다고 가정할게요.) 이 정렬하는데에는 최대 의 complexity를 필요로 합니다.(여기선 일단 넘어가겠습니다.) 정렬이 된 다음에는 어떤 일이 발생할까요? 짐작하시겠지만, 나와의 거리가 멀어질수록 호감도의 차이는 단조증가 함수의 형태로 나타나게 됩니다. 따라서 가장 가까운 친구들하고의 차이만 보면 된다는 얘기죠! 이렇게 되면 결국 최소 차이를 찾는 문제는 의 complexity로 찾을 수 있게 되고, \[O(N^2) \gg O(N\log N + N)\] 의 결과에 의해 엄청난 계산적 이득을 얻을 수 있습니다! 이제 실제 결과를 확인해 보시죠.
def smart_findMinDiff(scores):
scores = sorted(scores) # 먼저 정렬을 해줍니다.
mindiff = scores[1]-scores[0]
for i in range(1, len(scores)-1):
mindiff = min(mindiff, scores[i+1]-scores[i])
return mindiff
>>> smart_findMinDiff([4,9,1,32,13])
3
t0 = time()
>>> print smart_findMinDiff(scores)
>>> print "걸린시간 : %.2e" % (time()-t0)
0
걸린시간 : 9.82e-04와… 거의 100배 가까이 빨라진 걸 확인하실 수 있죠? 이것은 N의 개수가 증가할수록 어마어마한 차이로 나타납니다 ^^