3. 동명이인 찾기 ①

 

* 책: 모두의 알고리즘 with 파이썬

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

• n명의 이름이 들어있는 리스트에서 같은 이름이 있는지 확인
• 같은 이름이 있을 경우 새로 만든 집합에 넣어서 return 

 

1. 선행 개념: 집합 (set)

리스트와 마찬가지로 정보를 여러개 넣어서 보관할 수 있는 파이썬 자료형

• 단, 같은 자료가 중복되서 들어가지 않으며
• 자료의 순서도 무관함: {1, 2} = {2, 1}

 

※ 자주 쓰이는 집합 기능 

 
########### len(s): 집합 s의 길이(자료 개수) ################
 
s = set() # 새 집합 만들기
len(s) # 새 집합이므로 0
len({1,2,3}) # 자료 개수가 세 개 = 3
 
 
########### s.add(x): 집합 s에 x를 추가 #####################
 
s = {1, 2, 3}
s.add(4) # {1, 2, 3, 4}
 
 
########### s.discard(x): 집합에 x가 들어있을 경우 삭제 ######
# 없으면 아무런 변화 X 
 
s.discard(5) # {1,2,3,4}
s.discard(4) # {1,2,3}
 
 
########### s.clear(): 집합 내 모든 요소 없애기 ############## 
 
s.clear() # {}
 
 
########### x in s: 집합 s에 x가 있는지 Boolean으로 확인 #####
 
4 in s # False
4 not in s # True
1 in s # True

 

 

2. 동명이인을 찾는 알고리즘

    1) 리스트 첫 번째 요소와 나머지 요소들을 비교

    2) 리스트 두 번째 요소와 첫 번째 요소를 제외한 나머지 요소들을 비교

    3) 리스트 마지막 요소는 아무와도 비교할 필요가 없음

   4) 같은 이름이 있을 경우 집합에 추가 

def find_same_name(names):
    n = len(names)
    result_set = set()
    for i in range(0, n-1):
        for j in range(i+1, n):
            if names[i] == names[j]:
                result_set.add(names[i])
 
    return result_set

 

위 코드에서 중첩 반복문이 핵심 

    1) for i in range(0, n-1): 확인하고 싶은 이름으로, 리스트의 마지막 이름은 제외

    2) for j in range(i+1, n): 비교 대상 이름으로, i보다는 항상 뒤의 이름; (리스트 길이-1)의 인덱스를 가지는 끝 이름까지 포함

 

3. 계산 복잡도? 

    두 이름이 같은지 '비교'하는 횟수를 따짐 

    결론적으로 1/2n² - 1/2n 이므로 O(n²)

      ⇒ 입력크기 n이 커질수록 제곱에 비례하여 연산 시간이 증가함 wow

 

 

<연습 문제> 

n명 중 두 명을 뽑아 짝을 짓는다고 할 때 짝을 지을 수 있는 모든 조합을 출력하는 알고리즘을 만들어보세요. 

    1) 사람 이름이 들어간 리스트 n

    2) 리스트에서 두 명씩 짝짓기

    3) 2)에서 얻은 짝 중 중복은 없애기 

    4) 조합 출력 코드 

name_lists = ['amy', 'brad', 'cindy', 'diana', 'emily', 'frank', 'gina']
 
def my_bf(names):
    n = len(names)
    pairs = set()
    for i in range(0, n-1):
        for j in range(i+1, n):
            pairs.add(str(names[i]+'-'+names[j]))
    return pairs
 
my_bf(name_lists) # n(n-1)/2 의 조합
"""'amy-brad', 'amy-cindy', 'amy-diana', 'amy-emily', 'amy-frank',"""  
""" 'amy-gina', 'brad-cindy', 'brad-diana', 'brad-emily', 'brad-frank',""" 
""" 'brad-gina', 'cindy-diana', 'cindy-emily', 'cindy-frank', 'cindy-gina',""" 
""" 'diana-emily', 'diana-frank', 'diana-gina', 'emily-frank', 'emily-gina', 'frank-gina'"""

 

# 오답노트

처음에는 아래 코드와 같이 짰더니 6쌍밖에 나오지 않음

모든 경우의 수 고려가 아닌 바로 뒤의 요소하고만 짝을 지어주었기 때문 ~_~

name_lists = ['amy', 'brad', 'cindy', 'diana', 'emily', 'frank', 'gina']
 
def my_bf(names):
    n = len(names)
    pairs = set()
    for i in range(0, n-1):
        pairs.add(str(names[i]+'-'+names[i+1]))
    return pairs
 
my_bf(name_lists) """ 'amy-brad',  'brad-cindy', 'cindy-diana', 'diana-emily', 'emily-frank', 'frank-gina'"""

 

 

ㅇ