[Python] '동명이인 찾기1' 알고리즘

본문은 <모두의 알고리즘 with 파이썬>(길벗, 2017)을 학습하고 개인 학습용으로 정리한 내용입니다.

 

안녕하세요, 오늘은 Python '동명이인 찾기1' 알고리즘에 대해 알아보겠습니다

---

#0. 리스트에 있는 값을 차례대로 비교하기

1. list의 0 번째 아이템을 뒤의 항목들(1, 2, 3...항목들)과 비교합니다

2. 만약에 겹치는 항목이 있으면 첫 번째 아이템은 동명이인입니다 (빈 집합에 추가)

3. 첫 번째 아이템을 뒤의 항목들(2, 3, 4...항목들)과 비교합니다

(이와 같은 과정을 list의 n-2번째 항목까지 반복합니다)
 

 

위의 내용을 함수(find_same_person)로 구현하면 아래와 같습니다

 

def find_same_person(a):
    n = len(a)
    result = set() # 빈 집합 생성
    for i in range(0, n-1):
        for j in range(i+1, n):
            if a[i] == a[j]: # 동명이인이라면
                result.add(a[i]) # result 집합에 추가
    return result

 

아래와 같이 동명이인('유재석')이 담긴 리스트를 생성하고 함수를 호출하고 리스트 값을 던져주면 유재석이 출력되는 것을 확인할 수 있습니다

 

name = ["유재석", "김태호", "조세호", "유재석"]
print(find_same_person(name))

---

# 번외.

Q. 왜 동명이인을 담을 자료형으로 일반적으로 사용되는 리스트(list)가 아니라 집합(set)을 사용했을까?

 

A.

위의 예시에서는 '유재석'이 2번 등장하였습니다. 따라서 해당 프로그램에서는 '유재석'이 한 번만 집합에 추가되었지만 만약 name 리스트에 '유재석'이 3번 이상 등장한다면 '유재석'이 2번 이상 추가될 것입니다.

따라서 리스트 자료형을 사용할 시 유재석이 2번 이상 등장하는 시각적 불편함?과 자료의 불완전성을 피하기 위해 집합자료형을 사용했다고 볼 수 있습니다.

---

오늘은 이렇게 Python에서 '동명이인 찾기(1)' 알고리즘에 대해 알아보았습니다

해당 알고리즘은 실제 프로그램에서 중복되는 값을 찾아야 될 때 등의 상황에 유용하게 사용될 것 같습니다

다음번에 또 다른 '알고리즘에 대한 내용'으로 찾아오겠습니다