배열 - 가장 기초적인 자료구조 ( 3 )

배열 시리즈의 마지막 포스트입니다.
이번 포스트에서는 배열 자료구조에 제약사항 한 가지를 더한 집합이라는 자료구조에 대해서 알아보며 특정 조건으로 인해 달라지는 연산의 효율성에 대해서 이야기해보겠습니다.

---

1. 집합이란?

집합이란 꽤 친숙하고 실생활에 밀접해있는 단어인데요. 중복값을 허용하지 않는 자료구조를 뜻합니다.컴퓨터 과학에서 여러 가지 형태로 집합을 구현하고 있지만 여기서는 배열을 기반으로 한 집합을 이야기해보겠습니다.

---

2. 배열기반 집합의 연산

배열 기반 집합의 연산 중 읽기, 검색, 삭제 의 경우 일반 배열 자료 구조와 동일한 단계를 가집니다. 하지만 삽입의 경우 원소가 중복되지 않아야 한다는 집합의 제약사항으로 인해 별도의 단계가 발생합니다. 삽입하려는 원소가 배열 내에 존재하지 않아야 하기에 선형 검색 ( 전체 순환 )이 1회 이루어지게 됩니다.

크기가 N인 배열에서

• 가장 뒤에 삽입하려는 경우 전체 검색 ( N단계 ) + 삽입 ( 1단계 )로 N + 1 단계로 연산
• 최악의 시나리오인 가장 앞에 삽입하는 경우 전체 검색 ( N단계 ) + 기존에 위치한 원소들의 이동 ( N단계 ) + 삽입 ( 1단계 ) 로 총 2N + 1단계를 통해 연산

이를 통해 동일한 형태의 자료구조 일지라도 제약사항 등의 특정 조건이 존재할 때에는 연산의 효율성이 달라질 수 있다는 것을 알 수 있습니다.

---

마치며

 이번 포스트에서는 동일한 자료구조에서 특정 조건이 주어졌을 때 효율성이 어떻게 변하는지를 살펴보았습니다.
오늘 설명을 보시고 "그러면 단점만 존재하는 집합을 왜 사용하느냐?" 하는 생각이 드실 수 있습니다.
집합은 삽입 시 비용은 높지만 원소의 무결성을 보장해 줍니다. 이는 원소가 단 하나만 존재해야 하는 경우 삽입 후에 별도의 추가 검증 작업이 필요 없다는 것을 의미하는데요. 때문에 집합 자료구조는 원소의 Unique가 보장되어야 하고 삽입보다 읽기 작업이 많이 발생하는 상황에서 더 효율적으로 쓰일 수 있습니다.
이 포스트로 배열 자료구조에 관한 포스팅 시리즈를 마치겠습니다.
감사합니다.

 

관련 게시물

배열 - 가장 기초적인 자료구조 ( 1 )

배열 - 가장 기초적인 자료구조 ( 2 )