어떤 자연수들의 list A가 주어진다고 가정해 봅시다. 이 list에는 어떤 수들이 존재하는지 확인하려면 어떻게 해야 할까요? 즉, 중복되는 것들을 제외하고 distinct한 원소들은 몇 개가 있을까요?
이 문제를 풀기 위해서는 다양한 방법들이 존재할 수 있습니다. 그 중에서 가장 먼저 생각해 볼 수 있는 방법이 distinct한 원소들만을 저장하는 list를 따로 만들어서 A의 원소들을 하나씩 그 list에 속해있는지 검사하면서 없으면 그 list에 추가시켜주는 방법이 있겠습니다. 하지만 이 방법은 distinct한 원소들을 저장하는 list가 커지면 커질수록 비효율적이 되는 알고리즘입니다. 왜냐하면 그만큼 뒤져야 하는 list가 커지면 비효율적이 되기 때문이죠. 이를 코드로 구현해보면,
def distinctElem_list(A):
distinct = [] #distinct한 원소들만 간직하는 list를 만들고,
for a in A: #A의 원소들을 하나씩 돌려가면서
if a not in distinct: #distinct에 없으면 추가합니다.
distinct.append(a)
return len(distinct) #마지막으로 해당 list의 크기를 리턴합니다.잘 돌아가는지 확인하기 위해 간단하게 sample input을 만들어 보겠습니다.
>>> import random
>>> A = [random.randint(1, 5) for _ in range(10)]
>>> print A
[4, 2, 5, 2, 4, 5, 1, 4, 2, 5]위에서 distinct한 원소는 [1, 2, 4, 5]로 4가 정답이겠죠? 그럼 잘 동작하는지 바로 확인해 보겠습니다.
>>> print distinctElem_list(A)
4결과가 잘 나오네요. 그럼 성능은 어느정도 나올까요? 다음과 같이 테스트를 진행해 보겠습니다.
>>> bigA = [random.randint(1,20000) for _ in range(20000)]
>>> from time import time
>>> t0 = time()
>>> print distinctElem_list(bigA)
12668
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 2.31e+00역시나 예상했던대로 조금 무겁네요… ㅠ 그럼 조금 더 빠르게 만들 수 있는 방법은 없을까요? 네. 꾸준히 연습을 하셨으면 느끼시겠지만, sorting을 활용한 trick을 사용하는 것입니다! 정렬을 하게 되면 무조건 다음 것하고만 비교하면 되기 때문에 $O(n\log n)$의 복잡도로 bounded되겠죠? 그럼 직접 구현해보고 성능을 확인해 봅시다.
def distinctElem_list_opt(A):
count = 0
A.sort() #일단 정렬을 하구요.
now = None
for a in A: #하나씩 빼면서 이웃하고만 비교하면 됩니다.
if a != now:
count += 1
now = a
return count
>>> t0 = time()
>>> print distinctElem_list_opt(bigA)
12668
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 1.11e-02와우.. 거의 200배 차이가 나는 것을 보실 수 있죠?? 이는 $n$이 커지면서 더 심해진답니다. 하지만 우리는 여기서 만족할 수 없습니다. 오늘의 주인공인 set 자료구조를 활용하면 어떨까요? set자료구조의 특징은 중복된 값이 없다는 것과, 그렇기 때문에 disjoint set operation(union, intersection, difference 등..)에 특화되어 있다는 장점이 있습니다. 나중에 set의 진가를 활용할 날이 많이 있을것이니 일단은 굉장히 distinct한 element와 관련해서 효율적인 자료구조라는 것 정도만 알아둡시다 :) (참고: set구조는 정렬이 되어있는 구조가 아닙니다! 따라서 list처럼 넣은 순서 그대로 있지 않습니다! 정렬하시고 싶으시면 sorted함수를 사용하여 다시 list구조로 변환시키셔야 합니다!)
이제 이를 이용해서 같은 기능을 하는 코드를 짜 봅시다.
def distinctElem_set(A):
return len(set(A)) #코드는 완전 심플합니다! set에서 굉장히 편리한 constructor를 제공하기 때문이죠.
>>> t0 = time()
>>> print distinctElem_set(bigA)
12668
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 1.41e-03앞서 우리가 크게 개선한 알고리즘보다 10배 가까이 빠른것을 확인하실 수 있죠? 이렇게 강력한 기능들을 가진 built-in 자료구조들을 잘 염두해 두고 적재적소에 잘 활용하도록 합시다 :)