모두의 알고리즘 문제 03. 동명이인 찾기 1

def find_same_name (a):
    n=len(a)  #리스트a의 길이 저장
    result=set() #결과 저장할 빈 집합 생성
    for i in range (0, n-1):  #비교 기준을 선정하는 반복문
        for j in range (i+1, n):  #비교 대상을 선정하는 반복문, i+1이 아니라 1을 사용하면 첫 바퀴는 괜찮지만-
            if a[i]==a[j] :       #다음바퀴에 비교 기준이 넘어가도 비교 대상은 첫바퀴와 동일하므로 원하는 결과가 나오지 않는다.
                result.add(a[i]) # 중복된 이름이 나오면 집합에 추가한다.
    return result

name=["Tom", "Jerry", "Mike", "Tom"]
print(find_same_name(name))

name2=["Tom", "Jerry", "Mike", "Tom", "Mike"]
print(find_same_name(name2))

상술한 프로그램은 리스트의 동명이인을 찾아서 동명이인의 이름을 result집합에 넣는 프로그램이다.

 

이 프로그램의 시간복잡도를 분석해보자. 같은 이름을 찾는 알고리즘이므로 두 이름이 같은지 비교하는 횟수를 따져보면 된다. 리스트 길이가 4일 때, 즉 n=4일 때의 비교 횟수를 보자.

 

일단 마지막 위치의 이름은 비교 기준으로 잡을 필요가 없다. 그 원소가 비교 기준이 됐을 때는 비교 대상도 없고 그 전에 충분히 비교됐기 때문이다. 결국 전체 비교 횟수는 0+1+2+3+....+(n-1)이 되는데 이를 1부터 n까지의 합을 구하는 공식에 대입하면 (n-1)(n-1+1)/2 = n(n-1)/2 = 1/2n^2 - 1/2n 번 비교해야 한다는 것을 알 수 있다.

 

1/2n^2 - 1/2n 은 빅 오 표기법으로는 O(n^2)으로 표현한다. n의 제곱에 비례해서 계산시간이 변하는 것이 핵심이기에 n^2 앞의 계수 1/2이나 -1/2n은 무시하고 O(n^2)으로 표현한다.