배열(Array)

배열이란?

배열은 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합입니다.

*여기서 설명하는 배열은 ‘정적 배열’을 기준으로 합니다.

배열의 특징

  • 고정된 크기: 정적 배열은 선언 시점에 크기가 확정되며, 실행 도중에 크기를 변경할 수 없습니다.
  • 인덱스를 이용한 빠른 접근: 메모리 주소가 연속적이기 때문에 arr[k]로 k번째 원소에 O(1) 시간에 접근 가능합니다. 이 때, 직접 접근이 가능하다는 것은 랜덤 접근으로 표현하기도 합니다.
  • 삽입/삭제의 비효율: 중간에 원소를 삽입하거나 삭제하려면, 뒤쪽에 위치한 원소를 전부 옮겨야 하기 때문에 O(n) 시간이 소요됩니다.

랜덤 접근과 순차적 접근

  • 직접 접근 == 랜덤 접근
  • 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때, 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능입니다.
  • 이와 반대인 순차적 접근은 데이터를 저장된 순서대로 검색해야 합니다.

배열과 연결 리스트의 비교

  • 탐색 속도는 배열이 연결 리스트보다 빠르다.
    • 배열의 경우, 각 요소를 탐색하면 되지만 연결 리스트의 경우, 연결된 다음 요소에 따라 찾는 데에 시간이 더 오래 소요됩니다.
  • 추가 및 삭제는 연결 리스트가 배열보다 빠르다.
    • 배열은 모든 요소를 옮겨야 추가 또는 삭제가 가능하지만 연결 리스트의 경우 다음에 올 요소에 대해 가리키는 주소를 바꿔주면 되기 때문에 더 빠릅니다.

동적 배열(Dynamic Array - vector, ArrayList)

동적 배열이란?

동적으로 요소를 할당할 수 있는 자료구조입니다. 정적 자료구조인 배열의 단점을 보완하여 동적으로 배열의 사이즈를 조정할 수 있도록 한 자료구조입니다.

동적 배열의 특징

  • 배열의 크기 변경: 요소를 배열처럼 연속적으로 저장하면서, 배열의 크기를 필요에 따라 확장 또는 축소할 수 있는 구조입니다.
  • 동작의 원리: 초기 용량을 정하고, 원소를 삽입하면서 현재 사용 크기가 한계에 도달하면 용량을 2배 등으로 늘려 새 배열을 할당한 후 기존 데이터를 복사한 뒤 새 배열로 교체합니다.

동적 배열의 예시

C++의 Vector 

#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v;          // 기본 생성 (용량 0 또는 최소 시작)
    v.push_back(10);        // 동적 확장되어 10 삽입
    v.push_back(20);
    
    cout << v[0] << endl;   // 인덱스로 접근
    cout << v.size() << endl;
    return 0;
}
  • 특징
    • 동적 확장: push_back()으로 원소를 추가할 때, 내부 용량이 가득차면 두 배 크기로 재할당(Amortized O(1) 삽입)
    • 랜덤 접근: v[i]로 O(1) 접근 가능
    • 메모리 연속성: 내부적으로 연속된 배열을 사용하므로, 캐시 친화적(Cache-friendly)
    • 삽입/삭제: 맨 뒤 O(1), 중간 O(n)

자바의 ArrayList 

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(10);
        list.add(20);
        
        System.out.println(list.get(0));  // 10
        System.out.println(list.size());  // 2
    }
}
  • 특징
    • 내부적으로 Object[] 배열로 관리
    • 원소가 추가될 때, 동적 활당(새 배열 할당 후 복사)
    • 인덱스 접근 가능, 일부 메서드(get(index) 등)가 O(1)
    • 임의 접근 O(1), 중간 삽입/삭제 O(n)

자바스크립트의 Array 

let arr = [];
arr.push(10);      // 동적으로 확장
arr.push(20);

arr[2] = 30;       // 인덱스로 추가 가능
console.log(arr);  // [10, 20, 30]

arr.pop();         // 맨 끝 원소 제거
console.log(arr);  // [10, 20]
  • 특징
    • 일반 배열처럼 보이나 내부적으로는 동적 할당 구조를 가집니다.
    • 크기를 명시적으로 고정할 필요가 없고, push(), pop() 등을 사용하면 알아서 크기가 확장/축소됩니다.
    • 인덱스를 순차적으로 사용하는 경우에는 배열처럼 작동하며, 희소 배열(중간에 인덱스가 비는) 형태로도 동작 가능

배열과 동적 배열 비교

| 항목 | 정적 배열 (Array) | 동적 배열 (Dynamic Array) | |———————|———————————————|———————————————————–| | 크기 지정 | 고정적 (선언 시 크기 확정) | 자동 또는 프로그래머가 원하는 시점에 변경 | | 메모리 구조 | 연속적 | 연속적 (단, 확장 시 재할당 후 복사) | | 삽입/삭제 (맨 뒤) | O(1) (여유 공간이 있어야 함) | 평균(Amortized) O(1) | | 삽입/삭제 (중간) | O(n) (원소들을 한 칸씩 밀거나 당겨야 함) | O(n) (배열 내부 이동 필요) | | 랜덤 접근 | O(1) (인덱스로 직접 접근) | O(1) (인덱스로 직접 접근) | | 예시 언어/클래스 | C/C++ 배열, Java 배열 등 | C++ std::vector, Java ArrayList, JavaScript Array |

참고 자료

  1. 면접을 위한 CS 전공지식 노트, 주홍철
  2. https://www.geeksforgeeks.org/array-data-structure-guide/