[C/C++] 동적 2차원 배열과 가변길이배열(VLA)

C언어의 표준에서는 고정된 크기의 배열을 선언할 때 배열의 크기를 컴파일 시간에 알 수 있어야 했다.

그렇기 때문에 C99 표준 이전에는 배열의 크기로 변수를 사용하는 것이 허용되지 않았다.

 

하지만 C99부터는 '가변 길이 배열'(Variable Length Arrays, VLAs)의 개념이 도입되어 실행 시간에 배열의 크기를 결정할 수 있게 되었습니다. 즉, 배열의 사이즈에 변수가 들어가도 됐다.

 

그 이전에는 동적할당을 이용하여, 이 문제를 해결했다.

 

아래는 VLA 를 사용하여 입력받은 높이와 너비에 해당하는 사각형을 숫자로 채우는 코드이다.

#include <cstdio>

int main(){
    int n;
    int m;
    while (1){
        scanf("%d",&n);
        scanf("%d",&m);
        if ( n > 0 && m > 0 && n <= 100 && m <= 100) break;
        else printf("INPUT ERROR!\n");
    }

    int arr[n][m];
    int num = 1;
    for ( int i = 0; i < n; i++){
        for ( int j = 0; j < m; j++){
            if ( i%2 == 0 ) arr[i][j] = num++;
            else arr[i][m-1 -j] = num ++;
        }
    }

    for (int i = 0; i < n; i++){
        for ( int j = 0; j < m; j++){
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

입력으로 4 와 5를 넣으면 아래와 같이 출력된다.

 

 

이 코드를 VLA 를 사용하지 않고 바꿔보자.

 

동적할당을 이용해 2차원 배열을 만드는 방법 중 하나는 아래와 같이 엘리베이터 처럼 구현 하는 것이다.

이중포인터에 익숙하지 않은 사람들은, M에 대한 동적할당을 먼저 본 후에 N에 대한 동적할당을 보기 바란다.

N의 각 요소들은 각 M할당(배열)의 첫번째 요소의 주소를 가리키는 포인터의 주소를 값으로 가진다.

 

따라서 코드는 아래와 같다. ( 항상 메모리 할당 해제의 주의하자.)

#include <cstdio>
#include <cstdlib>

int main() {
    int n, m;
    while (1) {
        scanf("%d", &n);
        scanf("%d", &m);
        if (n > 0 && m > 0 && n <= 100 && m <= 100) break;
        else printf("INPUT ERROR!\n");
    }

    // 동적으로 2차원 배열을 생성합니다.
    int **arr = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        arr[i] = (int*)malloc(m * sizeof(int));
    }

    int num = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i % 2 == 0) arr[i][j] = num++;
            else arr[i][m - 1 - j] = num++;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }

    // 할당된 메모리를 해제합니다.
    for (int i = 0; i < n; i++) {
        free(arr[i]);
    }
    free(arr);

    return 0;
}

 

배열과 포인터 사이의 관계를 좀 더 명확히 보고 싶다면 아래와 같이 작성해도 문제 없다.

    int **arr = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        *(arr+i) = (int*)malloc(m * sizeof(int));
    }

    int num = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i % 2 == 0) *(*(arr+i)+j) = num++;
            else *(*(arr+i)+(m-1-j)) = num++;
        }
    }

 

또 다른 기법도 존재한다.

 

하나의 malloc 호출을 사용하여 모든 행과 열에 대한 메모리를 연속적으로 할당하는 것이다.

 

먼저 전체 배열에 대한 메모리를 할당하고, 그 다음에는 각 행의 시작점을 가리키는 포인터 배열을 할당한다.

    // 전체 2차원 배열에 대한 메모리를 한 번에 할당합니다.
    int *data = (int *)malloc(n * m * sizeof(int));
    // 각 행의 시작점을 가리키는 포인터 배열을 할당합니다.
    int **arr = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        arr[i] = data + i * m;
    }

    int num = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i % 2 == 0) arr[i][j] = num++;
            else arr[i][m - 1 - j] = num++;
        }
    }
    
    ....
    
    free(data)
    free(arr)

 

기존에는 malloc 을 여러번 호출하여 '행 단위로' 데이터를 동적할당했다면, 이 경우에는 행과 열에 해당하는 모든 데이터를 malloc 호출 한번으로 할당한다. (인덱싱에 사용된 malloc 호출을 말하고자 하는게 아니다)

 

첫 번째 방식인 malloc 을 여러번 사용하여 행 단위 데이터를 동적할당하는 방식은 아래와 같은 특징이 있다.

 

• 유연성: 각 행마다 다른 크기의 메모리를 할당할 수 있어서, 모든 행이 동일한 열 수를 가질 필요가 없는 비균일 배열을 쉽게 구현할 수 있다.
• 메모리 단편화: 여러 메모리 할당이 이루어지기 때문에 메모리 단편화의 가능성이 더 높다. 이는 장기간 실행되는 프로그램에서 성능 저하로 이어질 수 있다.
• 메모리 오버헤드: 각 행마다 별도의 메모리 할당이 이루어지기 때문에, 메모리 관리에 추가적인 오버헤드가 발생할 수 있다. 이는 할당된 각 메모리 블록의 메타데이터 관리에 필요한 추가 공간 때문이다.
• 관리의 복잡성: 메모리 해제 시 각 행에 대한 free 호출이 필요하기 때문에, 메모리 누수를 방지하기 위해 더 주의 깊은 관리가 요구된다.

 

반면 두번째 방식인 하나의 malloc 으로 모든 데이터를 할당하는 방식은 아래와 같은 특징이 있다.

• 메모리 단편화 감소: 전체 배열에 대한 메모리가 연속적으로 할당되기 때문에, 메모리 단편화가 적게 발생한다. 메모리 단편화는 할당된 메모리 블록 사이에 사용되지 않는 작은 공간이 생기는 현상을 말한다. 연속적인 메모리 할당은 이러한 공간을 최소화한다.
• 효율적인 메모리 접근: 메모리가 연속적으로 할당되므로 CPU 캐시 효율이 개선될 수 있다. 이는 특히 배열을 순차적으로 접근할 때 성능 이점을 제공한다.
• 관리의 단순성: 메모리 할당과 해제 과정이 간단해진다. 전체 배열에 대해 하나의 malloc과 하나의 free 호출만 필요하기 때문에, 메모리 누수의 가능성을 줄일 수 있다.