Page 30 -

1.8 집합: 단 하나의 규칙으로 효율성이 1
DATA STRUCTURES AND ALGORITHMS

달라진다 자료 구조가 중요한 까닭

또 다른 자료 구조인 집합을 파헤쳐 보자. 집합은 중복 값을 허용하지 않는 자료 구조다.

실제로 집합의 종류는 꽤 다양하지만 여기서는 배열 기반 집합을 다룬다. 배열 기반 집합은 값들의
단순 리스트로 배열과 거의 비슷하다. 배열 기반 집합과 일반적인 배열 간 유일한 차이점은 집합

은 중복 값의 삽입을 절대 허용하지 않는다는 점이다.
예를 들어 ["a", "b", "c"]라는 집합에 또 다른 "b"를 추가하려고 하면 컴퓨터는 "b"가 이미 집

합에 있으므로 삽입을 허용하지 않는다.
즉, 집합은 중복 데이터가 없어야 할 때 유용하다.

예를 들어 온라인 전화번호부를 만든다면 같은 전화번호가 두 번 나와서는 안 된다. 실은 나 역

시 현재 지역 전화번호부에서 같은 문제를 겪고 있다. 우리 집 전화번호가 내 이름뿐만 아니라
Zirkind라는 어떤 가족의 전화번호로 잘못 등록돼 있다(거짓말이 아니다). Zirkind를 찾는 사람
들한테서 오는 전화와 음성 메일이 솔직히 꽤 성가시다. 동시에 Zirkind 역시 왜 자신에게 아무
전화가 오지 않는지 궁금해하고 있으리라. Zirkind에게 전화해서 번호가 잘못됐다고 알려주면 내
아내가 전화를 받는다. 내 진짜 번호로 걸었기 때문이다(사실 이건 농담 삼아 한 거짓말이다). 전

화번호부를 만든 프로그램이 집합만 이용했다면….

어쨌든 배열 기반 집합은 중복 금지라는 제약이 하나 더 추가된 배열이다. 중복을 허용하지 않는
기능이 유용하기는 하나 이 간단한 제약으로 인해 네 주요 연산 중 하나에서 집합의 효율성이 크게
달라진다.

배열 기반 집합을 가지고 읽기와 검색, 삽입, 삭제 연산을 분석해 보자.

집합 읽기는 배열 읽기와 완전히 똑같다. 컴퓨터는 특정 인덱스에 들어 있는 값을 한 단계 만에 찾
는다. 이전에 설명한 대로 컴퓨터는 메모리 주소를 쉽게 계산해서 접근할 수 있으므로 집합 내 어
떤 인덱스든 갈 수 있다.

집합의 검색도 배열의 검색과 아무런 차이가 없다. 집합에서 어떤 값을 찾는 데 최대 N단계가 걸
린다. 삭제도 배열과 집합에서 동일하다. 값을 삭제하고 데이터를 왼쪽으로 옮겨 빈 공간을 메꾸
는 데 최대 N단계가 걸린다.

043