(C) 다차원 배열 편하게 malloc하기

백준 블로그는 처음이네요! 어떤 소재를 올리는 게 좋을지 모르겠어서 일단 제 다른 블로그에 올린 글에서 소재를 빼와서 쓰려고 합니다. C++에서는 쓸 수 없고 컴파일러도 맞아야 되기 때문에 유용할지는 모르겠네요.

보통 코드를 C로 짤 때는 아래와 같이 다차원 배열을 할당받습니다.

void version1(int h, int w) {
    int **array_2d = malloc(h * sizeof(int *));
    for(int i = 0; i < h; i++)
        array_2d[i] = malloc(w * sizeof(int *));

    // ...

    for(int i = 0; i < h; i++)
        free(array_2d[i]);
    free(array_2d);
}

이렇게 짜면 malloc/free 호출을 $O(h)$번씩 해야 하고 for문도 두 번씩 써야 해서 귀찮습니다(3차원 이상이면 더 늘어납니다). 그런데 이 방법을 사용하면 별도의 귀찮은 과정 없이 malloc 한 번으로 다차원 배열을 할당받을 수 있습니다.

모든 환경에서 가능한 것은 아니고, VLA를 지원하는 C 컴파일러(GCC, clang 등)가 필요합니다. 백준에서 사용하는 컴파일러는 모두 VLA를 지원하지만, 아쉽게도 Visual Studio에서는 지원하지 않습니다.

void version2(int h, int w) {
    int (*array_2d)[w] = malloc(h * sizeof *array_2d);
    // 혹은 malloc(h * sizeof(int [w]))
    // 혹은 malloc(h * w * sizeof(int)). 혹시 UB의 소지가 있다면 알려주세요

    // ...

    free(array_2d);
}

...생소한 문법이 한 줄에 3번이나 나오긴 하네요. 하나씩 설명드리겠습니다.

해설

위 코드에서 가장 의아해 보이는 부분 3가지를 꼽자면 아마 이렇게 될 것 같습니다.

  • int (*array_2d)[w]???
  • 배열 길이에 변수가 들어간다고???
  • sizeof에 괄호가 없다고???

먼저 int (*array_2d)[w];int의 (길이가 w인) 배열의 포인터 array_2d를 선언하는 선언문입니다. 함수 포인터(int (*fn_ptr)(int);의 형태였죠)를 배운 적이 있다면 그것과 같은 원리입니다. 단지 포인터가 가리키는 것이 함수에서 배열로 바뀐 것뿐입니다.

쉽게 이해할 수 있도록 1차원 배열의 경우와 비교해 보자면 이렇게 됩니다. "int"가 "int의 배열"로 바뀌는 것에 주목해 주세요.

  • int *array_1d = malloc(n * sizeof(int));int의 포인터int n개 분량의 공간을 할당해 주는 코드입니다.
  • int (*array_2d)[w] = malloc(n * sizeof(int [m]));int의 배열의 포인터int의 배열 n개 분량의 공간을 할당해 주는 코드입니다.

포인터는 배열처럼 []을 통해 n번째 원소에 접근할 수 있고 할당받은 것의 타입은 int의 배열의 포인터이니, 이 공간은 int의 배열의 배열, 즉 2차원 배열처럼 쓸 수 있습니다. (int의 배열)의 포인터인데 왜 헷갈리게 *[w]보다 안에 있냐면... 원래 C가 그렇습니다. 원본 글에 이 얘기를 하는 문단이 있는데 도움이 될까 싶네요.

배열 길이에 변수가 들어가는 것도 의아해 보일 수 있는데, 이건 아까 언급한 VLA(variable-length array), 즉 길이가 런타임에 정해지는 배열입니다. 엄연히 C99부터 생긴 표준 문법이지만(C++에서는 지원하지 않습니다), 필수 구현 사항은 아니기 때문에 Visual Studio 컴파일러처럼 지원하지 않는 컴파일러가 있습니다. 배열 길이가 문제 전체에서 상수라면 VLA 지원이 없어도 위의 트릭을 쓸 수 있습니다(예를 들어 int (*array_2d)[3]).

위의 두 개에 비하면 조금 사소하지만, sizeofsizeof(타입) 형태뿐만 아니라 sizeof 표현식 형태로도 쓸 수 있고 후자의 경우에는 괄호가 필요 없습니다. 저는 PS를 할 때 변수명을 짧게 쓰기 때문에 sizeof *a라고 쓰면 sizeof(int [m])보다 글자 수가 적어지는 장점도 있지만, 굳이 PS가 아니더라도 갑작스럽게 타입을 바꿔야 할 때 수정할 것이 적어진다는 장점이 있습니다(이 블로그에서 읽었던 내용입니다).

예제

7568번 문제: 덩치는 이렇게 풀 수 있습니다. 혹시 모를 복붙을 방지하기 위해 두 줄을 지웠습니다.

int main(void) {
    int n;
    scanf("%d", &n);
    int (*arr)[2] = malloc(n * sizeof *arr);
    for(int i = 0; i < n; i++)
        scanf("%d %d", &arr[i][0], &arr[i][1]);
    for(int i = 0; i < n; i++) {
        int k = 0;
        // ❓
        printf("%d ", k + 1);
    }
}

3차원 이상의 배열이 필요할 때를 대비해서 다른 예를 들어보자면 7569번 문제: 토마토에서는 토마토 창고를 이렇게 선언할 수 있습니다.

int main(void) {
    int m, n, h;
    scanf("%d %d %d", &m, &n, &h);
    int (*tomato)[n][m] = malloc(h * sizeof *tomato);

    // ...
}

더 극단적인 예가 필요하다면 17114번 문제: 하이퍼 토마토의 11차원 토마토 창고는 이렇게 선언할 수 있습니다.

int (*tomato)[v][u][t][s][r][q][p][o][n][m] = malloc(w * sizeof *tomato);

도움이 되셨으면 좋겠습니다. 읽어주셔서 감사합니다 🙇


댓글 (1개) 댓글 쓰기


rhdqor213 2달 전

다차원 동적 배열 쓸 일이 생기면 아예 1차원 배열에서 N_1, N_2, N_3... 끼리 곱하고 계산해서 썼는데 이런 방법도 있었네요! 흥미롭게 읽었습니다. 감사합니다.