샷건치며 배우는 자료구조 with C++, 3화

배열에 대해 알아봅시다.

읽어주세요

자료구조를 배우기 위해 위대한 항로(?)를 넘어 여기까지 오신 분들 환영합니다. 본 게시글은 자료구조를 공부하면서 복습 겸 정리하기 위해 작성하였습니다. 개인적으로 강좌 형식 및 장난을 섞어가며 작성하는 걸 좋아하기 때문에 진지한 게시글을 원하신다면 뒤로 가기를 눌러주세요.

C++ 언어를 기반으로 하고 있습니다. 다른 프로그래밍 언어를 사용 중이신 경우 개념(이론)을 배우는 데 큰 문제는 없지만, 실제 코드로 구현할 땐 생각보다 차이가 있을 수 있습니다.

업데이트

1. C 언어 구현 내용 제거
   • 게시글의 내용이 너무 복잡해져 제거하였습니다.

게시글 개선을 위해 임시 숨김 처리

배열

실생활에서 배열이라는 단어를 사용하시나요? 프로그래밍, 수학, 과학 분야를 공부 중이거나 업계에서 일하고 있는 게 아니라면 대부분 들어보지도 사용하지도 않는 단어라고 생각합니다. 그렇기 때문에 배열이라는 개념을 처음 배울 때 많이 낯설고 어렵게 느껴지기도 합니다.

배열^Array은 자료구조에서 가장 기본적이고 널리 사용되는 구조 중 하나로, 동일한 데이터 타입의 요소(1)를 메모리 공간에 순차적으로(연속적으로) 저장하는 방식입니다.

1. 요소^Element는 배열에 할당되어 있는 각 값이나 아이템을 의미합니다. '요소' 대신 '원소'라는 단어를 사용하기도 하는데요 같은 의미입니다.

배열을 중국어로 뭐라고 하는 지 아세요?

중국에서 배열을 수조(数组)라고 표기합니다. 셈 수(数)와 짤 조(组)라는 한자로 이루어져 있습니다. 숫자와 조를 의미하는데요, 조는 그룹^Group을 의미합니다. 즉, 데이터를 그룹화한다는 의미에서 조(组)라는 한자가 사용되었습니다. 배열의 본질적인 특성인 그룹화의 의미가 잘 담겨 있음을 확인할 수 있습니다.

한국과 일본에서는 배열(配列)로 표기합니다. 배치할 배(配)와 나열할 열(列)이라는 한자로 이루어져 있고, 데이터를 나열하여 배치한다는 의미를 갖고 있습니다.

동일한 데이터 타입의 요소를 연속적으로 배치해야 하는 경우로는 무엇이 있을까요? 음... 역시 게임만한 예시가 없는 것 같네요.

여러분이 1인 게임 개발자로 FPS 게임을 만들고 있다고 가정해 봅시다. 그리고 한 라운드 당 100명의 적^Enemy을 관리하고 있다고 하구요. 우리는 아직 자료구조 배열을 배우기 전이기 때문에 적에 해당하는 변수 100개를 만들어 관리하고 있습니다. 100개 정도야 시간이 좀 걸리겠지만 관리하는데 큰 문제는 없어보입니다. 다만 적이 100명이 아니라 1,000명으로 늘어나면 선언하고 사용하는 데 시간이 많이 소요되고 관리하는 데 있어 매우 비효율적입니다. 이럴 때 사용하는 개념이 바로 배열입니다.

배열은 동일한 데이터 타입의 요소를 그룹화할 수 있고 이를 하나의 이름과 인덱스^Index를 통해 원하는 데이터에 바로 접근할 수 있습니다. 일일이 적에 해당하는 변수를 찾아 접근할 필요없이 인덱스와 반복문만 있으면 매우 효율적으로 데이터를 다룰 수 있는 것이죠.

배열의 개념

배열의 특징

• 고정된 크기

  ---

  배열은 선언할 때 크기를 지정하기 때문에 고정된 크기를 갖습니다. 그래서 프로그램 실행 중 중간에 이 크기를 변경할 수 없습니다. 이를 정적 배열이라 합니다.

• 동일한 데이터 타입의 요소

  ---

  배열은 동일한 데이터 타입의 요소만을 가질 수 있습니다. 정수형 배열이면 정수형 데이터만 가질 수 있고, 실수형 배열이면 실수형 데이터만 가질 수 있습니다.

• 연속적인 배치

  ---

  배열의 요소는 메모리 공간에 연속 및 순차적으로 배치됩니다. 따라서 주소 계산이 매우 빠릅니다.

• 인덱스를 통한 접근

  ---

  각 요소의 위치를 의미하는 인덱스를 통해 원하는 데이터에 바로 접근할 수 있습니다.

파이썬의 리스트는 배열이라고 볼 수 없...

파이썬은 기본적으로 배열 개념을 제공하지 않습니다.(1) 그래서 리스트^List를 통해 배열의 개념을 배웁니다. 그런데 일부 게시글을 보면 파이썬의 리스트를 배열과 동일하게 취급하는 경우가 있는 것 같습니다. 파이썬의 리스트는 전통적인 배열 개념과는 다소 다른 특성을 갖고 있기에 동일하다고 보기 애매한 부분이 있습니다.

1. 3.3 버전 이후로 array 내장 모듈 제공 중

일반적으로 배열은 배열의 특징처럼 고정된 크기와 동일한 데이터 타입을 갖습니다. 반면에 파이썬의 리스트는 동적인 크기와 다양한 데이터 타입을 가질 수 있도록 설계되어 있습니다. 파이썬에서 진짜 배열 개념을 원하신다면 array 내장 모듈이나 NumPy 라이브러리를 사용하는 것이 적합합니다.

배열의 선언

C++

RAWstd::array

int main(int argc, char* argv[]) {
    int arr1[5] = { 1, 2, 3, 4, 5 };        // 배열 선언 1: 모든 요소 명시적으로 초기화
    int arr2[5] = { 1, 2, 3, };             // 배열 선언 2: 세 번째 요소까지 초기화 후, 나머지 0으로 초기화
    int arr3[5] = {};                       // 배열 선언 3: 모든 요소 0으로 초기화
    int arr4[] = { 1, 2, 3, 4, 5 };         // 배열 선언 4: 크기 생략 (자동으로 결정됨)

    return 0;
}

C++ 언어에서 배열을 선언할 때 C 언어 방식과 STL 컨테이너를 사용하는 방식, 두 가지가 있습니다.

위 방식은 C 언어에서 사용하던 방식으로, C 언어와의 호환성이 좋고 작성 방식이 친숙하단 장점이 있습니다.

#include <array>

int main(int argc, char* argv[]) {
    std::array<int, 5> arr1;                            // 배열 선언 1: 쓰레기값으로 초기화
    std::array<int, 5> arr2 = {};                       // 배열 선언 2: 모든 요소 0으로 초기화
    std::array<int, 5> arr3 = { 1, 2, 3, 4, 5 };        // 배열 선언 3: 모든 요소 명시적으로 초기화
    std::array<int, 5> arr4 = { 1, 2, 3, };             // 배열 선언 4: 세 번째 요소까지 초기화 후, 나머지 0으로 초기화

    // 배열 선언 후, 0으로 채우기
    std::array<int, 5> arr5;
    arr5.fill(0);

    return 0;
}

STL에서 제공하는 std::array는 C++ 언어에서 배열을 더 안정적으로 사용할 수 있도록 도와줍니다.

꺽쇠 괄호 안에 데이터 타입과 배열의 크기를 명시한 후, 이니셜 라이저를 통해 요소의 값을 초기화할 수 있습니다. 또는, 배열 선언 후 fill() 메서드를 호출하여 원하는 값으로 채울 수 있습니다.

배열의 차원

차원...?

배열에 차원이 있다면 믿으시겠습니까?

사실 차원^Dimension이라는 거창한 단어를 사용해서 좀 심오해진 것 같은데요... 이러한 단어가 붙은 이유는 간단합니다. 배열이 데이터를 저장하고 관리하는 방식이 공간적 구조를 보이기 때문에 그렇습니다. 이 차원이라는 것은 배열이 메모리 상에서 어떻게 구성되어 있는 지 논리적인 모델로 나타내는 구조 개념일 뿐 실제 데이터는 1차원 형태로 데이터가 순차적으로 나열되어 배치됩니다. 왜냐하면 메모리 공간은 차원이 없으니까요.

기본적으로 배열은 다차원 개념을 지원합니다. 우리가 배열의 선언에서 본 배열 선언은 1차원 배열입니다. 선^Line처럼 한 방향으로만 데이터가 배치되죠.

배열은 2차원, 3차원, ..., N차원까지 만들 수 있습니다. 보통 많이 사용한다면 3차원까지 사용하고 그 이상 사용하는 경우는 못 본 것 같습니다.

1차원2차원3차원

1차원

1차원 배열은 선처럼 한 방향으로 데이터가 순차적으로 배치되어 저장됩니다. 선형적인 구조를 보이죠.

1차원 배열의 선언은 배열의 선언 부분을 봐주세요.

2차원

2차원 배열은 엑셀의 시트를 생각하시면 됩니다. (행, 열) 또는 (X, Y)와 같이 구분할 수 있고 표처럼 보이기도 합니다. 평면적인 모습을 보입니다.

#include <array>

int main(int argc, char* argv[]) {
    // 2차원 배열 선언 1
    std::array<std::array<int, 5>, 5> arr1;

    // 2차원 배열 선언 2
    // arr2 = {};로 해도 됨
    std::array<std::array<int, 5>, 5> arr2 = {{
        {},
    }};

    // 2차원 배열 선언 3
    std::array<std::array<int, 5>, 5> arr3 = {{
        {{ 1, 1, 1, 1, 1 }},
        {{ 2, 2, 2, 2, 2 }},
    }};

    // 2차원 배열 선언 4
    std::array<std::array<int, 5>, 5> arr4 = {{
        {{ 1, 1, 1, 1, 1 }},  // 1행
        {{ 2, 2, 2, 2, 2 }},  // 2행
        {{ 3, 3, 3, 3, 3 }},  // 3행
        {{ 4, 4, 4, 4, 4 }},  // 4행
        {{ 5, 5, 5, 5, 5 }}   // 5행
    }};

    return 0;
}

C++ 언어에서 std::array 컨테이너로 2차원 배열을 선언하려면 위 코드 예시와 같이 중첩을 해야합니다. 그리고 이니셜라이저의 방식도 다소 복잡합니다. 생각보다 가독성이 많이 떨어지는 편입니다.

3차원

3차원 배열은 큐브^Cube를 생각하시면 됩니다. (행, 열, 깊이) 또는 (X, Y, Z)로 구분할 수 있습니다.

#include <array>

int main(int argc, char* argv[]) {
    // 3차원 배열 선언 1
    std::array<std::array<std::array<int, 3>, 3>, 3> arr1;

    // 3차원 배열 선언 2
    // arr2 = {};로 해도 됨
    std::array<std::array<std::array<int, 3>, 3>, 3> arr2 = {{
        {{
            {}
        }}
    }};

    // 3차원 배열 선언 3
    std::array<std::array<std::array<int, 3>, 3>, 3> arr3 = {{
        {{
            { 1, 1, 1 },
            { 1, 1, 1 },
            { 1, 1, 1 }
        }},
        {{
            { 2, 2, 2 },
            { 2, 2, 2 },
            { 2, 2, 2 }
        }},
    }};

    // 3차원 배열 선언 4
    std::array<std::array<std::array<int, 3>, 3>, 3> arr4 = {{
        {{
            { 1, 1, 1 },
            { 1, 1, 1 },
            { 1, 1, 1 }
        }},
        {{
            { 2, 2, 2 },
            { 2, 2, 2 },
            { 2, 2, 2 }
        }},
        {{
            { 3, 3, 3 },
            { 3, 3, 3 },
            { 3, 3, 3 }
        }}
    }};

    return 0;
}

C++ 언어의 2차원 배열 방식과 같습니다.

배열의 접근

배열의 각 요소는 메모리 공간에 연속적으로 배치되고 자신만의 고유한 인덱스를 부여 받습니다. 이 인덱스는 요소의 위치를 나타내고, 이를 통해 각 요소에 접근할 수 있습니다.

C/C++ 언어에서 인덱스는 0부터 시작하며, 영어로 Zero-Based Indexing이라 합니다. 1부터 시작하는 것이 익숙한 우리 문화에서 다소 당황스럽기도 합니다.

인덱스가 0부터 시작하기 때문에 배열의 크기에서 1을 뺀만큼만 인덱스 넘버로 사용할 수 있습니다. 예를 들어 배열의 크기가 10이라면 9까지만 인덱스 넘버로 사용할 수 있다는 뜻입니다. 배열의 크기를 넘어서는 인덱스 넘버를 사용하면 예상치 못한 오류가 발생하거나 프로그램 사용 중 충돌이 발생할 수 있습니다.

메모리 공간에 연속적으로 배치되는거 ㄹㅇ인가요?

#include <array>
#include <iostream>

int main(int argc, char* argv[]) {
    // 1차원 배열 선언
    std::array<int, 5> arr = { 1, 2, 3, 4, 5 };

    // 각 요소의 주솟값 출력
    for (auto num : arr) {
        std::cout << (&num) << "\n";
    }

    return 0;
}

fd548130
fd548134
fd548138
fd54813c

배열의 각 요소가 메모리 공간에 연속적으로 배치되는 지 주소 연산자(&)로 쉽게 확인할 수 있습니다.

출력 결과를 보시면 각 주솟값이 4Bytes만큼 차이나는 걸 확인할 수 있습니다.(1) int 자료형은 4Bytes의 크기를 갖기 때문에 메모리 공간에서 4Bytes를 간격으로 연속적으로 배치된 걸 알 수 있습니다.

1. 주솟값은 실행 시 또는 사용자마다 다르게 나타납니다..

1차원2차원3차원

1차원 배열의 인덱스

#include <array>
#include <iostream>

int main(int argc, char* argv[]) {
    // (1) 1차원 배열 선언
    std::array<int, 5> arr = { 1, 2, 3, 4, 5 };

    // (2) 인덱스 연산자를 통한 접근
    std::cout << arr[0] << "\n";

    // (3) at 메서드를 통한 접근
    std::cout << arr.at(1) << "\n";

    // (4) data 메서드를 통한 접근
    std::cout << *(arr.data() + 2) << "\n";

    return 0;
}

1. 1차원 배열 선언

   std::array 컨테이너로 1차원 배열을 선언합니다.

2. 인덱스 연산자를 통한 접근

   C 언어에서 사용하던 방식입니다. std::array 컨테이너는 인덱스 연산자가 오버로딩되어 있어 똑같이 사용할 수 있습니다.

3. at 메서드를 통한 접근

   at() 메서드는 인덱스 연산자차럼 각 배열의 요소에 접근할 수 있습니다. 이 메서드는 인덱스 연산자와 다르게 배열의 크기를 벗어난 인덱스가 지정되면 std::out_of_range 예외를 발생시킵니다. 프로그램에서 예외를 처리할 수 있어 더 안전한 배열의 접근이 가능해집니다.

4. data 메서드를 통한 접근

   포인터 연산을 통해 접근합니다. 인덱스 연산자와 at() 메서드에 비해 사용 방식이 복잡하기 때문에 많이 사용되는 방식은 아닙니다.

2차원 배열의 인덱스

배열의 각 차원 크기 구하기

#include <array>
#include <iostream>

int main(int argc, char* argv[]) {
    // 2차원 배열 선언
    std::array<std::array<int, 5>, 3> arr = {{
        { 1, 1, 1, 1, 1 },
        { 2, 2, 2, 2, 2 },
        { 3, 3, 3, 3, 3 }
    }};

    // 전체 크기
    std::cout << sizeof(arr) << "\n";

    // 행 차원의 크기
    std::cout << arr.size() << "\n";

    // 열 차원의 크기
    std::cout << arr[0].size(); << "\n";

    return 0;
}

size() 메서드를 호출하면 실제 크기를 확인할 수 있습니다.

실제 메모리에서 차지하는 크기는 sizeof 연산자로 구해야 합니다.

#include <array>
#include <iostream>

int main(int argc, char* argv[]) {
    // 2차원 배열 선언
    std::array<std::array<int, 5>, 3> arr = {{
        { 1, 1, 1, 1, 1 },
        { 2, 2, 2, 2, 2 },
        { 3, 3, 3, 3, 3 }
    }};

    // (1) 반복문을 통한 접근
    for (auto row = 0; row < arr.size(); ++row) {
        for (auto col = 0; col < arr[0].size(); ++col) {
            // 또는 arr[row][col];
            std::cout << arr.at(row).at(col) << " ";
        }
        std::cout << "\n";
    }

    // (2) 반복문을 통한 접근
    for (const auto& row : arr) {
        for (auto element : row) {
            std::cout << element << " ";
        }
        std::cout << "\n";
    }

    return 0;
}

std::array 컨테이너를 이용한 2차원 배열은 [][] 또는 at() 메서드를 통해 접근할 수 있습니다.

또는 for-each 반복문을 통해 더 쉽게 접근할 수 있습니다. 따로 인덱스를 필요로 하는 게 아니라면 이 방법도 괜찮습니다.

3차원 배열의 인덱스

#include <array>
#include <iostream>

int main(int argc, char* argv[]) {
    // 3차원 배열 선언
    std::array<std::array<std::array<int, 3>, 3>, 3> arr = {{
        {{
            { 1, 1, 1 },
            { 1, 1, 1 },
            { 1, 1, 1 }
        }},
        {{
            { 2, 2, 2 },
            { 2, 2, 2 },
            { 2, 2, 2 }
        }},
        {{
            { 3, 3, 3 },
            { 3, 3, 3 },
            { 3, 3, 3 }
        }}
    }};

    // 반복문을 통한 접근
    for (auto x = 0; x < arr.size(); ++x) {
        for (auto y = 0; y < arr[0].size(); ++y) {
            for (auto z = 0; z < arr[0][0].size(); ++z) {
                std::cout << arr.at(x).at(y).at(z) << " ";
            }
            std::cout << "\n";
        }
        std::cout << "\n";
    }

    return 0;
}

std::array 컨테이너를 이용한 3차원 배열은 [][][] 또는 at() 메서드를 통해 접근할 수 있습니다.

2차원 배열에서 설명했던 것처럼 for-each 반복문을 통해 더 쉽게 접근할 수도 있습니다.

배열의 시간 복잡도

연산	시간 복잡도
접근	\(O(1)\)
탐색	\(O(n)\) 또는 \(O(1)\)
삽입	\(O(n)\) 또는 \(O(1)\)
삭제	\(O(n)\) 또는 \(O(1)\)

1. 접근

   배열은 인덱스를 통해 원하는 요소에 바로 접근할 수 있습니다. 탐색 과정없이 즉시 접근할 수 있어 시간 복잡도는 \(O(1)\)입니다.

2. 탐색

   배열에서 특정 값을 찾으려면 모든 요소를 검사해야 할 수 있습니다. 최악의 경우 배열의 끝까지 탐색해야 하므로 시간 복잡도는 \(O(n)\)입니다.

   최선은 탐색을 시작하자마자 발견하는 것이기 때문에 \(O(1)\)도 될 수 있지만, 최악의 경우를 고려하면 \(O(n)\)입니다.

3. 삽입

   

   삽입하는는 과정

   배열의 삽입은 빈 공간 존재와 시프트 연산을 전제로 합니다. 시프트 연산을 전제로 하는 이유는 배열의 연속적인 성질을 유지해야 하기 때문입니다.

   배열의 특정 위치에 새로운 요소를 삽입하면 이후의 모든 요소를 뒤로 한 칸씩 이동해야 합니다. 삽입 이후의 모든 요소를 한 칸씩 뒤로 이동해야 하므로 최악의 경우 \(O(n)\)의 연산이 필요합니다. 단, 배열의 마지막 위치에 삽입한다면 이동할 요소가 없기 때문에 \(O(1)\)이 됩니다.

4. 삭제

   

   삭제하는 과정

   배열의 삭제는 시프트 연산을 전제로 합니다. 시프트 연산을 전제로 하는 이유는 배열의 연속적인 성질을 유지해야 하기 때문입니다.

   배열의 특정 위치에 있는 요소를 삭제하면 이후의 모든 요소를 앞으로 한 칸씩 이동해야 합니다. 삭제 이후의 모든 요소를 한 칸씩 앞으로 이동해야 하므로 최악의 경우 \(O(n)\)의 연산이 필요합니다. 단, 배열의 마지막 요소를 삭제한다면 앞으로 당길 요소가 없기 때문에 \(O(1)\)이 됩니다.

정리

배열은 동일한 데이터 타입의 요소를 메모리 공간에 순차적으로 배치하는 자료구조입니다. 고정된 크기를 갖기 때문에 크기가 변하지 않는 데이터를 다룰 때 효율적입니다. 데이터가 유동적이고 삽입과 삭제 연산이 많다면 다른 자료구조를 사용하는 것이 좋습니다.

연습문제 1

사용자로부터 5개의 데이터 요소를 입력받아 저장한 뒤, 이를 역순으로 출력하세요.

해답

#include <array>
#include <iostream>

constexpr auto SIZE = 5;

int main(int argc, char* argv[]) {
    // 배열 선언
    std::array<int, SIZE> arr = { };

    // 입력 받기
    for (int i = 0; i < SIZE; ++i) {
        std::cin >> arr[i];
    }

    // 역순 출력
    for (auto it = arr.rbegin(); it < arr.rend(); ++it) {
        std::cout << (*it) << " ";
    }

    return 0;
}

rbegin() 함수는 배열의 끝을 가리키고, rend() 함수는 배열의 처음을 가리킵니다. r은 Reverse를 의미합니다.

연습문제 2

크기가 10인 정수형 배열에 사용자로부터 데이터를 입력받아 모든 요소의 합을 출력하세요.

해답

#include <array>
#include <iostream>
#include <numeric>      // for std::accumulate

constexpr auto SIZE = 10;

int main(int argc, char* argv[]) {
    // 배열 선언
    std::array<int, SIZE> arr = {};

    // 입력 받기
    for (int i = 0; i < SIZE; ++i) {
        std::cin >> arr[i];
    }

    // 모든 요소의 합
    std::cout << (std::accumulate(arr.begin(), arr.end(), 0)) << "\n";

    return 0;
}

std::accumulate() 메서드는 누적합을 구합니다. 세 번째 매개변수는 초깃값입니다.

연습문제 3

다음과 같은 요소가 할당된 두 배열이 주어집니다. 두 배열의 합을 구하세요.

{ 1, 2, 3, 4, 5 } { 6, 7, 8, 9, 0 }

해답

```cpp title="answer3.cpp" linenums="1"

include

include

constexpr auto SIZE = 5;

int main(int argc, char* argv[]) { // 배열 선언 std::array arr1 = { 1, 2, 3, 4, 5 }; std::array arr2 = { 6, 7, 8, 9, 0 };

// 두 배열의 합
// note: std::transform 사용해도 됨
std::array<int, SIZE> arr3 = {};
for (int i = 0; i < SIZE; ++i) {
    arr3[i] = arr1[i] + arr2[i];
}

// 출력
for (int val : arr3) {
    std::cout << val << " ";
}

return 0;

} ```

연습문제 4

크기가 5인 정수형 배열 { 1, 2, 3, 4, 5 }가 주어질 때, 배열을 왼쪽으로 한 칸씩 이동한 결과를 출력하세요.

결과: { 2, 3, 4, 5, 1 }

해답

#include <algorithm>            // for std::rotate
#include <array>
#include <iostream>

constexpr auto SIZE = 5;

int main(int argc, char* argv[]) {
    // 배열 선언
    std::array<int, SIZE> arr = { 1, 2, 3, 4, 5 };

    // 회전
    std::rotate(arr.begin(), arr.begin() + 1, arr.end());

    // 출력
    for (int val : arr) {
        std::cout << val << " ";
    }
}

C++ 언어에서는 <algorithm> 헤더에 있는 std::rotate() 메서드로 쉽게 해결할 수 있습니다.

매개변수로 (시작, 새 시작 위치, 끝)을 받습니다.