Data Structures/Linear Data Structures

1.1.1 Array

개념

배열은 같은 자료형의 원소를 연속된 메모리 공간에 저장하는 자료구조입니다. 생성할 때 크기를 정하고, 인덱스로 원소를 읽거나 수정합니다. 인덱스는 00부터 시작합니다.

1차원 배열

선언과 초기화

  • C++20: 함수 밖에 int a[5];처럼 자료형, 이름, 크기를 적어 전역 배열을 선언하면 모든 원소가 00으로 초기화됩니다. 배열 크기에는 컴파일 시 정해지는 상수를 사용합니다.
  • Java 17: int[] a = new int[n]으로 만들며 길이는 a.length로 읽습니다. 정수 배열의 초기값은 00입니다.

원소 접근과 수정

배열 a에 3,1,4,1,53,1,4,1,5가 저장되어 있습니다. 각 칸 아래의 숫자는 인덱스입니다. a[0]은 첫 번째 원소인 33이고, a[2]는 세 번째 원소인 44입니다.

3 0 1 1 4 2 1 3 5 4
▲ [그림 1] 배열의 원소 수정 — 연산 전

a[2] = 9를 실행하면 인덱스 22에 저장된 값이 44에서 99로 바뀝니다.

3 0 1 1 9 2 1 3 5 4
▲ [그림 2] 배열의 원소 수정 — 연산 후

시간·공간복잡도

길이가 NN인 배열을 기준으로 합니다.

구분대상복잡도
시간원소 하나 읽기·수정O(1)O(1)
공간배열 전체 저장O(N)O(N)

2차원 배열

2차원 배열은 원소를 행과 열로 구분하여 저장합니다. a[i][j]에서 i는 행 인덱스, j는 열 인덱스입니다.

선언과 초기화

각 언어에서 모든 원소가 00인 22행 33열 배열은 다음과 같이 준비합니다.

항목C++Java
선언·초기화함수 밖에 int a[2][3];int[][] a;로 선언한 뒤 a = new int[2][3];로 초기화

원소 접근과 수정

다음 배열은 22행 33열입니다. a[0][2]는 첫 번째 행의 세 번째 값인 33이고, a[1][0]은 두 번째 행의 첫 번째 값인 44입니다.

열 0 열 1 열 2 행 0 1 2 3 행 1 4 5 6
▲ [그림 3] 2차원 배열의 원소 수정 — 연산 전

a[1][2] = 9를 실행하면 두 번째 행의 세 번째 원소가 66에서 99로 바뀝니다.

열 0 열 1 열 2 행 0 1 2 3 행 1 4 5 9
▲ [그림 4] 2차원 배열의 원소 수정 — 연산 후

시간·공간복잡도

NN행 MM열 배열을 기준으로 합니다.

구분대상복잡도
시간원소 하나 읽기·수정O(1)O(1)
공간배열 전체 저장O(NM)O(NM)

예제

문제

55개의 수가 순서대로 주어진다. 첫 번째 수와 세 번째 수를 출력한 뒤, 세 번째 수를 99로 바꾸고 바뀐 값을 출력하여라.

입력

첫째 줄에 10 00010\,000보다 작은 양의 정수 55개가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 첫 번째 수, 둘째 줄에 변경 전 세 번째 수, 셋째 줄에 변경 후 세 번째 수를 출력한다.

예제 입력

3 1 4 1 5

예제 출력

3
4
9

예제 코드

C++20

#include <iostream>

using namespace std;

int a[5];

int main() {
    int i;

    for (i = 0; i < 5; ++i) {
        cin >> a[i];
    }

    // 첫 번째와 세 번째 원소 조회
    cout << a[0] << '\n';
    cout << a[2] << '\n';

    a[2] = 9; // 세 번째 원소 갱신

    cout << a[2] << '\n';
}