배열의 메모리 모델과 접근 비용
배열은 알고리즘 문제에서 가장 먼저 선택되는 기본 자료구조입니다. 인덱스로 바로 접근할 수 있어 빠르지만, 중간 삽입/삭제에서는 이동 비용이 크게 발생합니다.
배열의 성능은 연속 메모리라는 물리적 특성에서 시작됩니다. 이번 절에서는 배열의 강점과 한계를 같은 문제 흐름 안에서 점검하고, 어떤 입력 분포에서 배열을 유지할지 판단 기준까지 정리합니다.
핵심 개념 요약: 배열 메모리 모델
배열의 핵심은 세 가지입니다.
연속 메모리: 같은 타입 원소가 메모리에 붙어서 저장됩니다. 그래서 캐시 친화적 순회가 가능하고, 반복 조회 성능이 안정적입니다.
인덱스 기반 조회: arr[i]는 주소 계산으로 바로 접근하므로 평균/최악 모두 O(1)입니다.
조회가 많은 문제에서 배열이 기본 선택지가 되는 이유입니다.
중간 삽입/삭제 비용: 중간 위치를 바꾸면 뒤 원소들을 밀거나 당겨야 해서 O(N)이 됩니다.
입력이 커질수록 이 이동 비용이 병목으로 드러납니다.
선형 메모리 모델이 실무에서 중요한 이유
문제 풀이에서는 알고리즘만 보고 구조를 고르면 성능이 흔들리기 쉽습니다. 배열은 조회 중심 워크로드에서 강하고, 중간 수정 중심 워크로드에서는 약합니다.
예를 들어 로그 조회 API처럼 인덱스 탐색이 반복되는 상황에서는 배열이 유리합니다. 반대로 편집기 버퍼처럼 중간 삽입/삭제가 연속되는 경우에는 이동 비용이 누적되어 손해가 커집니다.
즉, 연산 분포를 먼저 보고 배열을 선택해야 합니다. 조회/갱신/삽입 비율을 대략 잡아 보면 구조 선택 오류를 초기에 줄일 수 있습니다.
미니 입력으로 동작 검증하기
작은 입력으로도 배열의 비용 특성을 바로 확인할 수 있습니다.
- 초기 배열:
[10, 20, 30, 40] - 작업: 인덱스
1에 값99삽입
- 기존
20, 30, 40은 한 칸씩 오른쪽으로 이동합니다. - 빈 위치
1에99를 배치합니다. - 이동 원소 수가 커질수록 비용이 선형으로 증가합니다.
중간 삽입 이동 비용 확인
문제 의도: 중간 삽입 시 이동되는 원소 수를 코드로 확인합니다.
입력 예시: [10,20,30,40]에 중간 삽입 2회
출력 목표: 삽입 후 배열 상태와 이동 횟수
#include <iostream>
#include <vector>
using namespace std;
int insert_middle_and_count_shifts(vector<int>& arr, int value) {
int mid = static_cast<int>(arr.size()) / 2;
int shifts = static_cast<int>(arr.size()) - mid;
arr.insert(arr.begin() + mid, value);
return shifts;
}
int main() {
vector<int> arr = {10, 20, 30, 40};
int moved1 = insert_middle_and_count_shifts(arr, 99);
int moved2 = insert_middle_and_count_shifts(arr, 77);
for (int x : arr) cout << x << " ";
cout << "\n";
cout << "shift count: " << moved1 << ", " << moved2 << "\n";
return 0;
}import java.util.ArrayList;
import java.util.List;
public class Main {
static int insertMiddleAndCountShifts(List<Integer> arr, int value) {
int mid = arr.size() / 2;
int shifts = arr.size() - mid;
arr.add(mid, value);
return shifts;
}
public static void main(String[] args) {
List<Integer> arr = new ArrayList<>(List.of(10, 20, 30, 40));
int moved1 = insertMiddleAndCountShifts(arr, 99);
int moved2 = insertMiddleAndCountShifts(arr, 77);
System.out.println(arr);
System.out.println("shift count: " + moved1 + ", " + moved2);
}
}def insert_middle_and_count_shifts(arr, value):
mid = len(arr) // 2
shifts = len(arr) - mid
arr.insert(mid, value)
return shifts
arr = [10, 20, 30, 40]
moved1 = insert_middle_and_count_shifts(arr, 99)
moved2 = insert_middle_and_count_shifts(arr, 77)
print(arr)
print("shift count:", moved1, moved2)fn insert_middle_and_count_shifts(arr: &mut Vec<i32>, value: i32) -> usize {
let mid = arr.len() / 2;
let shifts = arr.len() - mid;
arr.insert(mid, value);
shifts
}
fn main() {
let mut arr = vec![10, 20, 30, 40];
let moved1 = insert_middle_and_count_shifts(&mut arr, 99);
let moved2 = insert_middle_and_count_shifts(&mut arr, 77);
println!("{:?}", arr);
println!("shift count: {}, {}", moved1, moved2);
}배열 메모리 모델 동작 인덱스 끝점 확인
삽입 위치 뒤에 있는 원소 수만큼 이동이 발생합니다. 입력 크기가 커질수록 한 번의 삽입 비용도 함께 커지므로, 중간 삽입이 많은 문제에서는 배열이 불리해집니다.
- 평균 시간복잡도:
O(N) - 최악 시간복잡도:
O(N) - 추가 공간복잡도:
O(1)(컨테이너 내부 확장 비용 제외)
인덱스 조회 비용 확인
문제 의도: 인덱스 조회가 반복될 때 배열의 강점을 확인합니다.
입력 예시: arr=[3,1,4,1,5,9], idx=[0,2,5,3]
출력 목표: 조회 값의 합
#include <iostream>
#include <vector>
using namespace std;
int sum_by_indices(const vector<int>& arr, const vector<int>& idx) {
int total = 0;
for (int i : idx) total += arr[i];
return total;
}
int main() {
vector<int> arr = {3, 1, 4, 1, 5, 9};
vector<int> idx = {0, 2, 5, 3};
cout << sum_by_indices(arr, idx) << "\n"; // 3+4+9+1=17
return 0;
}public class Main {
static int sumByIndices(int[] arr, int[] idx) {
int total = 0;
for (int i : idx) total += arr[i];
return total;
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9};
int[] idx = {0, 2, 5, 3};
System.out.println(sumByIndices(arr, idx)); // 17
}
}def sum_by_indices(arr, idx):
total = 0
for i in idx:
total += arr[i]
return total
arr = [3, 1, 4, 1, 5, 9]
idx = [0, 2, 5, 3]
print(sum_by_indices(arr, idx)) # 17fn sum_by_indices(arr: &[i32], idx: &[usize]) -> i32 {
let mut total = 0;
for &i in idx {
total += arr[i];
}
total
}
fn main() {
let arr = [3, 1, 4, 1, 5, 9];
let idx = [0usize, 2, 5, 3];
println!("{}", sum_by_indices(&arr, &idx)); // 17
}배열 메모리 모델 동작 포인터 흐름 추적
배열은 arr[i]처럼 위치를 바로 계산할 수 있어 반복 조회에서도 성능이 안정적입니다.
조회 대상이 많아져도 각 조회가 O(1)이므로 전체는 조회 횟수에 비례해 증가합니다.
- 평균 시간복잡도:
O(Q)(Q는 조회 횟수) - 최악 시간복잡도:
O(Q) - 추가 공간복잡도:
O(1)(입력 배열 제외)
상충 지점
배열 선택은 조회와 수정 비율을 함께 봐야 합니다.
- 장점: 인덱스 조회가 빠르고 구현이 단순함
- 장점: 연속 메모리로 순회 성능이 안정적임
- 단점: 중간 삽입/삭제 시 이동 비용이 큼
- 단점: 크기 확장 시 재할당 비용이 발생할 수 있음
조회 중심이면 배열을 유지하고, 중간 수정 중심이면 링크 기반 구조나 덱을 검토하는 것이 안전합니다.
구간 합 질의와 전처리
문제 의도: 배열 전처리(누적합)로 반복 구간 질의를 빠르게 처리합니다.
입력 예시: arr=[3,1,4,1,5,9], 구간 [1,3], [2,5]
출력 목표: 6, 19
배열의 선형 메모리 특성은 누적합 같은 전처리 패턴에서 특히 강합니다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> buildPrefixSum(const vector<int>& arr) {
vector<int> pref = {0};
int running = 0;
for (int x : arr) {
running += x;
pref.push_back(running);
}
return pref;
}
int rangeSum(const vector<int>& pref, int l, int r) {
return pref[r + 1] - pref[l];
}
int main() {
vector<int> arr = {3, 1, 4, 1, 5, 9};
vector<int> pref = buildPrefixSum(arr);
cout << rangeSum(pref, 1, 3) << "\n";
cout << rangeSum(pref, 2, 5) << "\n";
return 0;
}import java.util.ArrayList;
import java.util.List;
public class Main {
static List<Integer> buildPrefixSum(int[] arr) {
List<Integer> pref = new ArrayList<>();
pref.add(0);
int running = 0;
for (int x : arr) {
running += x;
pref.add(running);
}
return pref;
}
static int rangeSum(List<Integer> pref, int l, int r) {
return pref.get(r + 1) - pref.get(l);
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9};
List<Integer> pref = buildPrefixSum(arr);
System.out.println(rangeSum(pref, 1, 3));
System.out.println(rangeSum(pref, 2, 5));
}
}def build_prefix_sum(arr):
pref = [0]
running = 0
for x in arr:
running += x
pref.append(running)
return pref
def range_sum(pref, l, r):
return pref[r + 1] - pref[l]
arr = [3, 1, 4, 1, 5, 9]
pref = build_prefix_sum(arr)
print(range_sum(pref, 1, 3))
print(range_sum(pref, 2, 5))fn build_prefix_sum(arr: &[i32]) -> Vec<i32> {
let mut pref = vec![0];
let mut running = 0;
for &x in arr {
running += x;
pref.push(running);
}
pref
}
fn range_sum(pref: &[i32], l: usize, r: usize) -> i32 {
pref[r + 1] - pref[l]
}
fn main() {
let arr = [3, 1, 4, 1, 5, 9];
let pref = build_prefix_sum(&arr);
println!("{}", range_sum(&pref, 1, 3));
println!("{}", range_sum(&pref, 2, 5));
}배열 메모리 모델 동작 삽입/삭제 재확인
누적합은 여러 번의 구간 합 질의를 빠르게 처리하는 전처리입니다.
한 번 전처리하면 각 질의를 O(1)로 처리할 수 있어 조회 중심 문제에서 매우 효과적입니다.
- 평균 시간복잡도: 전처리
O(N), 질의O(1) - 최악 시간복잡도: 전처리
O(N), 질의O(1) - 추가 공간복잡도:
O(N)
활용 확장 포인트
배열 전처리 패턴은 다양한 문제로 확장됩니다.
- 누적합(prefix sum): 반복 구간 합 조회
- 차분 배열(difference array): 구간 업데이트를 모아 반영
- 슬라이딩 윈도우: 고정 길이 구간 최적화
- Fenwick/세그먼트 트리: 조회와 업데이트를 함께 처리
핵심은 배열을 단순 저장소가 아니라 전처리 중심 문제 해결 도구로 바라보는 것입니다.
실패사례 추가
배열만 고집하면 다음 반례에서 성능이 급격히 악화됩니다.
- 중간 삽입/삭제가 매우 자주 발생하는 경우
pop(0)를 반복하는 큐 패턴- 크기 확장이 연속으로 발생하는 대량 삽입
- 업데이트와 조회가 동시에 많은 동적 질의
이 경우 배열 단독보다 deque나 트리 기반 구조를 함께 고려해야 합니다.
구조 판정 요약
배열은 조회와 전처리 조합에서 강합니다.
반대로 수정이 자주 일어나는 작업에서는 비용 누적이 빠르게 커집니다.
따라서 입력 분포를 먼저 추정하고, 그 분포에 맞는 자료구조를 선택해야 안정적인 성능을 얻습니다.
반례/실수 체크리스트
배열 사용 시 자주 발생하는 실수 패턴입니다.
- 중간 삽입/삭제가 반복되는데도 배열만 유지하는 경우
- 파이썬 리스트를 큐처럼
pop(0)로 반복 사용하는 경우 - 동적 확장 비용을 무시하고 대량 삽입을 연속 수행하는 경우
- 범위 합 질의를 매번 선형 스캔으로 처리하는 경우
배열을 기본 구조로 쓰더라도 반례를 먼저 점검하면 제출 실패와 성능 이슈를 크게 줄일 수 있습니다.
배열 선택 비용 모델 정리
| 연산 | 평균 시간 | 최악 시간 | 핵심 리스크 |
|---|---|---|---|
| 인덱스 조회 | O(1) | O(1) | 경계 체크 누락 |
| 맨 뒤 삽입 | O(1) | O(N) | 리사이즈 시 복사 비용 |
| 중간 삽입/삭제 | O(N) | O(N) | 이동 비용 누적 |
평균 성능만 보지 말고 최악 시나리오(리사이즈, 대량 이동)까지 함께 확인해야 합니다.
체크포인트
- 파이썬 리스트는 동적 배열이지 링크드 리스트가 아님
pop(0)는O(N)이므로 큐 용도는deque가 적합- 입력 크기와 I/O 비용을 함께 고려해야 체감 성능이 맞음
- 큰 입력에서는 캐시 지역성과 상수 비용도 함께 점검
배열 구현 점검 체크리스트
- 문제 요구가 조회 중심인지 수정 중심인지 먼저 분류했는가
- 중간 삽입/삭제 빈도를 입력 범위와 함께 추정했는가
- 누적합 같은 전처리로 질의 비용을 줄일 수 있는가
- 대체 구조(
deque, 트리 기반 구조)를 비교해 보았는가
선형 메모리 모델 정리
배열은 단순한 기본 구조가 아니라 조회 중심 문제에 최적화된 구조입니다.
조회 패턴에서는 매우 강력하지만, 수정 패턴에서는 비용이 급격히 늘 수 있으므로 입력 분포에 맞게 선택해야 합니다.
배열 실패 로그 점검
오답 -> 디버깅 -> 교정 -> 검증 흐름으로 체크하면 인덱스 경계나 이동 비용 계산 오류를 빠르게 찾을 수 있습니다.
배열을 계속 쓸지 다른 자료구조로 전환할지는 입력 분포(조회 중심인지, 중간 삽입/삭제 중심인지)와 상충 지점를 함께 비교해 결정해야 합니다.
배열을 사용할 때 마지막 점검으로 아래 항목을 확인합니다.
- 중간 삽입/삭제가 반복되는데도 배열만 고집하는 경우
- 파이썬 리스트를 큐처럼
pop(0)로 반복 사용하는 경우 - 동적 확장 비용을 무시하고 대량 삽입을 연속으로 수행하는 경우
- 범위 합 질의를 매번 선형 스캔으로 처리하는 경우