[C++] 코딩테스트에서의 배열

1개요

배열은 동일한 타입의 원소들을 연속된 메모리 공간에 저장하는 가장 기본적인 자료구조다. 인덱스로 O(1) 접근이 가능하지만, 삽입 위치에 따라 시간 복잡도가 크게 달라진다. 맨 뒤 삽입은 O(1)이지만 맨 앞 삽입은 O(N)이 된다. 이 차이를 이해하면 어떤 자료구조를 선택해야 할지 판단하는 기준이 생긴다.

---

2배열의 세 가지 특징

1

동질성: 배열의 모든 원소는 동일한 타입이어야 한다. 정수형 배열이면 모든 원소가 int, 문자형 배열이면 모든 원소가 char다.

2

연속된 메모리 할당: 원소들이 메모리상에 연속적으로 배치된다. 단편화 문제가 적고, CPU 캐시를 효율적으로 활용할 수 있어 접근 속도가 빠르다.

3

인덱스 기반 접근: 첫 번째 원소는 인덱스 0. arr[i]처럼 어떤 위치든 O(1) 상수 시간에 직접 접근할 수 있다.

int arr[5] = {10, 20, 30, 40, 50} — 메모리 배치

arr[0]

10

0x...b0

arr[1]

20

0x...b4

arr[2]

30

0x...b8

arr[3]

40

0x...bc

arr[4]

50

0x...c0

int형 원소 하나는 4바이트이므로 주소가 4씩 증가하는 것을 확인할 수 있다.

---

3배열 선언 및 초기화 — 1차원

선언 문법은 data_type array_name[size]다. 초기화 방식에 따라 동작이 달라지므로 주의해야 한다.

초기화 없이 선언

쓰레기값(Garbage Value)이 들어간다. 실행할 때마다 값이 달라지므로 반드시 초기화해야 한다.

전체 초기화

int arr[5] = {1,2,3,4,5}
앞에서부터 순서대로 값이 채워진다.

부분 초기화

int arr[5] = {1,2,3}
지정한 값 이후 나머지는 0으로 자동 초기화된다.

전체 0 초기화

int arr[5] = {0} 또는 int arr[5] = {}
모든 원소를 0으로 빠르게 초기화하는 관용 표현이다.

주의: 초기화하지 않고 선언만 한 배열을 그대로 사용하면 쓰레기값이 출력된다. 코딩 테스트에서 원인 모를 오답의 주범이 될 수 있으므로, 선언과 동시에 초기화하는 습관을 들이자.

---

42차원 배열 선언 및 메모리 구조

2차원 배열은 1차원 배열을 여러 개 묶어 놓은 형태로, int arr[2][3]처럼 행(row)과 열(col) 크기를 함께 명시한다.

int arr[2][3] = {{1,2,3},{4,5,6}} — 논리 구조

[0]

[1]

[2]

행 0

1

2

3

행 1

4

5

6

행 우선(Row-Major) 저장: C++에서 2차원 배열은 내부적으로 1행 전체 → 2행 전체 순서로 연속 메모리에 저장된다. 즉 arr[0][0], arr[0][1], arr[0][2], arr[1][0], arr[1][1], arr[1][2] 순으로 배치된다. 2차원처럼 보여도 메모리는 항상 1차원이다.

int arr[2][3] = {
    {1, 2, 3},   // 0행
    {4, 5, 6}    // 1행
};
// 메모리: [1][2][3][4][5][6] 연속 배치
// arr[1][0]의 주소 = arr[0][0]의 주소 + (3 * sizeof(int))

---

5삽입 위치에 따른 시간 복잡도 차이

배열은 연속 메모리 구조이기 때문에 삽입 위치에 따라 성능이 크게 달라진다.

맨 뒤 삽입  O(1)

가장 효율적

기존 원소를 전혀 건드리지 않고 다음 빈 자리에 바로 추가. 다른 원소 이동이 없으므로 상수 시간.

맨 앞 삽입  O(N)

가장 비효율적

기존 원소 전체를 한 칸씩 뒤로 밀어야 한다. 원소가 N개면 N번의 이동이 필요.

맨 뒤 삽입 — arr[size]에 바로 대입

1

3

5

99

← 한 번에 추가 O(1)

맨 앞 삽입 — 기존 원소 전체 이동

2

1

3

5

7

9

← 5번 이동 후 삽입 O(N)

맨 뒤 vs 맨 앞 삽입 — 원소 수별 연산 횟수

맨 뒤 삽입 — O(1) 맨 앞 삽입 — O(N)

// 맨 뒤 삽입 — O(1)
if (size < capacity) {
    arr[size] = newValue;  // 그냥 넣기만 하면 끝
    size++;
}

// 맨 앞 삽입 — O(N)
for (int i = size - 1; i >= 0; i--)
    arr[i + 1] = arr[i];  // 전체를 한 칸씩 뒤로
arr[0] = newValue;
size++;

---

6실전 문제 — 배열 활용 패턴 3가지

① 배열 제어하기 — 중복 제거 + 내림차순 정렬

핵심 아이디어: sort()로 내림차순 정렬 후 unique()로 연속된 중복값을 뒤로 밀고, erase()로 제거한다. unique()는 정렬된 배열에서만 올바르게 동작하므로 순서가 중요하다.

bool compare(int a, int b) { return a > b; }  // 내림차순 기준

vector<int> solution(vector<int> lst) {
    sort(lst.begin(), lst.end(), compare);       // 내림차순 정렬
    lst.erase(unique(lst.begin(), lst.end()),    // 중복 제거
               lst.end());
    return lst;
}
// {4,2,2,1,1,3,4} → {4,3,2,1}

② 두 수를 뽑아서 더하기 — set으로 중복 없는 합 수집

핵심 아이디어: set<int>에 두 원소의 합을 삽입하면 중복이 자동 제거되고 오름차순 정렬도 자동으로 된다. 이중 루프로 모든 쌍을 순회하면 O(N²).

vector<int> solution(vector<int> numbers) {
    set<int> sum;
    for (int i = 0; i < numbers.size(); ++i)
        for (int j = i + 1; j < numbers.size(); ++j)
            sum.insert(numbers[i] + numbers[j]);  // set이 중복+정렬 처리
    return vector<int>(sum.begin(), sum.end());
}
// {2,1,3,4,1} → {2,3,4,5,6,7}

③ 모의고사 — 패턴 배열 + 나머지 연산

핵심 아이디어: 각 수포자의 반복 패턴을 배열로 정의하고 i % pattern.size()로 패턴을 순환시킨다. 맞힌 횟수를 비교해 최댓값과 동률인 사람을 모두 반환한다.

vector<int> p1 = {1,2,3,4,5};
vector<int> p2 = {2,1,2,3,2,4,2,5};
vector<int> p3 = {3,3,1,1,2,2,4,4,5,5};

for (int i = 0; i < answers.size(); i++) {
    if (answers[i] == p1[i % p1.size()]) cnt[0]++;
    if (answers[i] == p2[i % p2.size()]) cnt[1]++;
    if (answers[i] == p3[i % p3.size()]) cnt[2]++;
}
// i % size() 로 패턴을 무한 반복시키는 것이 핵심

---

7한눈에 보는 정리

연산	시간 복잡도	이유
임의 접근 arr[i]	O(1)	시작 주소 + i × 타입 크기로 직접 계산
맨 뒤 삽입/삭제	O(1)	다른 원소 이동 없음
중간/맨 앞 삽입/삭제	O(N)	이후 원소들을 전부 밀거나 당겨야 함
선형 탐색	O(N)	최악의 경우 모든 원소를 순회
크기 변경	불가	C++ 정적 배열은 선언 시 크기 고정

---

8오늘의 회고

이번 챕터에서 가장 인상 깊었던 건 2차원 배열도 메모리상에서는 1차원으로 저장된다는 사실이었다. 행 우선 순서로 연속 배치된다는 것을 이해하니, 2차원 배열의 열(col) 방향 순회가 왜 행(row) 방향 순회보다 느린지 — 캐시 미스가 더 자주 발생하기 때문 — 까지 자연스럽게 이해됐다.

맨 앞 삽입이 O(N)이라는 사실을 단순히 외우는 것에서 끝내지 않고, 연속 메모리 구조상 앞의 빈 공간이 없기 때문에 전체를 밀어야 한다는 이유를 이해한 것이 중요했다. 앞쪽 삽입/삭제가 잦은 경우에는 배열 대신 deque를 선택해야 한다는 판단 기준도 이 이해에서 나온다.