파이썬 - 컬렉션 자료구조

시작

이전까지는 시퀀시 자료구조에 대해서 알아보았습니다.

시퀀스는 메모리에 연속적으로 존재하는 자료구조 이며,

이러한 특성 때문에 슬라이싱과 인덱싱 기능 등이 있었습니다.

 

이번에 살펴볼 컬렉션 자료구조는 오브젝트를 여러 개 가지고 있지만,

시퀀시와 달리 데이터가 메모리에 연속적으로 존재하지 않는 컬렉션 자료구조에 대해서 알아볼 것입니다.

 

컬렉션 자료구조는 데이터가 연속적으로 저장되어 있지 않기 때문에,

시퀀스에서 기본적으로 제공하던 슬라이씽 기능이 없습니다.

 

그래서 기본 기능은

컬렉션 자료구조에 성분이 존재하는지 확인하는 in,

컬렉션에 담겨있는 오브잭트의 수를 세는 len 그리고

컬렉션의 데이터를 순회하는 기능 (loop)을

가지고 있습니다.

 

파이썬에서 기본적으로 제공되는 컬렉션 자료구조는 set과 dicionary가 있습니다.

그러면 셋과 딕셔너리에 대해서 알아봅시다.

 

set과 dictionary

 

파이썬에서 set과 dictionary는 hash table을 이용하여 구현되었습니다.

hash table은 key에서 value로가는 map 혹은 함수를 이용한 데이터 구조입니다.

이러한 hash table은 key값을 이용하여 바로 데이터를 처리할 수 있습니다.

그래서 보통의 경우 O(1)의 시간복잡도를 가집니다.

하지만 hash table의 구현과 데이터의 상황에 따라 O(n)까지 늘어날 수 있습니다.

 

hash table로 구현된 둘은 무지 흡사하게 되어있습니다.

그래서 set이 dictionary의 key만 존재하는 경우라고 생각하기도 합니다.

명확하게는 아닙니다. 

set

set은 mutable 타입이며 중복요소가 없습니다. 

hash table로 구현된 set은 삽입, 제거, 탐색의 시간복잡도가 보통의 경우 O(1)이 소요됩니다.

상황에 따라 O(n)까지 시간복잡도가 올라갈 수 있지만.

코딩 문제풀이에서는 O(1)이라고 생각하고 접근해도 무방합니다.

그래서 이제부터 삽입, 제거, 탐색의 시간복잡도를  O(1)라고 생각합시다.

 

이러한 특징을 가지는 set은 자료구조에 성분이 존재하는지 확인하는 상황과 자료구조에서 중복 항목을 제거해야 하는 상황에서 유용하게 사용할 수 있습니다.

 

set자료구조와 in을 활용하면 성분의 존재 여부를 O(1)의 시간에 확인할 수 있습니다.

또한 특정한 자료구조의 성분을 set에 담으면,

중복 성분이 제거가 됩니다.

 

이 두 가지 특성을 이용항 문제들이 해쉬 유형으로 출제되고 있으니,

확실히 익혀봅시다.

set정의와 연산

셋은 set()또는 {}를 이용하여 정의할 수 있습니다.

{}의 경우 다음에 배울 dictionary와 혼용되어 사용하기 때문에,

자주 set()을 이용합니다.

{1}처럼 안에 오브잭트가 있는 경우 set으로 정의되지만,

{}으로 작성하면 dictionary로 정의되는 것을 확인할 수 있습니다.

a = set()

b = {1}

c = {}

print(type(a), type(b), type(c))

---> set, set, dictionary

1. add()

구체적인 방법

add를 이용하여 성분을 추가할 수 있습니다.

하지만 리스트와 달리 삽입 순서가 보존되지 않습니다.

a = set()

a.add(1)

a.add("hello")

print(a)

---> {"hello" , 1}

시간복잡도

리스트에서 마지막에 원소를 추가하는 append()는 O(1)의 시간복잡도를 가지고 있습니다.

하지만 set의 add의 경우 추가할 값이 이미 집합 안에 존재하는지 탐색하고,

만약 존재하지 않는다면 성분을 추가합니다. O(1)

그래서 탐색에서 보통의 경우 O(1)에서 최악의 경우 O(n)까지 올라가지만,

대부분 O(1)이라서 O(1)이라고 생각합시다.

결국 탐색에 O(1) * 성분 추가 O(1) = O(1)입니다. 

 

2. 합집합

구체적인 방법

유니온 메서드는 합집합의 복사본을 만들고 리턴합니다.

하지만 업데이트의 경우 복사본을 만들지 않고 mutable 오브젝트인 a를 수정하고 none을 리턴합니다.

a = {1, 2, 3, 4, 5}

b = {1, 2, 3, 4 ,5 ,6 ,7 ,8 ,9 ,10}

print(a.union(b))
---> {1,2,3,4,5,6,7,8,9,10}

print(a.update(b))
---> none

시간복잡도

O(len(a)+len(b))입니다.

여기서부터는 힘듭니다. 그래서 결과만 살펴봅시다.

궁금하신 분들은 cpython코드를 참고해 봅시다.

https://github.com/python/cpython/blob/main/Objects/setobject.c

4. 교집합

a = {1, 2, 3, 4, 5}

b = {1, 2, 3, 4 ,5 ,6 ,7 ,8 ,9 ,10}

print(a.intersection(b))
---> {1,2,3,4,5}

시간복잡도

평균 O(min(len(a), len(b))에서 최약의 경우 O(len(a) * len(b))까지 입니다.

궁금하신 분들은 cpython코드를 참고해 봅시다.

https://github.com/python/cpython/blob/main/Objects/setobject.c

5. 차집합

구체적인 방법

difference()는 차집합을 리턴합니다.

간단하게 a - b를 사용할 수도 있습니다.

a - b의 경우도 diffenece()와 마찬가지로 결괏값을 리턴합니다.

a = {1, 2, ,3}

b = {1, 2 }

print(a.difference(b))

---> {2, 3}

시간복잡도

O(len(a))입니다.

궁금하면 아래를 참고합시다.

https://github.com/python/cpython/blob/main/Objects/setobject.c

6. 제거

구체적인 방법

set.remove(target)는  target을 제거하고 none을 리턴합니다. 만약 target이 존재하지 않으면 에러를 발생합니다. 같은 기능을 하지만 에러를 발생하지 않는 discard()도 있습니다. set에도 list에서 쓰이는 함수인 pop()이 있습니다. set에서 pop()을 사용하면 순서가 없기 때문에 무작위로 성분을 제거하고. 제거한 성분을 리턴합니다.

a = {1,2,3,4,5}

a.pop()

---> 랜덤

a.remove(6)

---> 에러 or none

a.discard(6)

---> none

시간복잡도

해쉬 테이블로 구현되어 있어.

O(1)이라고 생각하면 됩니다.

문제

찾아보자. 

dictionary

dictionary는 hash table을 이용하여 구현되었습니다.

hash table은 고유한 key와 이에 대응되는 value를 가지고 있는 자료구조입니다.

그렇기에 dictionary도 고유한 key와 value를 가지고 있습니다.

저번에 공부한 set은 dictionary에 key만 존재하고 value가 없는 자료구조로 생각할 수 있습니다.

set에서 삽입, 삭제, 탐색이 보통의 경우 시간복잡도가 O(1)이였습니다.

dictionary도 set과 마찬가지로 key를 삽입, 삭제, 탐색이 O(1)의 시간복잡도를 가집니다.

 

hash table로 구현된 dictionary는 리스트 처럼 순서가 없었습니다.

그래서 슬라이싱 기능을 사용할 수 없습니다.

하지만 파이썬 3.7 버전부터 삽입 순서가 보존되어 loop를 통해 탐색할때.

삽입순으로 탐색이 됩니다.

이거 진짜 편합니다. 꼭 기억합시다!

dictionary정의와 연산

dictionary는 {}를 이용하여 정의합니다.

dictionary의 성분인 key와 value는 :을 통해 구분합니다.

key의 경우 변하지 않고 유일해야합니다.

그래서 중복되지 않는 Immutable타입이 사용됩니다.

Immutable타입은 메모리에서 변경이 불가능한 타입을 말합니다.

예를들면 과거에 공부했던 string, int, float, tuple등이 포함됩니다.

만약 list와 같은 mutable타입을 dictionay의 key로 사용하려 한다면,

오류를 발생합니다. 

a = {}

dic = {1:2, "1":2, (1,2) : [1,2,3,4] }

print(dic[(1,2)]

---> [1, 2, 3, 4]

 

1.setdefault()

dictionary 자료구조에서 key를 이용하여 value에 접근할 때.

dictionary[key] 문법을 이용합니다.

만약 dictionary 자료구조안에 key가 존재하지 않는다면.

오류가 발생합니다.

이러한 상황에서 key가 없다면 기본값으로 설정을 하고.

만약 존재한다면 val값을 가져올수 있는 함수가 setdefault()입니다.

 

setdefault()함수는 빈 딕셔너리부터 시작을해서 추가하며 사용할 수 있다는 점에서.

list의 append()와 비슷합니다.

dic = {}

dic[1] = 3

---> 에러

dic.setdefault(1, 3)

---> 3

2.update()

dictionary_1.update({key : val })는 dictionary_1의 key의 값을 val로 수정합니다.

만약 key가 dictionary_1에 존재하지 않는다면.

새롭게 추가합니다. 

dic = {1:2}

dic.update({1:3})

print(dic)

---> {1:3}

dic.update({2:4})

print(dic)

---> {1:3, 2:4}

3.popitems(), pop()

dictionary의 아이템을 제거할 떄는 리스트와 동일하게 pop()을 사용할 수 있습니다.

리스트의 경우 pop()의 파라매터가 위치를 나타내는 index였지만.

dictionary는 key입니다. 

 

dictionary에는 리스트의 pop(0)처럼 사용할수 있는 popitem()가 있습니다.

파이썬 버전 3.7이후부터 dictionary는 삽입 순서가 위지가 됩니다.

그래서 dictionary에 popitem()를 사용하면.

마지막에 추가된 원소가 dictionary에서 삭제되고 리턴이 됩니다.

dic = {1:1, 6:2}

dic.pop(6)

print(dic)

---> {1:1}

dic = {}

for i in range(10):
    dic.setdefault(i, i)

print(dic)

--->	{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9}

for _ in range(10):
  print(dic.popitem())
  
--->	(9, 9)
	(8, 8)
	(7, 7)
	(6, 6)
	(5, 5)
	(4, 4)
	(3, 3)
	(2, 2)
	(1, 1)
	(0, 0)

4. 한줄로 dicitionary 정의 하기, 컴프리헨션

구체적인 방법

for문을 이용하여 사용할 dictionary를 초기화 하는 경우가 많습니다.

이를 깔끔하게 한줄로 작성하게 도움을 주는 문법이 컴프리헨션입니다.

처음 접한다면 새로운 문법에 대한 거부감이 있을 수 있지만. 

진짜 편하고 많이 사용합니다.

dic = { str(element) : element for element in range(10) }

print(dic)

---> {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}

dic = { str(element) : element for element in range(10) if element % 2 == 0 }

print(dic)


---> {'0': 0, '2': 2, '4': 4, '6': 6, '8': 8}

이런식으로 for와 {}를 이용하여 dic를 만들수 있습니다..

뒤에 if를 추가하면 조건에 부합하는 것들만 첨가됩니다.

 

시간복잡도

for loop와 마찬가지로 O(n)입니다. 

여기서 n은 in 뒤에 iterable이라 불리는 반복 가능한 객체의 길이입니다.

5. dictionary loop사용법

dictionary의 메서드인 items(), keys(), values()를 이용하면.

for loop에 사용할 수 있습니다.

items()는 한번에 key와 value를 리턴하고.

keys()는 한번에 key만 리턴하고.

values()는 한번에 value를 리턴합니다.

dic = { str(element) : element for element in range(10) if element % 2 == 0 }

for key, val in dic.items():
	print(key, val)
    
for key in dic.keys():
	print(key)
    
for val in dic.values():
	print(val)

 

시간복잡도

O(n)입니다. 

여기서 n은 dictionary의 성분수 입니다.

 

문제

https://programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

코딩테스트 연습

문제는 대략 이렇습니다.

마라톤에 참가자중 단 1명만 완주를 하지 못합니다.

이때 미완주자 1명을 리턴하는 문제입니다.

인풋은 참가자 명단과 완주자 명단입니다.

참가자 명단의 크기가 10만 이하이기 떄문에.

10만명이라 생각하고 문제를 풀어야 합니다.

인풋이 10만명일때는 O(nlogn)이하의 알고리즘을 작성해야,

통과할 수 있습니다.

먼저 코드를 작성하지 말고.

어찌하면 O(nlogn)이하로 미완주자를 리턴할 수 있을지,

설계를 하고 코드를 작성해 봅시다.

 

구라코드 

이문제를 해결하기 위해서는 어떻게 해야 할까요?

참가자 명단을 정리하고.

완주자 명단을 loop를 돌며 참가자 명단에서 제외하고.

남는 사람을 리턴하면 됩니다.

 

리스트를 이용하여 위의 생각을 구현하면 어떻게 될까요?

만약 리스트로 작성한다면.

완주자를 참가자 명단에서 제외하는 부분에서 많은 시간 복잡도를 잡아 먹을 것입니다.

리스트는 성분을 제거하는데 경우 O(1) ~ O(n)가 사용되기 떄문에.

이 부분을 해결하기 위해 O(n) * O(k) = O(nk)가 사용되어 시간초과 판정을 받습니다.

 

이를 좀더 효율적으로 변형하기 위해서 list에 sort()를 사용한다고 가정해 봅시다.

먼저 참가자 명단과, 완주자 명단을 sort()합니다.

그리고 완주자 명단을 뒤에서 부터 탐색합니다.

만약 맨뒤에 성분이 완주자와 같다면 pop()하고 아니면 remove()를 통해 제거합니다.

요런 식으로 하면 정렬하는데 O(nlogn)

탐색하는데 O(n)

운이 좋으면 O(1), 나쁘면 O(k)입니다.

그래서 O(nklogn)이됩니다.

 

리스트를 이용하는 다른 솔루션이 있을수 있습니다.

하지만 이쯤되면.

다른 데이터 구조를 생각해 보는 것이 좋습니다.

dictionary를 이용하는 솔루션을 생각해 봅시다.

먼저 딕셔너리를 {참가자 : 0}로 초기화 합니다.

참가자를 돌며 dic[참가자] += 1을 진행합니다.

같은 이름이 있는 사람들은 숫자로 표시됩니다.

이렇게 정리된 참가자 데이터에서 완주자 명단을 순회하며.

dic[완주자] -= 1을 진행합니다.

1명을 제외하고 모두 완주하였기 떄문에.

정리된 참가자 데이터 dic의 1개의 value값이 1이고 나머지는 모두 0이 됩니다.

여기서 value가 1인 값을 리턴합니다.

 

요런식으로 하면 참가자를 정리하는데 O(n)

완료자 순화하며를 제거하는데 O(n)

1을 찾아서 리턴하는데 O(n)

이되어 O(3n) = O(n)입니다.

 

그러면 이 구라코드를 이용하여 작성해 봅시다.

만약 O(nlogn)이하인 구라코드를 못찾는다면,

코드 작성을 시작할 필요도 없습니다.

def solution(participant, completion):
    dic = {p : 0 for p in participant}
    for p in participant:
        dic[p] += 1
    for p in completion:
        dic[p] -= 1
    for key, val in dic.items():
        if val == 1:
            return key

이전 글 - 파이썬 시퀀스

다음 글 - 파이썬 스택과 큐