파이썬 딕셔너리 알고리즘 동명이인 찾기 2 #12

파이썬 딕셔너리 알고리즘 동명이인 찾기 2 #12

 

안녕하세요.

 

파이썬으로 공부하는 알고리즘 12번째 시간입니다.

 

이번 시간에는 지난 알고리즘 네 번째 시간에 다루었던 동명이인 찾기 2탄!! 을 준비했습니다. 지난 시간의 알고리즘은 나열되어 있는 리스트 안에 값은 값이 두 개 이상 있는지 확인해서 돌려주는 문제였습니다.

 

예를 들어서, ["박지성", "차두리", "김남일", "박지성"]이라는 리스트가 있다면, 이 리스트 안에서 중복된 데이터 "박지성"을 찾아서 결과로 리턴해주는 형태였습니다.

 

이번 시간에도 똑같이 풀면 안 되겠죠? 이번에는 파이썬의 딕셔너리(dictionary)라는 자료 구조를 이용해서 동명이인을 찾아보는 알고리즘입니다. 우선 딕셔너리가 무엇이지 알아볼게요!

 

1. 딕셔너리란 무엇인가?

파이썬에 있는 딕셔너리의 자료 구조는, 키와 값으로 구성되어 있습니다. 키와 값의 대응 관계가 저장이 되어 있는데요. 예를 들어 딕셔너리 안에 사람들의 이름(키)과 나이(값)가 함께 매칭 되어 저장되어 있는 것이라 생각하시면 이해하기 편하실 것 같습니다.

 

2. 딕셔너리를 만드는 방법

d = {"Justin" : 13, "John" : 10, "Mike" : 9}

이렇게 만드시면 d라는 딕셔너리가 만들어진 것입니다.

위 내용을 잠깐! 설명해 보자면, Justin이라는 키에 값이 13이라는 뜻입니다. John과 Mike도 각 각 10, 9의 값을 가진 키가 되는 것입니다.

 

아무것도 들어있지 않은 빈 딕셔너리를 만드는 방법도 알아보겠습니다.

d = {}
d = dict()

위와 같이 두 가지 방법으로 빈 딕셔너리를 만들 수 있습니다.

 

키만 입력한다던지, 값만 입력해서 딕셔너리를 생성할 수 없습니다.

 

3. 딕셔너리에 새 값을 추가하는 방법

d["Summer"] = 1

위와 같은 명령으로 딕셔너리에 새로운 값을 추가할 수 있습니다.

 

4. 딕셔너리에 여러 값을 추가하는 방법

n_info = {
	1 : "대한민국",
    2 : "필리핀",
    3 : "미국"
}

위와 같은 명령으로 여러 개의 값을 딕셔너리에 추가할 수 있습니다.

 

여기에 하나의 국가 값을 더 추가하려면 어떻게 해야 할까요?

n_info[4] = "영국"

이렇게 추가하면 됩니다.

 

여기서는 1,2,3,4 가 키가 되고, 대한민국, 필리핀, 미국, 영국이 값이 되는 거 겠죠.

 

5. 딕셔너리 명령어들!

딕셔너리에는 위와 같은 명령어들이 있습니다.

 

6. 딕셔너리 장점

딕셔너리는 긴 if-elif 문장을 간단하게 만들어주는 장점이 있습니다. 예를 들어 아래와 같은 코드가 있다고 합니다.

이런 문장을 아래와 같이 간결하게 만들 수 있습니다.

 

이젠 딕셔너리를 이용해서 동명이인을 찾아볼까요?

우선 아래 코드를 먼저 보겠습니다.

dictionary =
{
	"이름 1" : 이름 1이 등장한 횟수,
    "이름 2" : 이름 2이 등장한 횟수,
    "이름 3" : 이름 3이 등장한 횟수
}

앞서 예를 들었던 ["박지성", "차두리", "김남일", "박지성"]을 위의 코드를 이용해서 처리해 보겠습니다.

name_dic =
{
	"박지성" : 2,
    "차두리" : 1,
    "김남일" : 1
}

그럼 이 딕셔너리에서 값이 2 이상인 키를 출력하면 이름이 두 번 나온 동명이인을 찾을 수 있겠죠?

 

간단합니다.

 

이 알고리즘을 순서대로 정리를 해보겠습니다.

 

1. 이름과 등장 횟수를 저장할 비어있는 딕셔너리를 만든다.

2. 리스트에서 하나씩 꺼내서 딕셔너리에 입력한다.

3. 이때 이름이 딕셔너리에 존재하는지 확인한다.

4. 이미 존재하는 이름이라면 값을 1 증가시킨다.

5. 없다면, 딕셔너리에 이름을 값 1과 함께 입력한다.

6. 리스트에 더 이상 이름이 없을 때까지 1~5번 과정을 반복한다.

7. 마지막으로, 딕셔너리에서 값이 2 이상인 키를 꺼내어 출력한다.

 

이렇게 구현할 수 있겠습니다. 그럼 소스로 만들어 보겠습니다.

# 두 번 이상 나온 이름 찾기
# 입력: 이름이 n개 들어 있는 리스트
# 출력: n개의 이름 중 반복되는 이름의 집합

def find_same_name(a):
    # 1단계: 각 이름의 등장 횟수를 딕셔너리로 만듦
    name_dict = {}
    for name in a:  # 리스트 a에 있는 자료들을 차례로 반복
        if name in name_dict:     # 이름이 name_dict에 있으면
            name_dict[name] += 1  # 등장 횟수를 1 증가
        else:                     # 새 이름이면
            name_dict[name] = 1   # 등장 횟수를 1로 저장

    # 2단계: 만들어진 딕셔너리에서 등장 횟수가 2 이상인 것을 결과에 추가
    result = set()  # 결괏값을 저장할 빈 집합
    for name in name_dict:  # 딕셔너리 name_dict에 있는 자료들을 차례로 반복
        if name_dict[name] >= 2:
            result.add(name)

    return result

name = ["Tom", "Jerry", "Mike", "Tom"]  # 대소문자 유의: 파이썬은 대소문자를 구분함
print(find_same_name(name))

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

##알고리즘 분석##

이전에 [파이썬_알고리즘] 4편에서 다루었던 동명이인 찾기의 계산 복잡도는 O(n²)이었습니다. 반면 이번 시간에 다루는 딕셔너리를 이용해 동명이인을 찾는 알고리즘은 O(n)이 됩니다. 프로그램에서는 for문이 얼마나 나오는지, 겹치는 건지 아닌지에 따라 계산 복잡도가 많은 차이를 보입니다.

 

[파이썬_알고리즘] 동명이인을 찾아라!! #4 편 보러 가기

2020/01/31 - [DB엔지니어가 공부하는 python] - [파이썬_알고리즘] 동명이인을 찾아라!! #4

[파이썬_알고리즘] 동명이인을 찾아라!! #4

 

어떠셨나요? 더욱 간결해진 계산 복잡도를 가진 딕셔너리 동명이인을 찾아라 였습니다.

다음 편에 다시 돌아오겠습니다.

 

감사합니다.

 

# 파이썬으로 배우는 알고리즘 컨텐츠는 <모두의파이썬X알고리즘, 길벗>을 참고로 작성하는 포스팅 입니다. 물론 협찬은 없습니다.ㅎㅎ

https://book.naver.com/bookdb/book_detail.nhn?bid=14341699

 

by.sTricky