[코딩 테스트] C++ 배열 | 선언, 차원, 효율성

이 글은 〈[되기] 코딩 테스트 합격자 되기(C++ 편)〉에서 발췌했습니다.

골든래빗 출판사
박경록 지음

[코딩 테스트] C++ 배열 | 선언, 차원, 효율성

배열은 같은 타입의 원소들을 효율적으로 관리할 수 있는 기본 자료형입니다. 같은 타입의 변수가 여러 개 필요한 경우 자주 사용하죠. 예를 들어 학생 1,000명의 점수를 관리해야 한다고 생각해봅시다. 정수형 변수 1,000개를 선언해서 관리할 수도 있지만 선언하는데 시간도 많이 걸리고 각 변수들을 따로 관리해야 하기 때문에 효율적이지 않습니다. 배열은 하나의 변수 이름으로 동일한 타입의 데이터를 그룹화하여 관리할 수 있고, 인덱스라는 것으로 원하는 데이터에 임의 접근할 수 있다는 장점이 있습니다.

1. 배열 개념

1.1 배열 선언

먼저 배열을 선언하는 법을 알아보겠습니다. 기존 변수를 선언할 때는 int a와 같이 변수의 타입과 이름을 명시했습니다. 배열은 int a[10]과 같이 배열의 크기를 추가로 명시합니다. 다음 코드는 정수형 배열을 선언한 것이고, 정수형 대신 다른 타입이 올 수도 있습니다.

일반적인 방법

#include <iostream>

using namespace std;

int main() {
  int arr1[] = {1, 2, 3, 4, 5}; // 배열 내 원소: 1 2 3 4 5, 크기는 5
  // 첫 두 요소 초기화, 나머지는 0
  int arr2[5] = {1, 2}; // 배열 내 원소 : 1 2 0 0 0
  // 모든 요소를 0으로 초기화
  int arr3[5] = {}; // 배열 내 원소: 0 0 0 0 0
  // 초기화 없이 선언 (초깃값은 정의하지 않음, 출력값은 불확정). 
  int arr4[5]; // 배열 내 원소: 불확정 (쓰레기값)
  return 0;
}

1.2 배열과 차원

배열은 2차원 배열, 3차원 배열과 같이 다차원 배열을 사용할 때도 많습니다. 하지만 컴퓨터 메모리의 구조는 1차원이므로 2차원, 3차원 배열도 실제로는 1차원 공간에 저장합니다. 다시 말해 배열은 차원과는 무관하게 메모리에 연속 할당됩니다.

배열의 접근 및 제어

배열로 선언한 변수들은 메모리의 연속된 공간에 할당됩니다. 따라서 다음 코드를 보면 배열의 원소 간 주소값은 변수 크기만큼 차이납니다. 변수명 앞에 &을 붙이면 해당 변수의 주소값을 연산합니다. 다음 코드를 보면 배열의 각 원소들의 메모리 주소가 연속적이라는 것을 알 수 있습니다.

#include <iostream>

using namespace std;

int main() {
  int intArray[3] = {1, 2, 3};
  double doubleArray[3] = {1.1, 2.2, 3.3};
  char charArray[3] = {'a', 'b', 'c'};

  // int 배열의 주소값, int의 크기는 4바이트이므로 주소가 4씩 증가
  &intArray[0]; // 0x7ffeeef7a8c0
  &intArray[1]; // 0x7ffeeef7a8c4
  &intArray[2]; // 0x7ffeeef7a8c8

  // double 배열의 주소값, double의 크기는 8바이트이므로 주소가 8씩 증가
  &doubleArray[0]; // 0x7ffeeef7a8b0
  &doubleArray[1]; // 0x7ffeeef7a8b8
  &doubleArray[2]; // 0x7ffeeef7a8c0

  // char 배열의 주소값, char의 크기는 1바이트이므로 주소가 1씩 증가
  &charArray[0]; // 0x7ffeeef7a8af
  &charArray[1]; // 0x7ffeeef7a8b0
  &charArray[2]; // 0x7ffeeef7a8b1

  return 0;
}

위 코드에서 intArray를 그림으로 그려보면 다음과 같습니다. 이렇게 메모리 주소가 연속적이라는 특징이 있어 배열은 인덱스를 활용하여 특정 원소에 임의 접근(Random Access)할 수 있습니다.

실제로 인덱스를 활용해서 배열을 제어하는 방법은 다음 코드를 참고해주세요.

#include <iostream>

using namespace std;

int main() {
  // 배열 선언 및 초기화
  int arr[5] = {10, 20, 30, 40, 50};

  // 인덱스를 사용하여 특정 원소 읽기
  cout << "arr[0] = " << arr[0] << endl; // 첫 번째 원소 출력 / arr[0] = 10
  cout << "arr[3] = " << arr[3] << endl; // 네 번째 원소 출력 / arr[3] = 40

  // 인덱스를 사용하여 특정 원소 수정
  arr[2] = 60;
  // 변경 후 배열 상태 : arr = {10, 20, 60, 40, 50}

  return 0;
}

2차원 배열

2차원 배열은 1차원 배열을 확장한 겁니다. C++에서 다음과 같이 사용할 수 있습니다.

#include <iostream>

using namespace std;

int main() {
  int arr[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}; // 2차원 배열 선언
  cout << arr[2][3] << endl; // arr[2][3]에 저장된 값을 출력 / 12
  arr[2][3] = 15; // arr[2][3]에 저장된 값을 15로 변경
  cout << arr[2][3] << endl; // 변경된 값을 출력 / 15

  return 0;
}

2차원 배열 데이터에 접근하는 방법은 1차원 배열과 비슷합니다. 행과 열을 명시해 [ ] 연산자를 2개 연이어 사용한다는 점만 다릅니다.

#include <iostream>

using namespace std;

int main() {
  // 2행 3열 2차원 배열을 표현하는 배열 선언
  int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};
  // 배열 출력을 확인하기 위한 코드
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 3; j++) {
      cout << arr[i][j] << " ";
    }
    cout << endl;
  }
  return 0;
}

이를 그림으로 나타내면 다음과 같습니다.

왼쪽은 2차원 배열을 사람이 이해하기 쉽도록 2차원으로 표현한 것이고, 오른쪽은 실제 메모리에 2차원 배열이 저장된 상태를 표현한 겁니다. 사람이 이해하기에는 왼쪽의 형태로 이해하는 것이 편리하므로 2차원 배열을 왼쪽의 행과 열 공간처럼 표현하는 경우가 많지만 실제로는 오른쪽처럼 0행, 1행 순서로 데이터를 할당해 1차원 공간에 저장합니다. 이런 배열의 특성을 잘 기억해두기 바랍니다.

2. 배열의 효율성

이제 배열 연산의 시간 복잡도를 공부하면서 배열의 효율성을 알아보겠습니다.

2.1 배열의 시간 복잡도

배열 데이터에 접근할 때의 시간 복잡도를 알아봅시다. 배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근할 수 있습니다. 따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)입니다. 배열에 데이터를 추가하는 경우는 어떨까요? 배열은 데이터를 어디에 저장하느냐에 따라 추가 연산에 대한 시간 복잡도가 달라집니다.

※ 삭제 연산의 경우도 추가와 마찬가지의 시간 복잡도를 가집니다.

맨 뒤에 삽입할 경우

다음과 같은 배열이 있을 때 2를 추가한다고 생각해봅시다. 맨 뒤에 삽입할 때는 arr[3]에 임의 접근을 바로 할 수 있으며 데이터를 삽입해도 다른 데이터 위치에 영향을 주지 않습니다. 따라서 시간 복잡도는 O(1)입니다.

맨 앞에 삽입할 경우

데이터를 맨 앞에 삽입한다면 어떨까요? 이 경우 기존 데이터들을 뒤로 한 칸씩 밀어야 합니다. 즉, 데이터를 맨 앞에 삽입한다면 어떨까요? 이 경우 기존 데이터들을 뒤로 한 칸씩 밀어야 합니다. 즉, 미는 연산이 필요합니다. 데이터 개수를 N개로 일반화하면 시간 복잡도는 O(N)이 되겠네요.

중간에 삽입할 경우

중간에 삽입할 경우도 보겠습니다. 5 앞에 데이터를 삽입한다면 5 이후의 데이터를 뒤로 한 칸씩 밀어야 할 겁니다. 다시 말해 현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산을 해야 합니다. 밀어야 하는 데이터 개수가 N개라면 시간 복잡도는 O(N)이겠네요.

2.2 배열을 선택할 때 고려할 점

데이터에 자주 접근하거나 읽어야 하는 경우 배열을 사용하면 좋은 성능을 낼 수 있습니다. 예를들어 그래프를 표현할 때 배열을 활용하면 임의 접근을 할 수 있으므로 간선 여부도 시간 복잡도 O(1)로 판단할 수 있습니다. 하지만 배열은 메모리 공간을 충분히 확보해야 하는 단점도 있습니다. 따라서 코딩 테스트에서는 다음 사항을 고려해 배열을 선택해야 합니다.

할당할 수 있는 메모리 크기를 확인해야 합니다. 배열로 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당에 실패할 수 있습니다. 운영체제마다 배열을 할당할 수 있는 메모리의 한계치는 다르지만 보통은 정수형 1차원 배열은 1,000만 개, 2차원 배열은 3,000 * 3,000 크기를 최대로 생각합니다.

중간에 데이터 삽입이 많은지 확인해야 합니다. 배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아져 실제 시험에서 시간 초과가 발생할 수 있습니다.

※ C++로 코딩 테스트를 풀 때는 직접 배열을 사용하기보다 STL에서 제공하는 벡터를 사용할 것입니다. 배열은 자주 사용하지 않으므로 개념만 이해하고 넘어가기 바랍니다.

저자 박경록

매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.