Computer Science/자료구조

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

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

1. 집합이란?

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


2. 배열기반 집합의 연산

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

크기가 N인 배열에서

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

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


마치며

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

 

관련 게시물

 

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

이번 포스트에서는 컴퓨터 과학에서 가장 기초적인 자료구조라고 할 수 있는 배열에 대해서 포스팅해보겠습니다. 배열에 대한 분석과 더불어 알고리즘에서 말하는 "속도" ( 시간 복잡도 ) 란 무

hy1as.tistory.com

 

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

지난 포스트에 이어 이번 포스트는 배열의 자료 구조 연산 과정을 알아보고 또 그 연산들의 계산 단계를 세어 보도록 하겠습니다. 읽기 배열에서는 특정 인덱스로 한 번에 접근해서 값을 확인할

hy1as.tistory.com