[코딩 테스트 합격자 되기 C++ 편] 05 배열

05-1 배열 개념

같은 타입의 변수가 여러 개 필요한 경우 자주 사용. 인덱스로 원하는 데이터에 임의 접근할 수 있다는 장점이 있다.

배열 선언

선언 : int a[10]; 와 같이 배열의 크기를 [ ] 연산자를 이용해 명시적으로 표시해주면 된다.

 

일반적인 방법

int main()
{
    int arr1[] = {1,2,3,4,5};   // 배열 내 원소 : 1 2 3 4 5, 크기 : 5
    int arr2[5] = {1,2};        // 배열 내 원소 : 1 2 0 0 0, 크기 : 5
    int arr3[5] = {};           // 배열 내 원소 : 0 0 0 0 0, 크기 : 5
    int arr4[5];                // 배열 내 원소가 쓰레기 값으로 되어 있음. 크기 : 5

    return 0;
}

 

배열과 차원

n차원 배열을 사용할 때도 많은데, 컴퓨터 메모리에 저장될 때는 차원과는 무관하게 메모리에 연속 할당된다.

 

배열의 접근 및 제어

변수명 앞에 &을 붙이면 해당 변수의 주소값을 연산한다. 해당 연산자를 통해 알아낼 수 있는 메모리 주소값은 연속적임을 코드를 수행해보면 알 수 있다.

#include <iostream>

int main()
{
    int intArray[3] = {1, 2, 3};

    for(int index = 0; index < 3; ++index)
    {
        cout << intArray[index] << endl;
    }
    
    double doubleArray[3] = {1.1, 2.2, 3.3};
    
    for(int index = 0; index < 3; ++index)
    {
        cout << doubleArray[index] << endl;
    }

    char charArray[3] = {'a', 'b', 'c'};
    
    for(int index = 0; index < 3; ++index)
    {
        cout << charArray[index] << endl;
    }

    return 0;
}

 

메모리 주소가 연속적이라는 특징이 있어 배열은 인덱스를 활용하여 특정 원소에 임의 접근(random access)할 수 있다.

 

2차원 배열

2차원 배열은 1차원 배열을 확장한 것으로 다음과 같이 사용할 수 있다.

1차원 배열과 비슷하게 행과 열을 명시하여 [ ] 연산자를 2개 연이어 사용한다는 점만 주의하면 된다.

#include <iostream>

int main()
{
    int arr[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};

    cout << arr[2][3] << endl;  // arr[2][3]에 저장된 값 출력. 12
    arr[2][3] = 15;
    cout << arr[2][3] << endl;  // arr[2][3]에 저장된 값 출력. 15
    
    return 0;
}

실제 메모리에 2차원 배열이 저장된 모습

05-2 배열의 효율성

배열 연산의 시간 복잡도

"배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근할 수 있습니다. 따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)입니다."

 

맨 뒤에 삽입할 경우

시간 복잡도 O(1) : 임의 접근이 가능하다는 점과 맨 뒤이기에 다른 데이터의 위치에 영향을 주지 않는다는 점 

 

맨 앞에 삽입할 경우

시간 복잡도 O(N) : 임의 접근은 가능하지만 기존의 모든 데이터가 N개인 경우 한 칸씩 미는 연산이 N번 수행되어야 하기 때문에 O(N)이다.

 

중간에 삽입할 경우

시간 복잡도 O(N) : 중간 위치에 임의 접근은 가능하지만, 중간 뒤에 있는 데이터가 N개라 할 때, 한 칸씩 미는 연산이 N번 수행되어야 하기 때문에 O(N)이다.

 

배열을 선택할 때 고려할 점

데이터에 자주 접근하거나 읽어야 하는 경우 배열을 사용하면 좋은 성능을 낼 수 이?ㅆ다.

 

ex) 그래프 표현 시, 배열을 활용하면 임의 접근이 가능하므로 간선 여부를 시간 복잡도 O(1)로 판단할 수 있다.

 

하지만, 배열은 메모리 공간을 충분히 확보해야 한다는 단점도 있다.

 

다음의 2가지 사항을 고려해서 배열을 선택할 것을 권장한다.

 

1. 할당할 수 있는 메모리 크기를 확인해야 한다. 데이터의 크기가 너무 크면 런타임에서 배열 할당에 실패할 수 있다.

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