CS학습
Set: 중복을 허용하지 않는 데이터의 모임
Set은 순서가 없고, 중복된 원소를 포함하지 않는 자료구조이다. 멤버십 테스트, 중복 제거 등 다양한 상황에서 유용하게 활용된다. Hash Table을 기반으로 구현되어 빠른 검색 속도를 제공한다.
송민성3분 읽기
1. 개념
Set(집합)은 수학적 집합의 개념을 프로그래밍적으로 구현한 자료구조이다. 주요 특징은 다음과 같다.
- 순서 없음(Unordered): 원소의 저장 순서가 보장되지 않는다.
- 중복 없음(Unique Elements): 동일한 값을 가진 원소를 두 번 이상 저장할 수 없다.
2. 왜 사용하는가
Set은 다음과 같은 상황에서 유용하다.
- 중복 제거: 데이터에서 중복된 값을 제거해야 할 때.
- 멤버십 테스트: 특정 값이 집합에 존재하는지 빠르게 확인해야 할 때.
- 합집합, 교집합, 차집합 연산: 집합 간의 연산을 효율적으로 수행해야 할 때.
3. 동작 원리
Set은 일반적으로 Hash Table을 기반으로 구현된다. Hash Table은 Key-Value 쌍을 저장하는 자료구조로, Key를 Hash Function을 통해 Index로 변환하여 Value에 접근한다. Set에서는 원소가 Key가 되고, Value는 단순히 존재 여부를 나타내는 Placeholder(예: True)가 된다.
- 삽입(Add): 원소를 Hash Function에 넣어 Index를 계산하고, 해당 Index에 원소를 저장한다. 만약 해당 Index에 이미 다른 원소가 존재하면 Collision이 발생하며, 이를 해결하기 위한 별도의 기법(예: Separate Chaining, Open Addressing)을 사용한다.
- 삭제(Remove): 원소를 Hash Function에 넣어 Index를 계산하고, 해당 Index의 원소를 삭제한다.
- 검색(Contains): 원소를 Hash Function에 넣어 Index를 계산하고, 해당 Index의 원소가 존재하는지 확인한다.
4. 코드 예제
python
# Python Set 예제
my_set = set()
# 원소 추가
my_set.add(1)
my_set.add(2)
my_set.add(2) # 중복된 원소는 추가되지 않음
my_set.add(3)
print(my_set) # 출력: {1, 2, 3}
# 원소 삭제
my_set.remove(2)
print(my_set) # 출력: {1, 3}
# 원소 존재 여부 확인
print(1 in my_set) # 출력: True
print(2 in my_set) # 출력: False
# 집합 연산
set1 = {1, 2, 3}
set2 = {3, 4, 5}
print(set1 | set2) # 합집합: {1, 2, 3, 4, 5}
print(set1 & set2) # 교집합: {3}
print(set1 - set2) # 차집합: {1, 2}5. 시간 복잡도 또는 성능 특성
- 삽입(Add): 평균 O(1), 최악 O(n) (Collision 발생 시)
- 삭제(Remove): 평균 O(1), 최악 O(n) (Collision 발생 시)
- 검색(Contains): 평균 O(1), 최악 O(n) (Collision 발생 시)
Hash Table의 성능은 Hash Function의 품질과 Collision 해결 기법에 크게 의존한다. 좋은 Hash Function은 원소를 균등하게 분산시켜 Collision을 최소화하며, 빠른 검색 속도를 보장한다.
6. 실무 사용 사례
- 웹 애플리케이션: 사용자 세션 관리, 중복 댓글 방지, 추천 시스템 등에 활용된다.
- 데이터 분석: 데이터 정제, 중복 데이터 제거, 고유 값 추출 등에 활용된다.
- 캐싱: 자주 사용되는 데이터를 Set에 저장하여 빠르게 접근할 수 있도록 한다.
7. 주의할 점
- Set은 순서가 보장되지 않으므로, 원소의 순서가 중요한 경우에는 List나 Tuple과 같은 자료구조를 사용해야 한다.
- Hash Function의 품질이 좋지 않으면 Collision이 자주 발생하여 성능이 저하될 수 있다.
- Set은 객체를 저장할 수 있지만, 객체의 Hash Code가 올바르게 구현되어 있어야 한다.
8. 핵심 정리
Set은 중복을 허용하지 않는 데이터의 모임으로, Hash Table을 기반으로 구현되어 빠른 검색 속도를 제공한다. 중복 제거, 멤버십 테스트, 집합 연산 등 다양한 상황에서 유용하게 활용될 수 있다. Hash Function의 품질과 Collision 해결 기법이 성능에 큰 영향을 미치므로, 주의해야 한다.