2024년 5월 28일 작성

자료 구조 - 배열 (Array)

배열은 동일한 유형의 요소들이 연속적으로 나열된 자료 구조입니다.

배열 : 요소를 연속적으로 저장하기

  • 배열(Array)은 동일한 data type을 가지는 요소들이 연속적인 memory 공간에 연속적으로 나열된 자료 구조입니다.
    • 배열의 크기는 선언 시에 지정하며, 한 번 생성된 배열의 크기는 변경할 수 없습니다.
    • 배열의 각 요소는 index를 통해 빠르게 접근할 수 있습니다.
  • 배열은 computer science에서 기본적인 자료 구조로, 그 특징들은 computer의 Memory, CPU 구조와 깊은 연관이 있습니다.

동일한 Data Type

  • 배열의 모든 요소는 동일한 data type을 가집니다.
    • 동일한 data type을 가짐으로써 배열 요소들의 크기가 일정하게 됩니다.
  • 이는 memory 주소 계산을 단순화하고, 배열 요소에 접근할 때 효율성을 높입니다.
int arr[5];    // 모든 요소가 int형

연속적인 Memory 공간

  • 배열의 요소들은 memory 상에 연속적으로 저장됩니다.
    • 연속적인 memory 할당은 배열 요소에 대한 index 기반 접근을 가능하게 합니다.
    • CPU는 배열의 시작 주소와 index를 이용하여 원하는 요소의 memory 주소를 직접 계산할 수 있습니다.
  • 예를 들어, 배열 arr의 시작 주소가 0x1000이고, 각 요소의 크기가 4Byte인 경우, arr[3]의 주소는 0x1000 + 3*4 = 0x100C가 됩니다.
int arr[5];    // memory 상에 연속적으로 저장

Index 사용

  • 배열의 각 요소는 index를 통해 접근할 수 있으며, index는 0부터 시작합니다.
    • 배열의 index를 통해 직접 요소에 접근할 수 있기 때문에, 배열은 상수 시간 복잡도(O(1))로 요소를 읽고 쓸 수 있습니다.
  • 이는 배열이 다른 자료 구조에 비해 빠른 접근 속도를 가지는 중요한 이유 중 하나입니다.
int value = arr[2];    // 세 번째 요소에 접근

고정된 크기

  • 배열의 크기는 선언 시에 지정되며, 한 번 생성된 배열의 크기는 변경할 수 없습니다.
    • 배열의 고정된 크기는 memory 할당을 단순화합니다.
    • 연속된 memory block을 할당하고, 이 block의 크기가 변경되지 않기 때문에 memory 관리가 상대적으로 용이합니다.
  • 이는 배열 요소의 주소 계산을 단순하게 유지할 수 있도록 합니다.
int arr[5];    // 크기가 5로 고정된 배열

효율적인 순차 접근

  • 배열은 memory 상에서 연속적으로 저장되므로, 순차적으로 접근할 때 효율적입니다.
    • cache memory는 공간 지역성(spatial locality) 개념을 활용하여, memory의 연속된 영역을 자주 참조하는 경우 더 효율적으로 작동합니다.
    • 배열의 요소들이 연속적으로 저장되므로, 배열의 순차적 접근은 CPU cache 성능을 극대화합니다.
for (int i = 0; i < 5; i++) {
    printf("%d ", arr[i]);
}

낮은 Memory Overhead

  • 배열은 다른 자료 구조에 비해 추가적인 memory overhead가 적습니다.
    • 배열은 단순히 요소들을 연속적으로 저장하는 구조이기 때문에, 각 요소에 대한 pointer나 link가 필요하지 않습니다.
  • 따라서 배열은 연결(Linked) List와 같은 다른 자료 구조에 비해 memory 사용 효율이 높습니다.
int arr[5];    // 배열 자체만 memory 차지

배열 사용 방법

  • 배열은 C 언어가 기본적으로 제공하는 자료 구조입니다.

배열 선언 및 초기화 (Declare & Initialize)

  • 대괄호([])를 사용하여 배열을 선언하고 초기화합니다.
#include <stdio.h>

int main() {
    // 정수형 배열 선언
    int arr[5];    // 크기가 5인 배열 선언

    // 배열 초기화
    arr[0] = 10;
    arr[1] = 20;
    arr[2] = 30;
    arr[3] = 40;
    arr[4] = 50;

    // 배열의 값 출력
    for (int i = 0; i < 5; i++) {
        printf("arr[%d] = %d\n", i, arr[i]);
    }

    return 0;
}

요소 접근 (Access)

  • 배열의 특정 index에 있는 요소에 접근할 수 있습니다.
int value = arr[2];    // 세 번째 요소에 접근

수정 (Modify)

  • 배열의 특정 index에 있는 요소의 값을 변경할 수 있습니다.
arr[2] = 35;    // 세 번째 요소의 값을 35로 변경

순회 (Traversal)

  • 배열의 모든 요소를 순회하면서 값을 처리할 수 있습니다.
for (int i = 0; i < 5; i++) {
    printf("%d ", arr[i]);
}
  • 배열 내에서 특정 값을 검색할 수 있습니다.
int key = 30;
for (int i = 0; i < 5; i++) {
    if (arr[i] == key) {
        printf("Found %d at index %d\n", key, i);
    }
}

목차