핵심 정리
| 구조 | 접근 | 끝 삽입 | 중간 삽입·삭제 | 크기 |
|---|---|---|---|---|
배열 T[] | O(1) | 불가 | 직접 이동 필요 | 고정 |
List<T> | O(1) | 평균 O(1) | O(n) | 가변 |
| 2차원 배열 | O(1) | 불가 | 구조 변경 어려움 | 고정 |
csharp
int[] fixedArray = new int[1000];
var dynamicArray = new List<int>();
fixedArray[3] = 10; // O(1)
dynamicArray.Add(10); // 평균 O(1)구조
배열은 같은 타입의 값을 연속된 공간에 저장합니다. 인덱스 i의 위치를 바로 계산할 수 있기 때문에 arr[i] 접근은 O(1)입니다. 이 장점 때문에 코테에서 입력 크기가 크고, 위치 기반 접근이 많으면 배열이 가장 단순하고 빠른 선택입니다.
csharp
int[] count = new int[100001];
foreach (int value in numbers)
{
count[value]++;
}List<T>는 내부적으로 배열을 들고 있는 동적 배열입니다. 공간이 부족해지면 더 큰 배열을 새로 만들고 기존 값을 복사합니다. 그래서 Add는 매번 O(1)은 아니지만, 여러 번 평균을 내면 O(1)에 가깝게 봅니다.
중간 삽입은 싸지 않다
배열과 동적 배열은 중간 삽입·삭제가 약합니다. 중간에 값을 넣으면 뒤의 원소를 한 칸씩 밀어야 하고, 삭제하면 다시 앞으로 당겨야 합니다.
csharp
var list = new List<int> { 1, 2, 3, 4 };
list.Insert(1, 99); // 2, 3, 4를 뒤로 이동
list.RemoveAt(2); // 뒤 원소를 앞으로 이동이 작업이 반복되면 전체가 O(n²)이 될 수 있습니다.
선택 기준
| 상황 | 적합한 선택 |
|---|---|
| 크기가 정해져 있음 | 배열 |
| 인덱스로 자주 접근 | 배열 또는 List<T> |
| 끝에 계속 추가 | List<T> |
| 값 범위가 작아 카운팅 가능 | 배열 |
| 중간 삽입·삭제가 많음 | 다른 자료구조 검토 |
| 2D 격자 문제 | 2차원 배열 또는 jagged array |
코테에서는 값 범위가 작으면 배열을 해시처럼 쓰는 경우가 많습니다.
csharp
int[] freq = new int[26];
foreach (char ch in text)
{
freq[ch - 'a']++;
}주의할 점
List<T>는 이름만 리스트일 뿐, 알고리즘 교재의 연결 리스트가 아니라 동적 배열입니다. list.Contains(x)는 보통 O(n)이고, list.Insert(0, x)를 반복하면 매번 원소 이동이 발생합니다.
입력의 최댓값이 큰데 값 범위를 그대로 배열 크기로 잡으면 메모리 제한을 먼저 넘을 수 있습니다. 배열을 카운팅 테이블로 쓰기 전에는 값 범위와 메모리 제한을 함께 계산하세요.
참고 링크
2 sources