n개의 요소를 저장하고 O(1) 연산을 지원하는 데이터 구조란?

이번 글에서는 n개의 요소를 저장하면서도 모든 연산이 O(1), 즉 상수 시간 안에 수행되는 데이터 구조를 살펴보겠습니다. 상수 시간이란 입력 크기와 무관하게 연산에 걸리는 시간이 항상 일정하다는 의미입니다.

이 데이터 구조는 0부터 n-1까지 총 n개의 요소를 저장하며, 요소들은 어떤 순서로든 배치될 수 있습니다. 핵심은 삽입(insertion), 삭제(deletion), 탐색(searching) 세 가지 기본 연산이 모두 O(1) 시간 복잡도를 가진다는 점입니다.

이 문제를 해결하는 방법은 의외로 간단합니다. 바로 부울(Boolean) 배열을 사용하는 것입니다. 이 배열은 인덱스 i에 해당하는 요소가 현재 존재하는지 여부를 표시합니다. 요소가 존재하면 1(true), 존재하지 않으면 0(false)을 저장합니다. 배열은 인덱스로 직접 접근할 수 있으므로 임의 위치에 대한 읽기와 쓰기가 모두 상수 시간에 이루어집니다.

알고리즘

초기화 — initialization(n)

begin
   부울 배열의 모든 요소를 0으로 채운다
end

삽입 — insert(i)

begin
   인덱스 i의 요소를 1(true)로 설정한다
end

삭제 — delete(i)

begin
   인덱스 i의 요소를 0(false)으로 설정한다
end

탐색 — search(i)

begin
   위치 i의 값을 반환한다
end

예제 코드

아래는 위 알고리즘을 C++로 구현한 예제입니다.

//initialization
void init(int n) {
   bool dataStructure[n];
   for (int i = 0; i<n; i++)
      dataStructure[i] = 0;
}
//Insertion
void insert(unsigned i) {
   dataStructure[i] = 1;
}
//Deletion
void delete(unsigned i) {
   dataStructure[i] = 0;
}
//Search
bool search(unsigned i) {
   return dataStructure[i];
}

정리

부울 배열을 활용하면 삽입, 삭제, 탐색 연산을 모두 O(1) 시간에 처리할 수 있습니다. 다만 이 방식은 요소 값 자체보다 '특정 값의 존재 여부'를 빠르게 확인해야 하는 상황(예: 집합 구현, 중복 검사)에 적합하며, 실제 요소들을 순서대로 순회해야 하는 경우에는 별도의 순회 비용이 발생한다는 점을 유의해야 합니다.