1. 배열 (Array)

배열이란?

"array를 그려줘"

 배열은 선형 자료 구조의 대표적인 형태이다. 프로그래밍을 접해본 사람이면 누구나 배열의 존재를 알고있을 것이다. 동일한 타입의 데이터를 연속적인 메모리 공간에 저장하는 자료 구조이다.

 

배열의 장점

 간단한 구조로 이루어져 빠른 접근이 가능하고, 연속적인 메모리 할당으로 캐시 적중률이 높아져 메모리 기대 성능이 좋다. 인덱스로 바로 직접 접근이 가능하기 때문에 접근하는 시간은 O(1) 상수시간으로, 인덱스를 알고 있다면 중간과정 없이 즉시 값을 꺼낼 수 있다. 또한, 우리가 생각하는 배열의 모양과 같이 실제 메모리 상에서도 연속적인 주소로 이루어져 있어 캐시 적중률이 높아 타 자료 구조에 비해 빠른 속도를 자랑한다.

 

배열의 단점

 장점을 모두 잊게 만드는 치명적인 단점은, 생성 시 크기가 고정된다는 점이다. 이를 상쇄하기 위해 동적 배열, 리스트 등의 자료 구조가 사용된다. 또한 중간에 있는 요소를 삽입, 삭제할 때 매우 비효율적이다. 삽입과 삭제 시간에만 O(n)이 걸리므로, 크기가 큰 데이터에 적용하는 것은 그다지 좋지 않을 수 있다. 

 

프로그래밍에서의 배열

C언어

#include <stdio.h>

int main() {
    int numbers[10] = {1, 2, 3, 4, 5};
    int length = 5;

    // 배열 요소 접근
    printf("%d\n", numbers[0]);
    printf("%d\n", numbers[2]);

    // 배열 요소 수정
    numbers[2] = 10;
    printf("%d\n", numbers[2]);

    // 배열 요소 삽입 (index 2에 99 삽입)
    for (int i = length; i > 2; i--) {
        numbers[i] = numbers[i - 1];
    }
    numbers[2] = 99;
    length++;
    for (int i = 0; i < length; i++) {
        printf("%d ", numbers[i]);
    }
    printf("\n");

    // 배열 요소 삭제 (index 2의 요소 삭제)
    for (int i = 2; i < length - 1; i++) {
        numbers[i] = numbers[i + 1];
    }
    length--;
    for (int i = 0; i < length; i++) {
        printf("%d ", numbers[i]);
    }
    printf("\n");

    return 0;
}

  

 배열 사용법의 표준은 C언어라고 생각한다. 기초 과정에서 항상 빠지지 않고 등장하며, 학습해놓으면 Java, Python, js 등에서 똑같이 쓸 수 있다. 

 코드를 살펴보면, 접근, 접근하여 수정은 O(1)로, 중간과정 없이 즉시 실행이된다. 하지만 삽입 부분을 살펴보면

 

배열 삽입 과정 (위 코드에 따라)

 1. index 2 자리를 만들기 위해 현재 인덱스 2부터 끝까지의 요소를 한 칸씩 뒤로 민다.

 2. index 2에 99를 넣는다.

 3. 총 길이를 증가 시킨다.

 

 위 같은 과정을 거친다. 만약 N개의 데이터가 있는 배열에 0번 자리에 삽입을 해야한다고 가정하면, 과정 1번에서 밀어야할 데이터의 개수는 N개이다. 그러므로 최악의 경우 O(n), 선형 시간만큼이 걸리는 것이다.

 삭제 과정도 비슷하다. index 2를 삭제한다고 가정하면, index 2의 뒤에있는 데이터를 앞으로 한 칸씩 당겨온다. 그러므로 최악의 경우 O(n), 선형 시간만큼 소요된다.