배열의 연속 메모리와 정렬 알고리즘 4종

배열은 “빠른 자료구조”로 뭉뚱그려 외우기 쉽지만, 실제로 빠른 이유는 메모리에 연속으로 놓인다는 한 가지에서 전부 나온다. 이 글에서는 그 성질에서 임의 접근 O(1)과 중간 삽입·삭제 비용이 어떻게 갈라지는지, 그리고 그 위에서 정렬 알고리즘 네 가지(삽입·병합·계수·힙)를 입력 특성에 따라 어떻게 고르는지를 이야기하려 한다.

배열 — 연속 메모리가 만드는 이득과 대가

배열은 같은 타입의 데이터를 인덱스로 빠르게 관리하는 자료구조다. 특징은 네 가지로 정리된다. arr[0]~arr[n-1]이 메모리에 연속 배치되고, 그 덕에 arr[i] 형태의 임의 접근(Random Access)이 즉시 가능하다. 대신 정적 배열은 선언 시 크기가 정해져 런타임에 늘릴 수 없고, for 루프로 전체 순회/가공하기에는 단순하고 빠르다.

1차원 배열 선언과 초기화:

int arr[5] = {10, 20, 30, 40, 50};

인덱스 범위는 0~4이고, 범위를 넘는 접근은 UB(Undefined Behavior, 어떤 결과가 나올지 보장되지 않는 동작) 위험이 있다.

2차원 배열은 행/열 인덱스 모두 경계 체크가 필요하다(0<=r<R, 0<=c<C).

int board[3][4] = {0};
board[1][2] = 7;

연속 메모리라는 특성은 주소를 직접 찍어보면 확인된다.

for (int i = 0; i < 5; i++) {
    cout << "arr[" << i << "] = " << arr[i] 
         << ", 주소: " << &arr[i] << endl;
}

주소 간격이 일정하게 증가하면 연속 배치라는 뜻이고, 이 특성이 순차 처리에서 캐시 효율 향상으로 이어진다. 또 순차 접근 없이도 특정 원소를 O(1)에 조회/수정할 수 있다.

cout << arr[0] << endl;
cout << arr[2] << endl;
arr[1] = 99;

실전에서 주의할 점:

• 입력 크기 N이 크고 중간 삽입/삭제가 많으면 배열 단독 사용은 시간초과 위험.
• 배열 문제의 첫 단계는 연산 패턴 분류(조회 중심 vs 구조 변경 중심).
• 오프바이원(off-by-one, 인덱스가 하나 어긋나는 실수) 방지를 위해 경계 테스트(N=1, 마지막 인덱스) 필수.
• 2차원 배열은 행/열 순서와 범위 검증을 먼저 고정하고 구현.

정렬 — 입력 특성으로 알고리즘을 고른다

정렬 알고리즘의 동작 원리와 시간복잡도를 비교하고, 정렬로 탐색 효율을 개선해 이진탐색의 전제를 갖추는 것이 목표다. 핵심 알고리즘은 네 가지 — 삽입 정렬(key 삽입 방식, 역순 입력에서 최악 O(N²)), 병합 정렬(분할 정복, 안정적 O(N log N)), 계수 정렬(O(N+K), 값 범위 K가 작을 때 효과적), 힙 정렬(max_heapify/build_heap 기반 O(N log N)).

삽입 정렬 코드 포인트:

for (int i = 1; i < n; i++) {
  int key = arr[i], j = i - 1;
  while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j--; }
  arr[j+1] = key;
}

효율성 비교:

알고리즘	시간복잡도	유의점
삽입 정렬	평균/최악 O(N^2)	거의 정렬된 입력에서 유리
병합 정렬	O(N log N)	안정적 성능, 대용량 적합
계수 정렬	O(N+K)	범위 K 크면 비효율
힙 정렬	O(N log N)	힙 구성/유지 로직 실수 주의

실전에서는 정렬 기준(오름/내림/커스텀)과 안정성 요구를 먼저 확인하고, 정렬 후 이분탐색 결합이 가능한지 우선 판단한다. 값 범위가 좁으면 계수 정렬, 아니면 비교 정렬을 고른다.

같은 회차에 이어 복습한 C 동적할당·구조체는 이 글의 주제와 결이 달라 덜어냈다. 힙 할당과 소유권 이야기는 new vs malloc에 따로 정리해 두었다.

핵심 요약 — 배열은 연속 메모리 덕에 O(1) 임의 접근과 캐시 효율을 얻지만, 중간 삽입/삭제가 많은 문제에서는 시간초과 위험이 있다. 정렬은 입력 특성(거의 정렬된 입력, 값 범위 K)에 따라 삽입/병합/계수/힙을 골라 쓴다.