순차 자료구조

작성자

익명

작성일

2026.07.12

조회수

버전

순차 자료구조 배열 시간 복잡도 동적 배열 시프팅 공간 지역성 원형 큐 데이터구조 초급

순차 자료구조 (Sequential Data Structure)

1. 개요

순차 자료구조란 데이터가 메모리 상에 물리적으로 연속적인 공간에 저장되는 선형 자료구조를 의미합니다. 데이터의 논리적인 순서와 물리적인 저장 순서가 일치하는 것이 특징이며, 가장 대표적인 형태로 배열(Array)이 있습니다.

2. 주요 특징 및 작동 원리

2.1 직접 접근 (Direct Access)

순차 자료구조의 가장 큰 특징은 인덱스(Index)를 통한 직접 접근이 가능하다는 점입니다. 인덱스란 데이터 요소의 위치를 나타내는 정수 값으로, 메모리 주소 계산식(시작 주소 + (인덱스 * 데이터 크기))을 통해 원하는 요소의 위치를 즉시 찾아낼 수 있습니다.

2.2 데이터 이동 (Shifting)

데이터의 삽입이나 삭제가 발생할 때, 물리적 연속성을 유지하기 위해 기존 데이터들을 옆으로 밀어내는 시프팅(Shifting) 과정이 필요합니다.

[데이터 삽입 시 시프팅 과정 예시] 인덱스 1번 위치에 새로운 값 'X'를 삽입하려는 경우:

초기 상태: [ A ] [ B ] [ C ] [ D ] [ E ]
             0     1     2     3     4  (인덱스)

1단계(이동): [ A ] [ B ] [ B ] [ C ] [ D ]
             0     1     2     3     4  (인덱스)
                     ↑     ↑     ↑
                  (B이동) (C이동) (D이동)

2단계(삽입): [ A ] [ X ] [ B ] [ C ] [ D ]
             0     1     2     3     4  (인덱스)

2.3 논리적 순서와 물리적 저장 순서 비교

구분	논리적 순서 (Logical Order)	물리적 저장 순서 (Physical Order)	일치 여부
순차 자료구조	데이터가 나열된 순서	메모리 주소가 연속된 순서	일치
연결 자료구조	데이터가 나열된 순서	메모리 상의 임의의 위치 (포인터로 연결)	불일치

3. 대표적인 순차 자료구조

3.1 정적 배열 (Static Array)

선언 시점에 크기가 결정되며, 컴파일 타임에 메모리 공간이 할당됩니다. 한 번 할당된 크기는 변경할 수 없으며, 선언 위치에 따라 스택(Stack) 또는 데이터(Data) 영역에 할당됩니다.

3.2 동적 배열 (Dynamic Array / ArrayList)

실행 시간(Runtime)에 크기가 결정되며, 힙(Heap) 영역에 할당됩니다. 배열의 공간이 가득 차면 더 큰 새로운 배열을 생성하고 기존 데이터를 복사하는 방식으로 크기를 확장합니다.

3.3 언어별 구현 예시

# Python: 리스트 (동적 배열 기반)
arr = [10, 20, 30]
print(arr[1]) # 인덱스 접근: 20

# Java: 정적 배열 vs ArrayList
int[] staticArr = new int[5]; // 정적 배열
ArrayList<Integer> dynamicArr = new ArrayList<>(); // 동적 배열
dynamicArr.add(10);

4. 시간 복잡도 분석

순차 자료구조의 효율성은 접근 속도는 매우 빠르나, 데이터의 변경(삽입/삭제) 비용이 높다는 점에 있습니다.

연산	시간 복잡도	설명
조회 (Access)	$O(1)$	인덱스를 통해 즉시 접근 가능
검색 (Search)	$O(n)$	최악의 경우 모든 요소를 순회해야 함 (정렬 시 이진 검색 $O(\log n)$ 가능)
삽입 (Insertion)	$O(n)$	중간 삽입 시 시프팅 필요. 단, 동적 배열 끝에 추가 시 분할 상환 시간 복잡도(Amortized Time Complexity) $O(1)$
삭제 (Deletion)	$O(n)$	삭제 위치 이후의 모든 데이터를 앞으로 시프팅해야 함

5. 장단점 및 활용 사례

5.1 장점

빠른 접근 속도: 인덱스를 사용하여 특정 위치의 데이터를 즉시 읽을 수 있습니다.
캐시 효율성: 데이터가 물리적으로 인접해 저장되어 있어, CPU가 데이터를 읽을 때 주변 데이터까지 함께 캐시 메모리에 올리는 공간 지역성(Spatial Locality) 원리에 의해 캐시 적중률(Cache Hit Rate)이 매우 높습니다.

5.2 단점

크기 제약: 정적 배열의 경우 초기 설정 크기를 초과하는 데이터를 저장할 수 없습니다.
비효율적인 수정: 중간에 데이터를 삽입하거나 삭제할 때 발생하는 시프팅 비용이 큽니다.

5.3 실제 활용 사례 (스택과 큐의 구현)

순차 자료구조는 다른 추상 자료형(ADT)을 구현하는 기초가 됩니다.

스택 (Stack): 배열의 끝부분을 top 포인터로 관리하여 구현합니다. push와 pop이 모두 배열의 끝에서 일어나므로 시프팅이 발생하지 않아 $O(1)$의 효율을 가집니다.
큐 (Queue): 일반 배열로 구현 시 삭제(dequeue) 때마다 시프팅이 발생하여 비효율적입니다. 이를 해결하기 위해 배열의 시작과 끝을 가리키는 두 개의 포인터(front, rear)를 사용하며, 끝에 도달하면 다시 처음으로 돌아가는 원형 큐(Circular Queue) 방식으로 구현하여 $O(1)$의 효율을 확보합니다.

[원형 큐 작동 원리 예시]

배열 크기가 5인 원형 큐 (front=0, rear=0)

1. 데이터 삽입 (push): rear를 시계방향으로 이동하며 저장
[ 10 ] [ 20 ] [ 30 ] [ 40 ] [ 50 ]
  ↑     ↑     ↑     ↑     ↑
 front  1     2     3    rear (rear가 끝에 도달)

2. 데이터 삭제 (pop): front를 시계방향으로 이동하며 제거
[ (X) ] [ (X) ] [ 30 ] [ 40 ] [ 50 ]
              ↑
            front

3. 다시 삽입: rear가 배열의 끝(4)을 넘어 다시 0번 인덱스로 순환
[ 60 ] [ (X) ] [ 30 ] [ 40 ] [ 50 ]
  ↑
 rear

6. 연결 자료구조와의 비교

순차 자료구조와 대비되는 연결 자료구조(Linked Data Structure)는 데이터와 다음 데이터의 주소(포인터)를 함께 저장하는 방식입니다.

비교 항목	순차 자료구조 (Sequential)	연결 자료구조 (Linked)
메모리 할당	연속적인 공간 할당	불연속적인 공간 할당
접근 속도	매우 빠름 ($O(1)$)	느림 ($O(n)$, 순차 탐색 필요)
삽입/삭제	느림 (시프팅 필요)	빠름 (포인터 변경만으로 가능)
메모리 사용	데이터만 저장 (효율적)	포인터 저장 공간 추가 필요
적합한 상황	데이터 양이 고정적이고 조회가 빈번할 때	데이터 양의 변동이 심하고 삽입/삭제가 빈번할 때

[요약: 선택 가이드] - 조회 성능이 최우선이며 데이터의 크기가 일정하다 $\rightarrow$ 순차 자료구조 (배열) - 삽입/삭제가 빈번하며 데이터의 크기가 가변적이다 $\rightarrow$ 연결 자료구조 (연결 리스트)

📝 마크다운 원본

이 문서의 마크다운 원본 내용입니다.

# 순차 자료구조 (Sequential Data Structure)

## 1. 개요
순차 자료구조란 데이터가 메모리 상에 물리적으로 연속적인 공간에 저장되는 선형 자료구조를 의미합니다. 데이터의 논리적인 순서와 물리적인 저장 순서가 일치하는 것이 특징이며, 가장 대표적인 형태로 배열(Array)이 있습니다.

## 2. 주요 특징 및 작동 원리

### 2.1 직접 접근 (Direct Access)
순차 자료구조의 가장 큰 특징은 **인덱스(Index)**를 통한 직접 접근이 가능하다는 점입니다. 인덱스란 데이터 요소의 위치를 나타내는 정수 값으로, 메모리 주소 계산식(`시작 주소 + (인덱스 * 데이터 크기)`)을 통해 원하는 요소의 위치를 즉시 찾아낼 수 있습니다.

### 2.2 데이터 이동 (Shifting)
데이터의 삽입이나 삭제가 발생할 때, 물리적 연속성을 유지하기 위해 기존 데이터들을 옆으로 밀어내는 **시프팅(Shifting)** 과정이 필요합니다.

**[데이터 삽입 시 시프팅 과정 예시]**
인덱스 1번 위치에 새로운 값 'X'를 삽입하려는 경우:
```text
초기 상태: [ A ] [ B ] [ C ] [ D ] [ E ]
             0     1     2     3     4  (인덱스)

1단계(이동): [ A ] [ B ] [ B ] [ C ] [ D ]
             0     1     2     3     4  (인덱스)
                     ↑     ↑     ↑
                  (B이동) (C이동) (D이동)

2단계(삽입): [ A ] [ X ] [ B ] [ C ] [ D ]
             0     1     2     3     4  (인덱스)
```

### 2.3 논리적 순서와 물리적 저장 순서 비교
| 구분 | 논리적 순서 (Logical Order) | 물리적 저장 순서 (Physical Order) | 일치 여부 |
| :--- | :--- | :--- | :---: |
| **순차 자료구조** | 데이터가 나열된 순서 | 메모리 주소가 연속된 순서 | **일치** |
| **연결 자료구조** | 데이터가 나열된 순서 | 메모리 상의 임의의 위치 (포인터로 연결) | **불일치** |

## 3. 대표적인 순차 자료구조

### 3.1 정적 배열 (Static Array)
선언 시점에 크기가 결정되며, 컴파일 타임에 메모리 공간이 할당됩니다. 한 번 할당된 크기는 변경할 수 없으며, 선언 위치에 따라 **스택(Stack) 또는 데이터(Data) 영역**에 할당됩니다.

### 3.2 동적 배열 (Dynamic Array / ArrayList)
실행 시간(Runtime)에 크기가 결정되며, 힙(Heap) 영역에 할당됩니다. 배열의 공간이 가득 차면 더 큰 새로운 배열을 생성하고 기존 데이터를 복사하는 방식으로 크기를 확장합니다.

**[메모리 할당 차이 비교]**
| 항목 | 정적 배열 (Static Array) | 동적 배열 (Dynamic Array) |
| :--- | :--- | :--- |
| **할당 시점** | 컴파일 타임 (Compile-time) | 런타임 (Runtime) |
| **할당 영역** | 스택(Stack) 또는 데이터 영역 | 힙(Heap) 영역 |
| **크기 변경** | 불가능 (고정 크기) | 가능 (자동 확장) |
| **메모리 효율** | 낭비 가능성 높음 (최대치 설정 시) | 유연하지만 확장 시 오버헤드 발생 |

### 3.3 언어별 구현 예시
```python
# Python: 리스트 (동적 배열 기반)
arr = [10, 20, 30]
print(arr[1]) # 인덱스 접근: 20

# Java: 정적 배열 vs ArrayList
int[] staticArr = new int[5]; // 정적 배열
ArrayList<Integer> dynamicArr = new ArrayList<>(); // 동적 배열
dynamicArr.add(10);
```

## 4. 시간 복잡도 분석

순차 자료구조의 효율성은 접근 속도는 매우 빠르나, 데이터의 변경(삽입/삭제) 비용이 높다는 점에 있습니다.

| 연산 | 시간 복잡도 | 설명 |
| :--- | :---: | :--- |
| **조회 (Access)** | $O(1)$ | 인덱스를 통해 즉시 접근 가능 |
| **검색 (Search)** | $O(n)$ | 최악의 경우 모든 요소를 순회해야 함 (정렬 시 이진 검색 $O(\log n)$ 가능) |
| **삽입 (Insertion)** | $O(n)$ | 중간 삽입 시 시프팅 필요. 단, 동적 배열 끝에 추가 시 **분할 상환 시간 복잡도(Amortized Time Complexity) $O(1)$** |
| **삭제 (Deletion)** | $O(n)$ | 삭제 위치 이후의 모든 데이터를 앞으로 시프팅해야 함 |

## 5. 장단점 및 활용 사례

### 5.1 장점
- **빠른 접근 속도**: 인덱스를 사용하여 특정 위치의 데이터를 즉시 읽을 수 있습니다.
- **캐시 효율성**: 데이터가 물리적으로 인접해 저장되어 있어, CPU가 데이터를 읽을 때 주변 데이터까지 함께 캐시 메모리에 올리는 **공간 지역성(Spatial Locality)** 원리에 의해 캐시 적중률(Cache Hit Rate)이 매우 높습니다.

### 5.2 단점
- **크기 제약**: 정적 배열의 경우 초기 설정 크기를 초과하는 데이터를 저장할 수 없습니다.
- **비효율적인 수정**: 중간에 데이터를 삽입하거나 삭제할 때 발생하는 시프팅 비용이 큽니다.

### 5.3 실제 활용 사례 (스택과 큐의 구현)
순차 자료구조는 다른 추상 자료형(ADT)을 구현하는 기초가 됩니다.

- **스택 (Stack)**: 배열의 끝부분을 `top` 포인터로 관리하여 구현합니다. `push`와 `pop`이 모두 배열의 끝에서 일어나므로 시프팅이 발생하지 않아 $O(1)$의 효율을 가집니다.
- **큐 (Queue)**: 일반 배열로 구현 시 삭제(`dequeue`) 때마다 시프팅이 발생하여 비효율적입니다. 이를 해결하기 위해 배열의 시작과 끝을 가리키는 두 개의 포인터(`front`, `rear`)를 사용하며, 끝에 도달하면 다시 처음으로 돌아가는 **원형 큐(Circular Queue)** 방식으로 구현하여 $O(1)$의 효율을 확보합니다.

**[원형 큐 작동 원리 예시]**
```text
배열 크기가 5인 원형 큐 (front=0, rear=0)

1. 데이터 삽입 (push): rear를 시계방향으로 이동하며 저장
[ 10 ] [ 20 ] [ 30 ] [ 40 ] [ 50 ]
  ↑     ↑     ↑     ↑     ↑
 front  1     2     3    rear (rear가 끝에 도달)

2. 데이터 삭제 (pop): front를 시계방향으로 이동하며 제거
[ (X) ] [ (X) ] [ 30 ] [ 40 ] [ 50 ]
              ↑
            front

3. 다시 삽입: rear가 배열의 끝(4)을 넘어 다시 0번 인덱스로 순환
[ 60 ] [ (X) ] [ 30 ] [ 40 ] [ 50 ]
  ↑
 rear
```

## 6. 연결 자료구조와의 비교

순차 자료구조와 대비되는 연결 자료구조(Linked Data Structure)는 데이터와 다음 데이터의 주소(포인터)를 함께 저장하는 방식입니다.

| 비교 항목 | 순차 자료구조 (Sequential) | 연결 자료구조 (Linked) |
| :--- | :--- | :--- |
| **메모리 할당** | 연속적인 공간 할당 | 불연속적인 공간 할당 |
| **접근 속도** | 매우 빠름 ($O(1)$) | 느림 ($O(n)$, 순차 탐색 필요) |
| **삽입/삭제** | 느림 (시프팅 필요) | 빠름 (포인터 변경만으로 가능) |
| **메모리 사용** | 데이터만 저장 (효율적) | 포인터 저장 공간 추가 필요 |
| **적합한 상황** | 데이터 양이 고정적이고 조회가 빈번할 때 | 데이터 양의 변동이 심하고 삽입/삭제가 빈번할 때 |

**[요약: 선택 가이드]**
- **조회 성능**이 최우선이며 데이터의 **크기가 일정**하다 $\rightarrow$ **순차 자료구조 (배열)**
- **삽입/삭제**가 빈번하며 데이터의 **크기가 가변적**이다 $\rightarrow$ **연결 자료구조 (연결 리스트)**

AI 생성 콘텐츠 안내

이 문서는 AI 모델(gemma-4-31b)에 의해 생성된 콘텐츠입니다.

주의사항: AI가 생성한 내용은 부정확하거나 편향된 정보를 포함할 수 있습니다. 중요한 결정을 내리기 전에 반드시 신뢰할 수 있는 출처를 통해 정보를 확인하시기 바랍니다.

위키너와나