배열(Array)과 집합(Set) 자료구조의 핵심 원리

자료구조는 데이터를 효율적으로 저장하고 관리하기 위한 구조입니다. 그중에서도 배열(Array)과 집합(Set)은 매우 기본적인 자료구조로 널리 사용됩니다. 이 두 자료구조의 가장 큰 차이점은 요소의 중복 허용 여부에 있습니다. 배열은 중복된 요소를 허용하는 반면, 집합은 고유한 요소만을 저장합니다.

배열(Array) 자료구조 이해하기

배열은 고정된 크기를 가지며, 동일한 자료형의 요소들을 연속된 메모리 공간에 저장하는 선형 자료구조입니다. 이러한 특성 덕분에 매우 효율적인 데이터 접근이 가능합니다.

배열의 주요 특징

고정된 크기: 배열은 생성 시점에 크기가 결정되며, 한 번 정해진 크기는 변경할 수 없습니다.
동일한 자료형: 모든 요소는 동일한 데이터 타입을 가집니다 (예: 모든 요소가 정수 또는 문자열).
연속적인 메모리 할당: 배열의 요소들은 메모리상에 순서대로 붙어있어, 첫 번째 요소의 주소만 알면 다른 모든 요소의 주소를 계산할 수 있습니다.
무작위 접근(Random Access): 인덱스(색인)를 사용하여 어떤 위치의 요소든 상수 시간(O(1)) 내에 즉시 접근할 수 있습니다.

배열 용어

배열에서 자주 사용되는 용어는 다음과 같습니다.

크기 (Size): 배열이 저장할 수 있는 최대 요소의 개수입니다. 예를 들어, 5개의 숫자를 저장할 수 있는 배열의 크기는 5입니다.
인덱스 (Index): 배열 내에서 특정 요소의 위치를 나타내는 번호입니다. 대부분의 프로그래밍 언어에서 인덱스는 0부터 시작합니다.

예시:

String[] planets = {"Mercury", "Venus", "Earth", "Mars", "Jupiter"};
// 인덱스 0: "Mercury"
// 인덱스 2: "Earth"

배열의 연산과 시간 복잡도

자료구조의 성능은 주로 시간 복잡도(Time Complexity)를 통해 측정합니다. 시간 복잡도는 입력 데이터의 크기(N)에 따라 알고리즘이 실행되는 데 걸리는 "단계 수"를 나타내며, Big O 표기법으로 표현됩니다.

읽기(Read) 연산: O(1)

배열의 특정 인덱스에 있는 요소를 읽는 작업은 항상 상수 시간(O(1))이 소요됩니다. 이는 배열의 요소들이 메모리에 연속적으로 저장되어 있기 때문에 가능합니다. 컴퓨터는 배열의 시작 주소와 요소의 인덱스를 이용해 원하는 요소의 메모리 주소를 즉시 계산할 수 있습니다. 예를 들어, 시작 주소 + (인덱스 * 요소 크기)와 같은 방식으로 특정 요소에 바로 접근합니다.

String[] items = {"Laptop", "Mouse", "Keyboard"};
String thirdItem = items[2]; // O(1) - "Keyboard"에 즉시 접근

탐색(Find) 연산: O(N)

배열에서 특정 값을 가진 요소를 찾는 연산은 최악의 경우 선형 시간(O(N))이 소요됩니다. 컴퓨터는 배열의 모든 요소를 순차적으로 확인해야만 해당 값을 찾을 수 있습니다. 원하는 요소가 배열의 마지막에 있거나 아예 존재하지 않는 경우, 모든 N개의 요소를 검사해야 합니다.

String[] products = {"Milk", "Bread", "Eggs", "Cheese"};
String target = "Eggs";
// "Eggs"를 찾기 위해 "Milk", "Bread"를 거쳐 "Eggs"에 도달 (3단계)
// 만약 "Yogurt"를 찾는다면, 모든 요소를 확인해야 함 (N단계)

삽입(Insert) 연산: O(1) 또는 O(N)

배열에 요소를 삽입하는 방법은 삽입 위치에 따라 시간 복잡도가 달라집니다.

배열의 끝에 삽입: O(1)

배열의 마지막 위치에 새 요소를 추가하는 것은 가장 효율적인 경우입니다. 배열의 크기가 허용하는 한, 단순히 비어있는 다음 위치에 값을 할당하면 되므로 상수 시간(O(1))이 소요됩니다.

int[] numbers = {10, 20, 30}; // 크기 4의 배열이라 가정, 마지막 인덱스 3이 비어있음
numbers[3] = 40; // O(1)
// 결과: {10, 20, 30, 40}

배열 중간 또는 시작 부분에 삽입: O(N)

배열의 중간이나 시작 부분에 요소를 삽입하려면, 삽입할 공간을 만들기 위해 해당 위치 이후의 모든 요소들을 한 칸씩 뒤로 밀어내야 합니다. 이 이동 작업이 입력 데이터 크기(N)에 비례하여 증가하므로, 최악의 경우 선형 시간(O(N))이 소요됩니다. 배열의 시작 부분에 삽입하는 것이 가장 많은 이동을 필요로 하는 최악의 상황입니다.

int[] data = {1, 3, 4}; // 인덱스 1에 2를 삽입하고 싶다고 가정 (가변 크기 배열 가정)
// 1. 인덱스 1 이후의 요소들 (3, 4)를 한 칸씩 뒤로 이동: (3 -> 인덱스 2), (4 -> 인덱스 3)
//    (실제 구현에서는 임시 배열 또는 메모리 이동 함수 사용)
// 2. 인덱스 1에 새 요소 삽입:
data[1] = 2; // O(N) - 요소 이동 후 삽입
// 결과: {1, 2, 3, 4}

삭제(Delete) 연산: O(N)

배열에서 특정 요소를 삭제하는 연산 또한 삽입과 유사하게 선형 시간(O(N))이 소요됩니다. 요소를 삭제하면 해당 위치에 빈 공간이 생기므로, 이 빈 공간을 채우기 위해 삭제된 요소 이후의 모든 요소들을 한 칸씩 앞으로 당겨야 합니다. 배열의 시작 요소를 삭제하는 경우, 가장 많은 요소 이동이 발생하여 최악의 시간 복잡도를 가집니다.

int[] values = {100, 200, 300, 400}; // 인덱스 1의 200을 삭제하고 싶다고 가정 (가변 크기 배열 가정)
// 1. 200 삭제 (논리적 삭제 또는 null 처리)
//    {100, _, 300, 400}
// 2. 빈 공간을 채우기 위해 300, 400을 앞으로 이동
values[1] = values[2]; // 300 이동
values[2] = values[3]; // 400 이동
// 결과: {100, 300, 400, _} (마지막 요소는 이전 값 유지 또는 초기화)

집합(Set) 자료구조 이해하기

집합은 중복을 허용하지 않는 요소들의 모음입니다. 즉, 모든 요소는 고유해야 합니다. 이미 존재하는 요소를 다시 삽입하려 하면 해당 작업은 무시됩니다. 이러한 특성 때문에 집합은 데이터의 유일성을 보장해야 할 때 매우 유용하게 사용됩니다.

본문에서는 개념적인 이해를 돕기 위해 '배열 기반의 집합'을 가정하여 설명합니다. 실제 집합 구현체는 내부적으로 해시 테이블이나 트리와 같은 다른 자료구조를 사용하여 성능을 최적화하는 경우가 많습니다.

// 집합의 예시 (개념적 표현)
Set uniqueNumbers = {1, 5, 10};
uniqueNumbers.add(5); // 5는 이미 존재하므로 추가되지 않음
uniqueNumbers.add(7); // 7은 없으므로 추가됨
// 결과: {1, 5, 7, 10} (순서는 구현체에 따라 다를 수 있음)

집합의 연산과 시간 복잡도

집합의 읽기, 탐색, 삭제 연산은 (배열 기반이라는 가정 하에) 배열과 유사한 시간 복잡도를 가집니다. 그러나 삽입 연산에서는 중복을 검사하는 과정이 추가되어 성능에 차이가 발생합니다.

읽기(Read) 연산: O(1)

배열과 마찬가지로, 특정 인덱스의 요소를 읽는 작업은 상수 시간(O(1))이 소요됩니다. 이는 내부적으로 요소들이 연속된 메모리에 저장되어 있다는 가정하에 가능합니다.

탐색(Find) 연산: O(N)

특정 값을 가진 요소를 찾는 연산 역시 배열과 동일하게 최악의 경우 선형 시간(O(N))이 소요됩니다. 모든 요소를 순차적으로 확인해야 하기 때문입니다.

삭제(Delete) 연산: O(N)

집합에서 요소를 삭제하고 빈 공간을 채우기 위해 나머지 요소들을 이동시키는 과정은 배열의 삭제 연산과 동일하게 선형 시간(O(N))이 소요됩니다.

삽입(Insert) 연산: O(N) 또는 O(2N)

집합에 요소를 삽입하는 연산은 배열과 가장 큰 차이를 보입니다. 집합은 중복을 허용하지 않으므로, 새 요소를 추가하기 전에 해당 요소가 이미 집합 내에 존재하는지 반드시 확인해야 합니다. 이 중복 검사 과정이 추가적인 비용을 발생시킵니다.

배열 기반 집합의 삽입 과정

새로 삽입하려는 요소가 집합 내에 이미 존재하는지 탐색합니다. (최악의 경우 O(N))
탐색 결과, 요소가 존재하지 않으면 실제 삽입을 진행합니다.
실제 삽입은 배열의 삽입 연산과 동일한 시간 복잡도를 가집니다. (끝에 삽입 O(1), 중간/시작에 삽입 O(N))

따라서, 배열 기반 집합의 삽입 연산은 다음과 같습니다:

집합의 끝에 삽입: N번의 중복 검사 + 1번의 삽입 = O(N+1), 즉 O(N)
집합의 중간/시작에 삽입: N번의 중복 검사 + N번의 요소 이동 + 1번의 삽입 = O(2N+1), 즉 O(N)

배열의 끝에 삽입하는 경우 1단계만 필요했던 것과 비교하면, 집합은 중복 검사 단계 때문에 항상 최소 N단계의 탐색 비용이 추가됩니다.

Java 컬렉션 프레임워크에서의 배열과 집합

Java는 다양한 자료구조를 편리하게 사용할 수 있도록 컬렉션 프레임워크(Collections Framework)를 제공합니다. 이 프레임워크는 데이터를 저장하고 조작하는 표준화된 인터페이스와 클래스들을 포함합니다.

컬렉션 프레임워크의 주요 인터페이스는 Collection과 Map입니다.

Collection: 단일 요소들을 저장하는 컬렉션의 루트 인터페이스입니다.
Map: 키(key)와 값(value)의 쌍으로 데이터를 저장하는 인터페이스입니다.

Collection 인터페이스는 다시 List, Set, Queue 등의 하위 인터페이스로 나뉩니다.

List: 요소의 순서가 유지되고 중복을 허용하는 컬렉션입니다. 배열의 특성과 가장 유사한 구현체인 ArrayList가 대표적입니다.
Set: 요소의 순서는 중요하지 않으며 중복을 허용하지 않는 컬렉션입니다. 집합의 특성을 가지며 HashSet, TreeSet 등이 있습니다.
Queue: 요소들이 특정 순서(FIFO 등)에 따라 추가되고 제거되는 컬렉션입니다.

`ArrayList` (List 인터페이스 구현)

ArrayList는 내부적으로 배열을 사용하여 데이터를 저장합니다. 따라서 배열과 유사하게 인덱스를 통한 빠른 접근(O(1))이 가능하지만, 중간 삽입/삭제 시에는 요소 이동으로 인해 성능 저하(O(N))가 발생할 수 있습니다. ArrayList는 동적으로 크기가 조절되는 배열의 구현체라고 볼 수 있습니다.

import java.util.ArrayList;

public class ListExample {
    public static void main(String[] args) {
        ArrayList<String> shoppingList = new ArrayList<>();
        shoppingList.add("사과");    // 끝에 추가 (평균 O(1))
        shoppingList.add("바나나");
        shoppingList.add(0, "오렌지"); // 시작에 추가 (O(N) - 기존 요소 이동)
        System.out.println("쇼핑 리스트: " + shoppingList); // [오렌지, 사과, 바나나]

        shoppingList.add("사과");    // 중복 허용
        System.out.println("중복 추가 후: " + shoppingList); // [오렌지, 사과, 바나나, 사과]
        
        System.out.println("두 번째 요소: " + shoppingList.get(1)); // O(1) - "사과"
    }
}

`HashSet` (Set 인터페이스 구현)

HashSet은 중복을 허용하지 않는 컬렉션입니다. 내부에 해시 테이블을 사용하여 데이터를 저장하므로, 요소의 삽입, 삭제, 탐색 연산이 평균적으로 상수 시간(O(1))에 가깝게 수행됩니다. 이는 본문에서 설명한 '배열 기반 집합'과는 다르게, 해시 함수의 효율성 덕분입니다. 그러나 최악의 경우 (해시 충돌이 심할 때) O(N)이 될 수도 있습니다.

import java.util.HashSet;

public class SetExample {
    public static void main(String[] args) {
        HashSet<String> uniqueItems = new HashSet<>();
        uniqueItems.add("펜");
        uniqueItems.add("노트");
        uniqueItems.add("지우개");
        System.out.println("고유 아이템: " + uniqueItems); // [펜, 노트, 지우개] (순서는 해시값에 따라 다름)

        boolean added = uniqueItems.add("펜"); // "펜"은 이미 존재하므로 추가되지 않음
        System.out.println("펜 추가 시도 결과 (추가됨?): " + added); // false
        System.out.println("중복 추가 후: " + uniqueItems); // [펜, 노트, 지우개] - 변화 없음
        
        System.out.println("노트 포함 여부: " + uniqueItems.contains("노트")); // true (평균 O(1))
    }
}

태그: 자료구조 배열 집합 시간복잡도 O(1)

8월 17일 08:53에 게시됨

괴물 클럽

배열(Array)과 집합(Set) 자료구조의 핵심 원리

배열(Array)과 집합(Set) 자료구조의 핵심 원리

배열(Array) 자료구조 이해하기

배열의 주요 특징

배열 용어

배열의 연산과 시간 복잡도

읽기(Read) 연산: O(1)

탐색(Find) 연산: O(N)

삽입(Insert) 연산: O(1) 또는 O(N)

배열의 끝에 삽입: O(1)

배열 중간 또는 시작 부분에 삽입: O(N)

삭제(Delete) 연산: O(N)

집합(Set) 자료구조 이해하기

집합의 연산과 시간 복잡도

읽기(Read) 연산: O(1)

탐색(Find) 연산: O(N)

삭제(Delete) 연산: O(N)

삽입(Insert) 연산: O(N) 또는 O(2N)

배열 기반 집합의 삽입 과정

Java 컬렉션 프레임워크에서의 배열과 집합

`ArrayList` (List 인터페이스 구현)

`HashSet` (Set 인터페이스 구현)

인기 태그

괴물 클럽

배열(Array)과 집합(Set) 자료구조의 핵심 원리

배열(Array)과 집합(Set) 자료구조의 핵심 원리

배열(Array) 자료구조 이해하기

배열의 주요 특징

배열 용어

배열의 연산과 시간 복잡도

읽기(Read) 연산: O(1)

탐색(Find) 연산: O(N)

삽입(Insert) 연산: O(1) 또는 O(N)

배열의 끝에 삽입: O(1)

배열 중간 또는 시작 부분에 삽입: O(N)

삭제(Delete) 연산: O(N)

집합(Set) 자료구조 이해하기

집합의 연산과 시간 복잡도

읽기(Read) 연산: O(1)

탐색(Find) 연산: O(N)

삭제(Delete) 연산: O(N)

삽입(Insert) 연산: O(N) 또는 O(2N)

배열 기반 집합의 삽입 과정

Java 컬렉션 프레임워크에서의 배열과 집합

ArrayList (List 인터페이스 구현)

HashSet (Set 인터페이스 구현)

인기 태그

`ArrayList` (List 인터페이스 구현)

`HashSet` (Set 인터페이스 구현)