[자료구조] 배열

배열(Array)은 가장 기본적이면서도 중요한 자료구조입니다. 여러 개의 데이터를 연속된 메모리 공간에 저장하고, 각 요소를 **인덱스(index)**로 접근할 수 있는 구조를 가지고 있습니다. 이 글에서는 배열의 특징과 배열에서 발생하는 주요 연산 복잡도, 그리고 이차원·삼차원 배열까지 간단하게 정리해보겠습니다.

 

1. 배열이란 무엇인가?

배열(Array)은 일정한 메모리 공간에 요소들이 순차적으로 나열된 자료구조입니다.

• 모든 요소는 고유한 인덱스(0부터 시작) 를 가짐
• 인덱스를 통해 원하는 요소를 빠르게 찾거나 수정 가능
• 메모리 상에 연속적으로 저장됨

예시)

기	술	면	접	화	이	팅
0	1	2	3	4	5	6

 

 

2. 배열과 RAM — 접근 속도가 일정한 이유

배열은 RAM(Random Access Memory) 구조와 유사합니다.
RAM은 어떤 주소에 접근하더라도 시간이 일정하며,
배열도 같은 방식으로 인덱스만 알면 즉시 접근이 가능합니다.

• 특정 인덱스에 접근하는 시간: O(1)
• 특정 인덱스 값을 수정하는 시간: O(1)

즉, 배열은 임의 접근(random access)이 매우 빠른 자료구조라는 특징을 가집니다.

 

3. 배열에서 원하는 데이터를 찾는 시간 — 순차 탐색

하지만 배열에 특정 값이 존재하는지 확인하는 경우는 상황이 달라집니다.

• 0번 인덱스부터 순차적으로 확인
• 최악의 경우 N개의 요소를 모두 확인해야 함
• 따라서 탐색 연산의 시간 복잡도는 O(n)

즉, “배열 = 항상 빠르다”는 것이 아니라,
인덱스로 접근하는 연산만 빠른 것이라는 점을 이해해야 합니다.

 

4. 배열에서 삽입/삭제 연산이 느린 이유

배열은 메모리 상에 연속적으로 저장되기 때문에,
중간에 데이터를 삽입하거나 삭제하면 뒤에 있는 모든 요소들이 이동해야 합니다.

예)

• 1번 자리에 새로운 데이터를 삽입하면
  → 기존 1, 2, 3 … N까지 모두 한 칸씩 밀어야 함
• 삭제도 마찬가지로 요소들을 앞으로 당겨야 함

따라서 배열의 삽입 및 삭제 연산은 O(n) 의 시간 복잡도를 가집니다.

 

5. 배열의 확장: 이차원 배열, 삼차원 배열

배열은 1차원뿐 아니라,
이차원(행 × 열), 삼차원(행 × 열 × 깊이) 형태로도 확장할 수 있습니다.

 

1️⃣  이차원 배열

• 배열 속에 배열이 있는 구조
• 인덱스 두 개(예: arr[행][열])로 요소를 식별

2️⃣  삼차원 배열

• 배열 속에 배열이, 그 안에도 배열이 포함된 구조
• 인덱스 세 개로 요소를 식별 (예: arr[행][열][깊이])

메모리 상에서는 결국 모두 1차원 형태로 펼쳐져 저장되지만,
논리적 구조는 2D 또는 3D처럼 사용할 수 있습니다.

 

이차원 배열: 행 - 열 순서로 메모리에 정리 / 삼차원 배열: 행 - 열 - 깊이 순서로 메모리에 정리

 

 

 

정리하면

 

배열(Array)은

• 인덱스를 통한 접근이 빠른 O(1) 구조
• 탐색/삽입/삭제는 상대적으로 느린 O(n) 연산
• 연속된 메모리 공간을 사용하여 속도가 빠르지만 유연성은 떨어짐
• 2차원/3차원 배열로 확장 가능

이러한 배열의 특징을 이해하면,
왜 특정 알고리즘이나 프로그래밍 언어에서 배열 대신 연결 리스트(linked list) 를 사용하기도 하는지 자연스럽게 이해할 수 있습니다.