# set

파이썬의 set에 개념에 대해 조금 정리해두고자 이 게시글을 작성합니다. set의 개념정리에 앞서 해시테이블이라는 것에 대해 먼저 정리가 필요합니다.

 

해시테이블

해시테이블은 두 가지 의미가 내포되어 있습니다. 첫번째는 키와 값으로 이루어진 자료구조를 의미하고 두번째는 해쉬를 통해서 값을 접근하는 형태의 구조를 의미합니다. 키와 값으로 이루어진 자료구조는 흔히 객체라고 말하는 파이썬에선 딕셔너리를 의미합니다. 본글과는 상관없기에 다루지는 않고 넘어가겠습니다.

 

해시를 통해서 접근하는 형태의 구조라는 단어를 듣고 처음에는 이해가 가지 않았으나 천천히 읽고 확인해보니 대충 납득되었습니다. 

 

set

lst = [1, 1, 2, 3]
st = set(lst)

print('list: ', lst)
print('set: ' , st)

list와 set이 다음과 같이 있다 가정하고 찍어보면 lst 변수의 중복된 값이 제거된 채로 st의 변수에 참조되는 것을 확인할 수 있습니다. set의 내장 모듈에서 해시를 이용해 해시값에 대한 위치를 찾고, 값 비교까지 더해 같으면 저장하지 않는 로직이 있기 때문입니다.

 

따라서 위와 같은 상황에서 1은 중복된 해시값으로 검증해 그 값을 제거한 나머지 값들을 set으로 보여지게 되는 것입니다. 다만, 기본적인 형태는 그렇습니다만 내장 모듈을 커스텀하였다면 올바르게 동작하지 않을 수 있습니다.

 

이런 식으로 set 내장모듈로는 다음과 같이 존재합니다. 근데 set은 어떨 때 쓰는지 문득 궁금하게 되었습니다.

 

단순히 처음 파이썬을 공부할 때는 중복된 값을 제거한다 정도로만 이해했으나 그와 더불어서 더 많은 이유가 있음을 알게 되었습니다. list에서 포함여부를 검사하는 것은 O(n)이라는 시간 복잡도를 가지지만 set에서는 O(1)이라는 시간 복잡도를 가지기에 연산 속도의 차이가 존재하게 됩니다. 그 외에 집합 연산이라던가, 코딩 테스트에서는 그래프의 알고리즘에서 활용되어지는 것으로 확인하였습니다.