알고리즘/Python

Python: Set 자료형에 대한 정리

두넌 2023. 5. 17.

Set 자료형에 대한 특징 및 정리

백준 문제를 풀다가(바로 전 게시물) Set 자료형을 활용하면 훨씬 더 효율적으로 문제를 풀이할 수 있는 것을 보고 Set 자료형에 대한 특징과 정리를 간단히 해보려고 한다.

set은 고유한(unique) 요소들로 구성됩니다.

중복된 값을 허용하지 않으므로, 집합 연산이나 중복된 값을 제거하는 등의 작업에 유용합니다.

set은 집합 연산을 지원합니다.

교집합, 합집합, 차집합 등의 연산을 쉽게 수행할 수 있습니다. 이는 데이터의 유일성 검사, 데이터 간의 관계 파악 등에 유용합니다.

set은 내부적으로 해시 테이블을 사용하여 요소를 저장하므로, 특정 요소의 존재 여부를 빠르게 확인할 수 있습니다.

이는 많은 요소 중에서 특정 요소의 존재 여부를 빠르게 검사하는 경우에 유용합니다.

set은 가변(mutable) 자료형입니다. 따라서 요소를 추가하거나 제거할 수 있습니다.

이는 데이터의 동적인 관리나 변경이 필요한 경우에 유용합니다.

set은 해시 가능한(hashable) 자료형만 요소로 가질 수 있습니다. 따라서 불변 자료형인 숫자, 문자열, 튜플 등은 set의 요소가 될 수 있습니다. 이는 set을 딕셔너리의 키로 사용하거나 다른 set과 연산을 수행하는 등의 상황에서 유용합니다.

파이썬의 set 자료형에서 in 키워드를 사용하여 특정 요소가 집합 안에 있는지 확인하는 경우 시간복잡도는 평균적으로 O(1) 이다

set은 위에서 설명했듯 해시 테이블을 사용하여 요소를 저장하므로 요소의 해시 값을 계산하여 해당 값을 인덱스로 사용하고 요소를 저장하고 조회한다.

이러한 방식으로 인해 set 은 상수 시간에 요소의 존재 여부를 확인할 수 있다

하지만, 리스트의 경우 in 키워드를 사용하여 특정 요소의 존재 여부를 확인하는 경우 시간복잡도는 평균적으로 O(n) 이며, 리스트의 크기에 비례한 시간이 소요된다

따라서 리스트를 자주 검색해야 하는 경우 검색에 특화된 자료구조인 set이나 dict를 고려하는 것이 효율적이다