파이썬 리스트 알고리즘 동명이인을 찾아라!! #4

파이썬 리스트 알고리즘 동명이인을 찾아라!! #4

 

안녕하세요.

 

파이썬으로 공부하는 알고리즘!!

 

오늘은 N명의 사함 이름 가운데서 같은 이름을 찾아 집합으로 만들어 보는 알고리즘을 공부하겠습니다.

 

예를 들어서 이름이 들어있는 리스트(전시간에 공부했었죠? ㅎㅎ) 에서 동명이인을 찾아 그 이름이 들어 있는 집합을 만드는것 입니다.

 

그럼 문제로 들어가기전에 집합에 대해서 한번 공부를 좀 해볼께요.

자 그림을 보면 s 라는 집합을 선언했습니다.

2번 라인에서 1을 add 했구요.

3번 라인에서 2를 add 합니다.

4번 라인에서 또 2를 add 했습니다.

 

결과는?

 

1,2 두개만 들어있네요!

 

네, 집합에서는 같은 수가 들어가지 않습니다.

 

결국 4번 라인에서 add 한 2는 집합으로 들어가지 못한게 되었네요.

 

자, 위에서 만든 s 집합에 자료가 몇개 있는지 len으로 확인하니 2개가 나왔습니다.

 

집합에서는 순서는 상관없습니다.

 

위 그림의 8번 라인을 보면 알 수 있겠죠?

 

집합과 관련된 기능을 좀 살펴 보겠습니다.

 

len 은 위에서 나왔습니다.

 

그리고 add 역시 위에 예시가 있습니다.

 

 

집합안의 자료를 삭제하는 discard가 있습니다. 

 

그리고 리스트에도 있는 clear 와 x in s 기능이 있습니다.

 

위 그림을 보시고 사용 예시를 확인 할 수 있습니다.

 

이젠 우리는 set (집합)을 어느정도 컨트롤 할 수 있습니다.

 

자, 문제를 시작해 보겠습니다.

 

1. 아래 그림처럼 처음 박지성을 뒤에 있는 차두리, 김남일, 박지성과 차례로 비교합니다.

 

2. 첫번째 박지성은 마지막 박지성과 같은 데이터 이므로 동명이인임이 확인 되었습니다. (중복으로 저장)

 

3. 처음 박지성을 빼고, 나머지를 같은 방법으로 비교 합니다. 중복이 없습니다.

4. 차두리를 빼고 나머지를 비교 합니다. 중복이 없습니다.

5. 마지막 박지성은 비교하지 않아도 됩니다.

 

이 알고리즘에서는 주의 할 점이 몇가지 있는데,

 

비교할 이름을 뽑은 다음에 그 보다 앞에 있는 데이터와는 비교하지 않아도 된다는점! 그리고 마지막 순번의 이름은 비교하지 않아도 된다는 것 입니다.

 

그리고 중간에 중복된 이름을 찾으면 그 결과를 집합에 추가해 주면 됩니다.

 

자, 여러분들 코딩을 해볼까요??

 

def find_same_name(a):
    n = len(a)   # 리스트의 자료 개수를 n에 저장
    samename = set()  # 결과를 저장할 빈 집합
    for i in range(0, n - 1):      # 0부터 n-2까지 반복
        for j in range(i + 1, n):  # i+1부터 n-1까지 반복
            if a[i] == a[j]:       # 이름이 같다면?
                samename.add(a[i])   # 찾은 이름을 result에 추가
    return samename

name = ["박지성", "차두리", "김남일", "박지성"]  
print(find_same_name(name))

name2 = ["박지성", "차두리", "김남일", "박지성"]
print(find_same_name(name2))

이젠 이 알고리즘을 분석해 보겠습니다.

 

우선 계산 복잡도를 생각해 보겠습니다.

 

위치	이름	비교 횟수	비교 대상
0	박지성	3	차두리,김남일,박지성
1	차두리	2	김남일,박지성
2	김남일	1	박지성
3	박지성	0	X

우리가 만든 알고리즘은 위의 표와 같이 계산을 한 결과 총 6번의 비교를 하게 됩니다.

 

하지만 지금처럼 4명의 이름으로 비교를 하는게 아니라 40명, 400명, 1천명의 이름을 비교 해야 한다면 어떨까요?

 

비교해야 하는 대상의 수를 N 이라고 한다면 이 알고리즘은..

 

1/2*(N의제곱) 만큼 계산을 해야 합니다.

 

그래서 이 알고리즘의 계산 복잡도는 O(n의제곱) 이라고 표기 합니다.

 

이 알고리즘은 입력 크키가 많아질수록 기하급수적으로 계산의 횟수가 증가 할 수 있습니다.

 

썩 좋은 알고리즘이 아닌것 이죠.

 

여러분들 머리속엔 이 알고리즘 대신 사용 할 수 있는 동명이인 찾기 알고리즘이 있을까요? ^^

 

저도 고민해 보겠습니다.

 

여러분들도 함께 고민해주시면 고맙겠습니다.

 

부족한 글 읽어주셔서 감사합니다.

 

오늘은 여기 까지 입니다.

 

 

 

by.sTricky