Python / Set()

안녕하세요!

오늘은 파이썬 set 에 대해 정리해보겠습니다 !

 

사실 지금껏 알고리즘 문제를 풀며 set()을 사용했던 경험은 별로 없는데요 ..

굳이 사용할 필요성을 못느꼈기 때문입니다 ㅎㅎㅎ ...

 

그런데 특정한 경우 set을 사용하면 연산이 빨라진다는 것을 확인했고 .. 그래서 이렇게 정리해보려고 합니다 !

 

x in s

제가 말한 특정한 경우는 x in s 연산입니다.

 

• 리스트에서 x in s 연산의 평균 시간 복잡도 : O(n)
• 세트에서 x in s 연산의 평균 시간 복잡도 : O(1)

이렇게 세트 연산에서 더욱 효율적인 이유는 무엇일까요?

 

파이썬의 set이 해시 테이블로 구현되어있기 때문입니다.

 

해시 테이블을 이해하려면 우선 해시 함수를 이해해야합니다.

해시 함수는 임의의 데이터를 인자로 받아, 특정 범위 내의 데이터로 반환하는 함수입니다. 이를 통해 반환된 데이터를 통해 해시 테이블에 데이터를 저장합니다. 해시 함수를 통해 해싱한 후 나온 결과값을 배열의 인덱스로 사용하여, 해당 위치에 데이터를 저장하는 방식입니다.

 

해시의 자세한 내용은 https://minzzl.tistory.com/56 을 참고해주세요.

 

따라서 어떤 값이 해시 테이블에 있는지 확인하려면, 해시 함수를 통해 나온 값을 이용해, 인덱스로 데이터에 접근하게 때문에 x in s 연산의 평균 시간 복잡도는 O(1)이 됩니다.

 

이와는 달리 리스트에서는 어떤 값이 리스트에 있는지 확인하려면, 리스트의 값을 일일이 확인해야합니다. 그렇기 때문에 O(N)의 연산이 걸리게됩니다.

 

그럼, set 사용법을 정리하고 이 글을 마치도록 하겠습니다.

 

해당 부분은 https://ctkim.tistory.com/entry/Python-%EC%9E%85%EB%AC%B8-%EA%B0%95%EC%A2%8C-12-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%A7%91%ED%95%A9Set-%EC%A0%95%EB%A6%AC-%EB%B0%8F-%EC%82%AC%EC%9A%A9%EB%B2%95 을 보고 작성했습니다!

 

파이썬 집합(set) 이란?

 

python 집합은 고유한 요소의 모음입니다. 집합의 목적은 단일 변수에 여러 항목을 저장하는 것입니다.

 

집합의 특징은 다음과 같습니다.

1. 순서가 없다. (인덱스로 접근하지 못한다.)
2. 중복은 허용되지 않는다.
3. 요소는 변경 불가능한 자료형만 사용할 수 있다.

 

 

파이썬에서 집합 만들기

 

1. set 함수 사용

 

집합을 만드는 첫번째 방법은 set() 함수를 이용하는 방법입니다. 이 함수는 변경 가능한 자료형(list, dictionary, string)을 집합으로 변환할 수 있습니다. 아래 코드는 리스트를 집합으로 변환하는 예시입니다.

 

>>> set_example = set([1, 2, 3, 4, 5])
>>> print(set_example)
{1, 2, 3, 4, 5}

 

2. 집합에 직접 할당

 

변수에 값을 직접 할당하여 집합을 만들 수도 있습니다. 아래 코드는 정수를 집합으로 변환하는 예시입니다.

 

>>> set_example = {1, 2, 3, 4, 5}
>>> print(set_example)
{1, 2, 3, 4, 5}

 

집합의 요소 접근

 

1. 집합의 인덱싱

 

Python에서 집합은 순서가 지정되지 않습니다. 그래서 인덱스로 접근할 수 없습니다. 인덱스로 요소에 접근하려고 하면 TypeError가 발생합니다.

 

2. 반복문을 이용한 집합 요소 접근

 

집합의 요소는 반복문을 이용하여 접근할 수 있습니다. 아래 코드는 반복문을 이용해 집합의 모든 요소에 접근하는 예시입니다. 

 

>>> set_example = {1, 2, 3, 4,5}
>>> for i in set_example:
>>> 	print(i)

 

3. in 연산자를 이용한 요소 확인

 

집합에 특정 요소가 있는지 in 연산자를 이용해서 확인할 수 있습니다. 아래 코드는 집합에 각 요소가 있는지 확인하는 코드로 값이 있다면 True를 반환하고 없다면 False값을 반환합니다.

 

>>> fruits = {"apple", "banana", "cherry"}
>>> print("apple" in fruits)
>>> print("grape" in fruits)
True
False

 

집합의 요소 추가

 

1. add() 메서드 사용

 

add() 메서드는 집합에 단일 요소를 추가하는데 사용할 수 있습니다. 아래 코드는 add() 메서드를 이용해 요소를 추가하는 예시입니다.

 

>>> set_example = {1, 2, 3, 4, 5}
>>> set_example.add(6)
>>> print(set_example)
{1, 2, 3, 4, 5, 6}

 

2. update() 메서드 사용

 

update() 메서드는 집합에 여러 요소를 추가하는 데 사용할 수 있습니다. 아래 코드는 update() 메서드를 이용해 리스트의 여러 요소를 집합에 추가하는 예시입니다.

 

>>> set_example = {1, 2, 3, 4, 5}
>>> set_example.update([6, 7, 8])
>>> print(set_example)
{1, 2, 3, 4, 5, 6, 7, 8}

 

 

집합의 요소 제거

 

1. remove() 메서드 사용

 

remove() 메서드는 집합에서 특정 요소를 제거하는데 사용할 수 있습니다. 요소가 집합에 없으면 keyError가 발생합니다. 아래 코드는 remove() 메서드를 이용해 요소를 제거하는 예시입니다.

 

>>> set_example = {1, 2, 3, 4, 5}
>>> set_example.remove(5)
>>> print(set_example)
{1, 2, 3, 4}

 

2. discard() 메서드 사용

 

discard() 메서드는 집합에서 특정 요소를 제거하는 데 사용할 수 있습니다. remove() 메소드와 달리, discard() 메소드는 요소가 세트에 존재하지 않는 경우 KeyTypeError를 발생하지 않습니다.

 

>>> set_example = {1, 2, 3, 4, 5}
>>> set_example.discard(6)
>>> print(set_example)
{1, 2, 3, 4, 5}

 

3. pop() 메서드 사용

 

pop() 메서드는 집합에서 임의의 요소를 제거하는데 사용할 수 있습니다. 아래 코드는 pop() 코드를 이용해서 임의의 요소를 제거하는 예시입니다. 이 때 맨 앞에 있는 요소가 계속해서 제거되는 것을 확인할 수 있습니다. 우리가 생각하기에 순서가 있는 것처럼 제거된다고 느낄 수 있지만 집합은 순서가 없기에 임의의 요소가 제거되는 것입니다.

 

>>> set_example = {1, 2, 3, 4, 5}
>>> set_example.pop()
>>> print(set_example)
{2, 3, 4, 5}

 

 

합집합, 교집합, 차집합, 대칭차집합

 

1. 합집합

 

두 집합의 합 집합은 두 집합의 모든 요소를 포함하는 집합입니다. 이는 union() 메서드 또는 '|' 연산자를 사용하여 수행할 수 있습니다 아래 코드는 union()을 통해 두 집합을 합치는 코드입니다. 이 때 집합은 중복된 요소가 있을 수 없기 때문에 4,5가 한개씩 있는 것을 확인 할 수 있습니다.

 

>>> set_a = {1, 2, 3, 4, 5}
>>> set_b = {4, 5, 6, 7, 8}
>>> set_c = set_a.union(set_b)
>>> print(set_c)
{1, 2, 3, 4, 5, 6, 7, 8}

>>> set_c = set_a | set_b
>>> print(set_c)
{1, 2, 3, 4, 5, 6, 7, 8}

 

2. 교집합

 

두 집합의 교집합은 두 집압에 공통인 요소만 포함하는 집합입니다. 이는 intersection() 메서드 또는 '&'연산자를 사용하여 달성할 수 있습니다.

 

>>> set_a = {1, 2, 3, 4, 5}
>>> set_b = {4, 5, 6, 7, 8}
>>> set_c = set_a.intersection(set_b)
>>> print(set_c)
{4, 5}

>>> set_c = set_a & set_b
>>> print(set_c)
{4, 5}

 

3. 차집합

 

두 집합의 차집합은 한 집합에는 있지만 다른 집합에는 없는 요소를 포함는 집합입니다. 이는 difference() 메소드 또는 `-` 연산자를 사용하여 달성할 수 있습니다.

 

 

>>> set_a = {1, 2, 3, 4, 5}
>>> set_b = {4, 5, 6, 7, 8}
>>> set_c = set_a.difference(set_b)
>>> print(set_c)
{1, 2, 3}

>>> set_c = set_a - set_b
>>> print(set_c)
{1, 2, 3}

 

4. 대칭차집합

 

두 집합의 대칭 차집합은 공통된 요소만 제외하고 모든 요소를 포함하는 집합입니다. 이는 symmetric_difference() 메서드 또는 `^` 연산자를 사용하여 달성할 수 있습니다.

 

>>> set_a = {1, 2, 3, 4, 5}
>>> set_b = {4, 5, 6, 7, 8}
>>> set_c = set_a.symmetric_difference(set_b)
>>> print(set_c)
{1, 2, 3, 6, 7, 8}

>>> set_c = set_a ^ set_b
>>> print(set_c)
{1, 2, 3, 6, 7, 8}