[자료구조] 집합 (누구나 자료구조와 알고리즘 도서 스터디)

---

이 포스팅은 '누구나 자료구조와 알고리즘 개정2판' 을 스터디한 내용을 바탕으로 작성하는 공부기록이다.

 

집합

중복값을 허용하지 않는 자료구조

연산(배열 기반 집합)

1. 읽기 : 배열과 마찬가지로 한 단계로 끝난다.
2. 검색 : 최대 N단계
3. 삽입
   중복값을 허용하지 않는다는 제약에 의해 삽입하려는 값이 이미 있는지 검색이 우선되어야 한다.
   맨 끝에 삽입하는 경우 N+1단계가 필요하고, 최악의 경우 맨 앞에 삽입할 때 N개를 검색하고 N단계를 거쳐 데이터 이동 후 값을 삽입하는 1단계로 총 2N+1단계가 필요하다.
4. 삭제 : 최대 N단계

 

삽입의 경우 일반적인 배열보다 느리지만 중복 금지가 지켜져야 할 경우는 집합이 답이며, 이는 곧 애플리케이션의 요구사항에 따라 어떤 자료구조가 더 적합한지를 결정해야 함을 의미한다.