배열 시리즈 글 중 2번째 글입니다.
- 배열에 대해 알아봅시다. 링크
- [현재 글] row major와 column major에 대해 알아봅시다.
- 배열 주요 연산의 복잡도를 알아봅시다. 링크
- dynamic array에 대해 알아봅시다. 링크
배열에서 행 우선 열 우선 방식이 무엇일까요? 다차원 배열에서 연속적인 공간에 원소들을 저장하는 방법을 의미합니다.
아래 그림과 같이 선언되어 있는, 배열이 있다고 해 보겠습니다.
행 우선 방식은 연속적인 메모리 공간에 저장될 때, 1행의 원소들이 나온 다음에, 2행의 원소들이 나옵니다. 즉
- 빠른 행이 먼저 등장합니다.
- 행이 같다면 빠른 열이 먼저 등장합니다.
이를 그림으로 표현해 보겠습니다.
1행의 원소들이 온전히 저장된 다음에, 2행의 원소들이 연속적인 메모리 공간에 저장됩니다.
1행 1열의 1, 1행 2열의 2, 2행 1열의 3, 2행 2열의 4 순서대로 저장이 됩니다.
연속적인 메모리에 어떻게 저장되는지 다른 관점에서, 도식화 한 그림이에요. 1행 먼저 나오고 2행이 먼저 나온다. 이 그림만 넣어두면 이해하기 편하실 거에요. 3차원 배열의 경우에는 어떨까요?
뭔가 복잡해 보이는데요. 3차원 배열은 1차원 배열의 2차원 배열이라 할 수 있습니다. 이렇게 보면 복잡하니, 묶어서 보도록 하지요.
저는 배열 {1, 2}를 x11로, {3, 4}를 x12로, {5, 6}을 x21로, {7, 8}을 x22로 보았습니다. 그렇다면 arr은 array를 모은 2차원 array, {{x11, x12}, {x21, x22}} 라고 할 수 있어요. 그렇다면 그림이 아래와 같이 그려질 겁니다.
메모리 상에는 위 순서대로 저장이 될 겁니다. 이제 묶어진 x11, x12, x21, x22를 풀어놓아야 겠군요.
그러면 이런 그림이 그려집니다. 즉 arr[0]에 있는 1, 2, 3, 4가 나온 다음에 arr[1]에 있는 5, 6, 7, 8이 나오는 셈입니다. 이를 다시 도식화 해서 그려보면 아래와 같습니다.
c, c++의 경우 이 방식으로 배열이 저장된다는 것 알아두시면 좋습니다.
반대로 배열에서 열 우선 방식은 1열에 있는 내용이 나온 다음에, 2열에 있는 내용이 나옵니다.
- 빠른 열이 먼저 등장합니다.
- 열이 같다면 빠른 행이 등장합니다.
이를 그림으로 표현하면 아래와 같습니다.
이제 아래 배열을 보겠습니다.
만약에, 이 배열이 행 우선이 아니라 열 우선 방식으로 저장된다면 어떻게 저장될까요? 먼저 1열부터 나오고, 2열이 나옵니다. 고로 5, 6, 7, 8 순서가 아니라 5, 7, 6, 8 순서대로 나오게 됩니다.
이것이 배열에서 열 우선 방식입니다. 이를 조금 더 보기 쉽게 도식화 시키면 아래 그림과 같습니다.
이러한 방식들을 아는 것이 왜 중요한지, 행렬 곱셈을 구현해 보면서 알아보도록 하겠습니다.