배열

배열이란

배열(array) 은 여러 데이터를 순서대로 저장하는 선형 자료구조입니다.

배열 안의 각 값은 순서를 가지고 있으며 각 위치에는 번호가 붙습니다. 이 번호를 인덱스(index)라고 합니다.

const numbers = [10, 20, 30, 40];

위 배열은 다음처럼 생각할 수 있습니다.

index:   0    1    2    3
value:  10   20   30   40

배열에서 첫 번째 값의 인덱스는 보통 0입니다. 그래서 numbers[0]은 첫 번째 값인 10을 가리키고, numbers[2]는 세 번째 값인 30을 가리킵니다.

numbers[0]; // 10
numbers[2]; // 30

배열의 중요한 특징은 다음과 같습니다.

• 데이터를 순서대로 저장한다.
• 각 데이터는 인덱스를 가진다.
• 인덱스를 이용해 특정 위치의 값에 접근할 수 있다.
• 전체 데이터를 처음부터 끝까지 순회하기 쉽다.

즉 배열은 순서가 있는 데이터 목록을 표현하기에 적합한 자료구조입니다.

인덱스로 접근한다는 것

배열의 핵심은 인덱스(index)입니다.

인덱스는 배열 안에서 값의 위치를 나타내는 번호입니다. 배열은 이 인덱스를 이용해 특정 위치의 값을 바로 읽을 수 있습니다.

const fruits = ["apple", "banana", "cherry"];

fruits[0]; // "apple"
fruits[1]; // "banana"
fruits[2]; // "cherry"

여기서 중요한 점은 배열이 값을 찾기 위해 앞에서부터 차례대로 확인하지 않아도 된다는 것입니다. fruits[2]라고 하면 배열은 세 번째 위치에 있는 값을 바로 읽을 수 있습니다.

이런 접근 방식을 임의 접근(random access) 이라고 합니다. 임의 접근이 가능하다는 것은 원하는 위치를 알고 있을 때 그 위치의 값에 바로 접근할 수 있다는 뜻입니다.

하지만 인덱스로 접근하기 위해서는 항상 정확한 위치를 알고 있어야만 합니다. 원하는 값이 어디에 있는지 모른다면 그때는 배열을 처음부터 끝까지 확인해야만 원하는 값을 찾아낼 수 있습니다.

배열의 기본 연산

배열을 다룰 때 자주 사용하는 기본 연산은 크게 다섯 가지입니다.

접근

접근은 특정 인덱스에 있는 값을 읽는 연산입니다.

const numbers = [10, 20, 30, 40];

numbers[2]; // 30

인덱스 2를 알고 있다면 배열은 바로 세 번째 값에 접근할 수 있습니다. 배열의 크기가 4이든, 4000이든, 인덱스를 알고 있다면 접근 시간은 거의 일정합니다.

그래서 배열의 인덱스 접근은 보통 O(1) 로 표현합니다.

순회

순회는 배열의 모든 값을 처음부터 끝까지 하나씩 확인하는 연산입니다.

const numbers = [10, 20, 30, 40];

for (let i = 0; i < numbers.length; i++) {
  console.log(numbers[i]);
}

배열에 값이 n개 있다면 모든 값을 한 번씩 확인해야 합니다. 그래서 순회의 시간 복잡도는 O(n) 입니다.

순회는 배열을 다룰 때 가장 기본적인 패턴입니다. 합계를 구하거나, 최댓값을 찾거나, 조건에 맞는 값을 세는 작업은 대부분 배열 순회에서 시작됩니다.

탐색

탐색은 배열 안에서 원하는 값을 찾는 연산입니다.

const numbers = [10, 20, 30, 40];

function includes(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return true;
    }
  }

  return false;
}

includes(numbers, 30); // true

여기서 30이 어느 위치에 있는지 모른다면 앞에서부터 하나씩 확인해야 합니다. 운이 좋으면 첫 번째에서 찾을 수도 있지만, 최악의 경우 마지막까지 확인해야 합니다.

그래서 일반적인 배열 탐색의 시간 복잡도는 O(n) 입니다.

삽입

삽입은 배열에 새로운 값을 추가하는 연산입니다.

배열의 끝에 값을 추가하는 경우는 비교적 단순합니다.

const numbers = [10, 20, 30];

numbers.push(40);

// [10, 20, 30, 40]

하지만 배열의 중간에 값을 넣는 경우에는 주의가 필요합니다.

기존 배열:

index:   0    1    2    3
value:  10   20   30   40

인덱스 1에 15를 넣고 싶다면:

index:   0    1    2    3    4
value:  10   15   20   30   40

15를 넣기 위해 기존의 20, 30, 40을 한 칸씩 뒤로 밀어야 합니다. 이처럼 중간 삽입은 주변 원소들을 이동시켜야 하기 때문에 비용이 커질 수 있습니다.

삭제

삭제는 배열에서 특정 값을 제거하는 연산입니다.

배열의 마지막 값을 제거하는 경우는 비교적 단순합니다.

const numbers = [10, 20, 30, 40];

numbers.pop();

// [10, 20, 30]

하지만 중간 값을 삭제하면 뒤에 있던 값들을 앞으로 당겨야 합니다.

기존 배열:

index:   0    1    2    3
value:  10   20   30   40

인덱스 1의 20을 삭제하면:

index:   0    1    2
value:  10   30   40

20이 빠진 자리를 채우기 위해 30, 40을 한 칸씩 앞으로 당겨야 합니다. 그래서 중간 삭제 역시 최악의 경우 O(n) 이 걸릴 수 있습니다.

배열의 시간 복잡도

배열의 기본 연산을 시간 복잡도로 정리하면 다음과 같습니다.

연산	시간 복잡도	이유
접근	O(1)	인덱스를 이용해 원하는 위치에 바로 접근할 수 있다.
순회	O(n)	모든 원소를 한 번씩 확인해야 한다.
탐색	O(n)	원하는 값이 어디 있는지 모르면 앞에서부터 확인해야 한다.
끝 삽입	O(1) 또는 amortized O(1)	끝에 추가하는 것은 보통 빠르지만, 동적 배열에서는 가끔 크기 조정이 일어날 수 있다.
중간 삽입	O(n)	뒤 원소들을 한 칸씩 밀어야 할 수 있다.
끝 삭제	O(1)	마지막 원소만 제거하면 된다.
중간 삭제	O(n)	뒤 원소들을 한 칸씩 앞으로 당겨야 할 수 있다.

이 표에서 가장 중요한 구분은 접근과 탐색입니다.

배열은 특정 위치에 접근하는 것은 빠릅니다. 하지만 특정 값을 찾는 것은 빠르다고 말할 수 없습니다. 인덱스를 알고 있느냐, 모르느냐가 배열의 성능을 크게 바꿉니다.

const numbers = [10, 20, 30, 40];

numbers[2]; // 접근: 인덱스를 알고 있으므로 O(1)

numbers.includes(30); // 탐색: 값의 위치를 모르면 차례대로 확인하므로 O(n)

배열이 빠른 이유

배열이 빠른 이유는 데이터가 순서대로 놓여 있고, 각 위치를 인덱스로 계산할 수 있기 때문입니다.

조금 더 낮은 수준에서 보면 배열은 보통 연속된 공간에 값을 저장합니다. 각 칸의 크기가 같다면 특정 인덱스의 위치는 다음처럼 계산할 수 있습니다.

원하는 위치 = 시작 위치 + 인덱스 × 칸의 크기

예를 들어 각 칸의 크기가 같고, 배열의 시작 위치를 알고 있다면 3번 인덱스의 위치는 앞에서부터 세 칸 떨어진 곳입니다. 따라서 배열은 0, 1, 2를 차례로 확인하지 않고도 3번 위치로 바로 갈 수 있습니다.

이것이 배열의 인덱스 접근이 O(1) 인 이유입니다.

배열이 빠른 상황은 대부분 이 특징에서 나옵니다. 특정 번째 값을 읽거나, 순서대로 값을 처리하거나, 구간을 다룰 때 배열은 단순하고 효율적인 구조가 됩니다.

배열이 느려지는 순간

배열은 위치를 알고 접근할 때는 빠르지만 원소의 위치를 바꿔야 하는 순간 느려질 수 있습니다.

대표적인 경우가 중간 삽입과 중간 삭제입니다.

[10, 20, 30, 40]

인덱스 1에 15 삽입:

[10, 15, 20, 30, 40]
          └── 기존 원소들이 뒤로 밀림

배열은 순서가 중요한 자료구조입니다. 중간에 새로운 값을 넣으면 기존 원소들의 순서를 유지하기 위해 뒤쪽 값들을 이동시켜야 합니다.

삭제도 마찬가지입니다.

[10, 20, 30, 40]

인덱스 1의 20 삭제:

[10, 30, 40]
     └── 뒤 원소들이 앞으로 당겨짐

이처럼 배열은 값을 읽는 일에는 강하지만 중간 구조를 자주 바꾸는 일에는 불리할 수 있습니다.

배열이 잘 맞는 상황

배열은 다음과 같은 상황에 잘 맞습니다.

순서가 중요한 데이터를 다룰 때

배열은 값의 순서를 그대로 보존합니다.

const steps = ["로그인", "상품 선택", "결제", "완료"];

이처럼 순서가 의미를 가지는 데이터라면 배열이 자연스럽습니다.

인덱스로 자주 접근할 때

몇 번째 값인지 알고 있고 그 위치의 값을 자주 읽어야 한다면 배열이 좋습니다.

const scores = [80, 95, 70, 100];

const firstScore = scores[0];
const thirdScore = scores[2];

전체를 순회해야 할 때

모든 값을 한 번씩 처리해야 하는 작업에도 배열은 잘 맞습니다.

const prices = [1000, 2000, 3000];

const total = prices.reduce((sum, price) => sum + price, 0);

끝에 값을 추가하는 일이 많을 때

목록의 끝에 데이터를 추가하는 작업은 배열과 잘 맞습니다.

const messages = [];

messages.push("안녕하세요");
messages.push("반갑습니다");

많은 언어의 동적 배열은 끝에 값을 추가하는 작업을 효율적으로 처리합니다.

배열이 불리한 상황

반대로 배열이 항상 좋은 선택은 아닙니다.

중간 삽입과 삭제가 자주 일어날 때

배열 중간에 값을 자주 넣거나 빼야 한다면 매번 많은 원소를 이동시켜야 할 수 있습니다.

예를 들어 맨 앞에 계속 새로운 값을 넣는 구조라면 기존 원소들이 매번 뒤로 밀려납니다.

const queue = [];

queue.unshift("first");
queue.unshift("second");
queue.unshift("third");

이런 작업이 많은 상황이라면 배열보다 다른 자료구조가 더 적합할 수 있습니다.

값 검색이 자주 필요할 때

배열에서 특정 값을 찾으려면 보통 처음부터 끝까지 확인해야 합니다. 데이터가 많고 검색이 자주 일어난다면 해시 테이블처럼 탐색에 더 적합한 자료구조를 선택하는 것이 좋습니다.

const users = ["kim", "lee", "park"];

users.includes("park"); // 최악의 경우 끝까지 확인, O(N)

데이터 사이의 관계를 표현해야 할 때

배열은 순서를 표현하기에는 좋지만, 복잡한 관계를 표현하기에는 한계가 있습니다.

예를 들어 친구 관계, 지하철 노선, 파일 시스템, 조직도처럼 데이터 사이의 연결이나 계층이 중요하다면 트리나 그래프가 더 자연스러울 수 있습니다.

배열과 연결 리스트의 차이

배열을 학습할 때 자주 함께 비교되는 자료구조가 연결 리스트입니다.

배열은 데이터를 연속된 위치에 저장하고 인덱스로 접근합니다. 반면 연결 리스트는 각 데이터가 다음 데이터를 가리키는 방식으로 이어집니다.

구분	배열	연결 리스트
저장 방식	연속된 공간에 저장	노드들이 포인터로 연결
인덱스 접근	빠름, O(1)	느림, O(n)
순회	처음부터 끝까지 순서대로 가능	처음부터 노드를 따라가며 가능
중간 삽입/삭제	원소 이동이 필요할 수 있음	위치를 알고 있다면 연결만 바꾸면 됨
메모리 사용	값들이 촘촘히 저장됨	포인터를 위한 추가 공간이 필요

배열은 인덱스 접근과 순회에 강합니다. 연결 리스트는 특정 위치의 노드를 이미 알고 있을 때 삽입과 삭제를 유연하게 처리할 수 있습니다.

배열에서 이어지는 알고리즘 패턴

배열은 단순한 자료구조이지만 많은 알고리즘 패턴의 출발점이 됩니다.

순회

배열의 모든 값을 하나씩 확인하는 가장 기본적인 패턴입니다.

for (let i = 0; i < array.length; i++) {
  // array[i] 처리
}

합계, 개수 세기, 최댓값, 최솟값 찾기 같은 문제는 대부분 순회에서 시작합니다.

투 포인터

배열의 두 위치를 가리키는 포인터를 움직이며 문제를 푸는 방식입니다.

left →                 ← right
[ 1, 2, 3, 4, 5, 6, 7 ]

정렬된 배열에서 두 수의 합을 찾거나, 양쪽 끝에서 범위를 좁혀가는 문제에서 자주 사용됩니다.

슬라이딩 윈도우

배열의 연속된 구간을 유지하면서 왼쪽과 오른쪽 경계를 움직이는 방식입니다.

[ 1, 2, 3, 4, 5, 6 ]
      └──── window ────┘

연속 부분 배열의 합, 가장 긴 부분 문자열, 고정 길이 구간의 최댓값 같은 문제에서 자주 등장합니다.

누적합

구간 합을 빠르게 구하기 위해 배열의 앞부분 합을 미리 저장해두는 방식입니다.

nums:   [2, 4, 6, 8]
prefix: [0, 2, 6, 12, 20]

배열이 자주 바뀌지 않고 구간 합 질문이 많다면, 누적합을 이용해 매번 다시 더하는 비용을 줄일 수 있습니다.

해시 테이블과의 조합

배열만으로 값을 찾으면 O(n)이 걸릴 수 있습니다. 하지만 해시 테이블을 함께 사용하면 이전 값을 기억해 더 빠르게 처리할 수 있습니다.

대표적인 예가 Two Sum 문제입니다.

정리

배열은 여러 데이터를 순서대로 저장하고 각 위치에 인덱스로 접근할 수 있는 선형 자료구조입니다.

배열의 가장 큰 장점은 인덱스를 알고 있을 때 원하는 위치의 값에 빠르게 접근할 수 있다는 점입니다. 그래서 배열의 접근 연산은 O(1) 입니다.

하지만 배열이 항상 빠른 것은 아닙니다. 원하는 값의 위치를 모르면 처음부터 차례대로 탐색해야 하므로 O(n) 이 걸릴 수 있습니다. 또한 중간에 값을 삽입하거나 삭제할 때는 뒤 원소들을 밀거나 당겨야 하므로 비용이 커질 수 있습니다.

결국 배열을 사용할 때는 다음 질문을 함께 생각해야 합니다.

• 이 데이터는 순서가 중요한가?
• 특정 위치에 자주 접근해야 하는가?
• 전체를 순회하는 일이 많은가?
• 중간 삽입과 삭제가 자주 일어나는가?
• 값 검색이 자주 필요한가?

배열은 가장 기본적인 자료구조이지만, 그 안에는 자료구조 선택의 핵심이 담겨 있습니다. 어떤 연산이 빠르고 어떤 연산이 느린지 이해하면, 이후 연결 리스트, 스택, 큐, 해시 테이블 같은 자료구조도 더 쉽게 비교할 수 있습니다.