13강 동명이인 찾기(Python Algorithm 13 person with the same name)

13강 동명이인 찾기(Python Algorithm 13 person with the same name)

 

부제 : 알고리즘을 배우면서 파이썬 기초부터 RPG까지 정복

내용 : 초중고 또는 코딩 기초 입문자를 위한 누구나 따라 배울 수 있는 Python Algorithm 프로그램 기초 강의

 

1. 파이썬 기초 입문자

2. 알고리즘 기초에서 수학 기초

3. 기초 코딩

4. Text RPG Project

 

[동영상강의]

https://youtu.be/kS-5v_-uBpY

Python-Algorithm-13-동명이인찾기.pdf

0.16MB

13. 동명이인 찾기(person with the same name)



n 명의 사람 이름 중에서 같은 이름을 찾아 집합으로 만들어 돌려주는 알고리즘을 구현 보도록 합시다. 



집합

동명이인찾기를 짜기 위해 집합을 배우고 들어가도록 합시다. 

수학의 집합과 비슷합니다. 

수학에서 집합은 원소들을 가지고 있죠?

예를 들면 A={1, 2, 3} 이라고 하면 이것을 A 집합이라고 합니다. 

이런식으로 나타내는 것을 원소나열법이라고 합니다. 

중괄호 표시로 하고 A 의 집합의 중괄호 안에 들어 있는 1, 2, 3 이 집합 A 의 원소라고 합니다.

수학에서 집합의 주요 특징은 다음과 같습니다. 

-  중복 불허
- 순서 없음

가령 {1, 1, 2, 3} 이런 식으로 같은 숫자 1 을 두 번 사용하지 않고 원소로 1만 들어가야 합니다. 

{1, 2} = {2, 1} 은 같은 의미입니다. 순서가 있지 않으므로 12강에서 하였던 최댓값 인덱스 값 즉 자료의 위치를 찾는 것은 집합으로 찾을 수 없습니다. 

그러기 위해서는 list 로 변환해야 하므로 이번 강의에서는 필요하지 않으므로 설명하지 않겠습니다. 

수학의 집합에서는 교집합, 합집합, 차집합 등의 종류들을 배우는데 

교집합은 두 집합이 있다면 같은 원소들을 찾아내는 것입니다. 

A = {1, 2, 3} 과 B = {2, 4, 5} 의 교집합을 구해 봅시다. 

 

A ∩ B = { 1, 2, 3  } ∩ { 2, 4, 5 } = {2} 

 

합집합은 두 집합의 원소들을 다 포함하는 것입니다. 

 

A  ∪ B = { 1, 2, 3  }  ∪ { 2, 4, 5 } = {1, 2, 3, 4, 5 } 

차집합은 중복되는 원소를 제거한 나머지를 구하면 됩니다. 

A - B = { 1, 2, 3  } - { 2, 4, 5  } = {1, 3 } 

집합 - set()

파이썬에서 집합은 list와 같이 정보를 여러 개 넣어서 보관할 수 있는 기능입니다. 

수학의 집합과 마찬가지로 집합에는 같은 자료가 중복되어 들어가지 않고, 자료의 순서도 의미가 없다는 점이 list 와 다릅니다. 

set() 을 이용해 자료를 추가하려면 add() 함수를 이용합니다. 

이외의 set() 과 관련된 함수들은 추후 다루면 하도록 하고 오늘은 그냥 add() 만 잘 배워도 됩니다. 

그리고 list와 마찬가지로 크기를 구할 때 len() 을 사용합니다. 

빈 set 을 만들어 add 를 이용해 값들을 넣어 봅시다. 

 

>>> s = set() 
>>> s.add(1) 
>>> s.add(2) 
>>> s 
{1, 2} 
>>>  

어떻습니까? 간단하죠

비어 있는 집합 자료형은 s = set() 으로 만들 수 있습니다. 

그럼 진짜로 순서와 관계없는지 확인해 보도록 합시다. 

크기도 구해보고.

 

>>> {1,2}=={2, 1} 
True 
>>>  
>>> len(s) 
2 
>>>  

True 가 나옵니다. 순서가 없다는 뜻입니다. 

원래 만들어져 있는 list 를 집합 자료형으로 나타내 봅시다. 

비록 아직까지 다른 type 으로 변환하는 것을 배우지는 않았지만 이 기회에 맛볼 수 있는 것 같습니다. 

 

>>> s = set([1,2,3]) 
>>> s 
{1, 2, 3} 
>>>  

list 로 있는 [1, 2, 3] 을 괄호로 묶어 set 으로 했더니 출력이 집합 set 형태 구조로 나오는 것을 볼 수 있습니다. 자료변환을 한 것입니다. 

문자열을 집합 자료형으로 만들어 봅시다. 

>>> s = set("hello") 
>>> s 
{'o', 'l', 'h', 'e'} 
>>> s = set("banana") 
>>> s 
{'n', 'a', 'b'} 
>>>  

l 은 중복이 되므로 한개만 나타나고 h, e, l, o 인 순서대로 안나오고 뒤죽박죽으로 나옵니다. 

banana도 마찬가지죠. 즉 set 은 순서와 관계없다는 뜻입니다. 



이제 본격적으로 알고리즘을 구현해 봅시다. 

 

name = {'Kim', 'Lee', 'Park', 'Kim'} 

- 첫번째 Kim 을 Lee, Park, Kim과 차례로 비교합니다. 
- 첫번째 Kim 과 마지막 Kim 이 같으므로 동명이인입니다. 
- 두번째 Lee 는 첫번째는 이미 비교했으므로 세번째 부터 Park, Kim 순서로 비교를 합니다. 
- 세번째 Park 을 마지막에 있는 Kim 과 비교합니다. 
- 마지막 Kim 은 모든 자료와 비교되었으므로 비교하지 않아도 됩니다. 
- 같은 이름은 Kim 입니다. 



findsamename.py

# 같은 이름 찾기 동명이인  
# 입력 : 이름이 n개 들어있는 list 
# 출력 : list에 들어있는 반복되는 이름의 집합 

def find_same_name(name_list):  
    n = len(name_list)   
    nameSet = set()             # 같은 이름을 저장할 빈 집합 
    for i in range(0, n-1):     # ① 0부터 n-2까지 반복  
        for j in range(i+1, n): # ② 자신 i 이후부터(i+1) n-1 즉 끝까지 비교  
            if name_list[i] == name_list[j]: # ③ 이름이 같으면  
                nameSet.add(name_list[i]) # ④ 찾은 이름을 nameSet에 추가 
    return nameSet    

name_list = ['Kim', 'Lee', 'Park', 'Kim'] 
print(find_same_name(name_list)) 

 

{'Kim'} 
PS C:\Users\khd>  

- n = 4
- ① range(0, 3) : 0, 1, 2 까지 반복
- i = 0
- ② range(1, 4) : 1, 2, 3 까지 반복
- j = 1
- ③ name_list[0] == name_list[1] : Kim 과 Lee 는 이름이 다름
- ② j = 2
- ③ name_list[0] == name_list[2] : Kim 과 Park 는 이름이 다름
- ② j = 3
- ③ name_list[0] == name_list[3] : Kim 과 Kim 은 이름이 같음
- ④ add(name_list[0]) : Kim을 nameSet 에 추가
- ① i = 1
- ② range(2, 4) : 2, 3 까지 반복
- j = 2
- ③ name_list[1] == name_list[2] : Lee 과 Park 는 이름이 다름
- ② j = 3
- ③ name_list[1] == name_list[3] : Lee 과 Kim 은 이름이 다름
- ① i = 2
- ② range(3, 4) : 3 만 실행
- j = 3
- ③ name_list[2] == name_list[3] : Park과 Kim 은 이름이 다름
- nameSet 반환



동명이인이 두명 되게끔도 한 번 해 봅시다. 

두 줄을 추가 합니다. 

# 같은 이름 찾기 동명이인  
# 입력 : 이름이 n개 들어있는 list 
# 출력 : list에 들어있는 반복되는 이름의 집합 

def find_same_name(name_list):  
    n = len(name_list)   
    nameSet = set()             # 같은 이름을 저장할 빈 집합 
    for i in range(0, n-1):     # ① 0부터 n-2까지 반복  
        for j in range(i+1, n): # ② 자신 i 이후부터(i+1) n-1 즉 끝까지 비교  
            if name_list[i] == name_list[j]: # ③ 이름이 같으면  
                nameSet.add(name_list[i]) # ④ 찾은 이름을 nameSet에 추가 
    return nameSet    

name_list = ['Kim', 'Lee', 'Park', 'Kim'] 
print(find_same_name(name_list)) 
name_list2 = ['Kim', 'Lee', 'Park', 'Kim', 'Lee'] # 추가 
print(find_same_name(name_list2))                 # 추가 

 

{'Kim'} 
{'Kim', 'Lee'} 
PS C:\Users\khd>  

{'Kim', 'Lee'} 은 경우에 따라 {'Lee', 'Kim'} 으로 나올 수도 있지만 집합은 순서가 없으므로  같은 경우입니다.  

다음 강의는 쉬어 가는 코너로 계산기를 여태 배운 지식으로 한번 짜보도록 합시다. 


구독 좋아요 해주세요. 큰 힘이 됩니다.