int[] fixedArray = new int[1000];
var dynamicArray = new List<int>();

fixedArray[3] = 10;  // O(1)
dynamicArray.Add(10); // 평균 O(1)

구조

배열은 같은 타입의 값을 고정된 길이의 index 슬롯에 저장합니다. 인덱스 i를 바로 지정할 수 있기 때문에 arr[i] 접근은 O(1)입니다. 이 장점 때문에 코테에서 입력 크기가 크고, 위치 기반 접근이 많으면 배열이 가장 단순하고 빠른 선택입니다.

int[] count = new int[100001];

foreach (int value in numbers)
{
    count[value]++;
}

List<T>는 내부적으로 배열을 들고 있는 동적 배열입니다. 공간이 부족해지면 더 큰 배열을 새로 만들고 기존 값을 복사합니다. 그래서 Add는 매번 O(1)은 아니지만, 여러 번 평균을 내면 O(1)에 가깝게 봅니다.

C++ std::vector도 같은 동적 배열 계열입니다. size()는 실제 원소 수, capacity()는 재할당 없이 담을 수 있는 공간이며 reserve(n)은 원소 수를 늘리지 않고 capacity만 확보합니다. Capacity를 넘는 삽입으로 재할당되면 기존 원소를 가리키던 pointer·reference·iterator가 무효화될 수 있습니다.

Count와 Capacity

Count는 실제 원소 수이고, Capacity는 재할당 없이 담을 수 있는 내부 배열의 길이입니다. 입력 크기를 알고 있고 많은 값을 추가할 때는 처음부터 용량을 잡아 불필요한 복사를 줄일 수 있습니다.

int expectedCount = 100_000;
var values = new List<int>(expectedCount);

values.AddRange(new[] { 4, 8, 15 });
// Count: 3, Capacity: expectedCount 이상

values.EnsureCapacity(200_000); // 최소 이 크기까지 확보하고, 실제 Capacity를 반환

Capacity를 작게 다시 지정하거나 TrimExcess()를 호출하면 내부 배열을 다시 만들 수 있습니다. 코딩 테스트처럼 한 번 채운 뒤 읽는 흐름에서는 보통 조절할 필요가 없고, 정확한 입력 크기를 알 때 생성자 용량만 주는 편이 충분합니다.

중간 삽입은 싸지 않다

배열과 동적 배열은 중간 삽입·삭제가 약합니다. 중간에 값을 넣으면 뒤의 원소를 한 칸씩 밀어야 하고, 삭제하면 다시 앞으로 당겨야 합니다.

var list = new List<int> { 1, 2, 3, 4 };
list.Insert(1, 99); // 2, 3, 4를 뒤로 이동
list.RemoveAt(2);   // 뒤 원소를 앞으로 이동

이 작업이 반복되면 전체가 O(n²)이 될 수 있습니다.

Remove(value)는 같은 값이 여러 개여도 첫 번째 일치 항목 하나만 지웁니다. 위치가 이미 정해졌다면 RemoveAt(index)를 쓰되, 둘 다 이동 비용은 O(n)입니다.

2차원 배열 모양

행마다 열 수가 같고 직사각형 좌표를 쓸 때는 int[,]가 읽기 쉽습니다. 행마다 길이가 달라질 수 있거나 각 행을 따로 만들고 싶으면 int[][]를 씁니다.

int[,] board = new int[3, 4];
int[][] adjacency =
{
    new[] { 1, 2 },
    new[] { 0 },
    Array.Empty<int>()
};

board[2, 3] = 1;
int firstNeighbor = adjacency[0][0];

int[][]는 바깥 배열만 먼저 만들어도 되므로 각 행을 반드시 초기화해야 합니다. 격자 크기가 고정된 문제에는 int[,] 또는 행 길이가 같은 int[][] 중 팀의 좌표 표기 관례에 맞는 형태를 고르면 됩니다.

선택 기준

코테에서는 값 범위가 작으면 배열을 해시처럼 쓰는 경우가 많습니다.

int[] freq = new int[26];

foreach (char ch in text)
{
    freq[ch - 'a']++;
}

주의할 점