자료구조(2) - 배열

hyejin·2024년 7월 18일

동적 배열 배열 빅오표기법 자료구조 정적 배열

study-2024

목록 보기

11/17

배열(Array)이란?

자료구조에서 기본적인 형태로, 동일한 타입의 데이터가 순차적으로 저장되는 구조를 말한다.
인덱스를 사용해 요소에 접근할 수 있으며, 고정된 크기를 가지거나 동적 크기를 가질 수 있다.

특징

인덱스를 사용한 빠른 접근: 배열의 각 요소는 인덱스를 통해 O(1) 시간에 접근 가능
고정 크기 또는 동적 크기: 배열은 고정된 크기를 가질 수도 있고, JavaScript나 Python 같은 언어에서는 동적으로 크기를 변경 가능
동일한 타입의 데이터 저장: 배열은 보통 동일한 타입의 데이터를 저장

예제

고정 크기 배열 (정적 배열)

고정 크기 배열은 생성 시 크기가 고정되며, 이후에는 크기 변경이 불가능하다. (C, C++, Java, C#)
아래 예제는 C언어로 작성된 예제이다.

#include <stdio.h>

int main() {
    // 정적 배열을 생성하고 모든 요소를 0으로 초기화
    int arr[5] = {0}; 

    // 배열에 데이터 추가
    arr[0] = 10;
    arr[1] = 20;
    arr[2] = 30;
    arr[3] = 40;
    arr[4] = 50;

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

    return 0;
}

> Array values:
arr[0] = 10
arr[1] = 20
arr[2] = 30
arr[3] = 40
arr[4] = 50

arr[5]에 데이터를 추가한다면?

#include <stdio.h>
int main() {
    arr[5] = 60;
    // 배열의 내용 출력
    printf("Array values:\n");
    for (int i = 0; i < 5; i++) {
      printf("arr[%d] = %d\n", i, arr[i]);
    }
    return 0;
}

// 결과
Array values:
arr[0] = 10
arr[1] = 20
arr[2] = 30
arr[3] = 40
arr[4] = 50

C언어에서는 정적 배열의 크기를 넘는 접근을 시도한 경우, 경고 또는 런타임 에러가 발생할 수 있다.

동적 크기 배열

JavaScript/TypeScript의 배열은 동적 크기를 가지며, 요소를 추가하거나 제거할 수 있다.
아래 예제는 typescript 언어로 작성된 예제이다.

// 동적 크기 배열 생성
let dynamicArray: number[] = [];

// 요소 추가
dynamicArray.push(10); // [10]
dynamicArray.push(20); // [10, 20]
dynamicArray.push(30); // [10, 20, 30]

// 요소 제거
dynamicArray.pop(); // [10, 20]

// 요소 앞에 추가
dynamicArray.unshift(5); // [5, 10, 20]

// 요소 앞에서 제거
dynamicArray.shift(); // [10, 20]

// 요소 접근
console.log(dynamicArray[1]); // 20

// 요소 수정
dynamicArray[1] = 25;
console.log(dynamicArray); // [10, 25]

주의 !!
python에서는 리스트가 동적 배열이기 때문에 크기가 자동으로 조정되지만, 인덱스를 통해 접근할 때 범위를 벗어나면 IndexError가 발생한다.
-> 리스트의 크기가 동적으로 증가하더라도, 인덱스 접근은 여전히 현재 리스트의 범위 내에서만 가능하기 때문

내부 동작 원리

메모리 할당: 배열은 연속된 메모리 블록에 할당된다. 이는 요소에 대한 빠른 접근을 가능하게 한다.
인덱싱: 배열 요소는 인덱스를 사용하여 접근할 수 있으며, 인덱스는 0부터 시작한다.
삽입/삭제: 동적 배열의 경우, 요소를 삽입하거나 삭제할 수 있다. 하지만 이러한 작업은 배열의 크기를 변경할 수 있으며, 배열 요소를 이동해야 하는 경우도 있다. 이는 추가적인 시간 복잡도를 초래할 수 있다.

시간 복잡도

접근 시간: O(1)
검색 시간: O(n)
삽입/삭제 시간: O(n)

시간 복잡도(Time Complexity)
알고리즘의 효율성을 측정하는 데 사용되는 개념으로, 입력 크기 n에 대한 연산 횟수를 표현한다. 이는 보통 빅오 표기법(Big O Notation)으로 표현되며, 최악의 경우 수행되는 연산 횟수를 나타낸다.

최상의 경우: 오메가 표기법(Big-Ω)

평균의 경우: 세타 표기법(Big-θ)

최악의 경우: 빅오 표기법(Big-O)

요약

배열은 동일한 타입의 데이터를 순차적으로 저장하는 자료구조로, 인덱스를 사용해 빠르게 접근할 수 있다.
정적 배열과 동적 배열이 있으며, 각각의 특성과 사용 용도가 다르다.
Python이나 JavaScript에서는 동적 배열을 사용해 요소를 추가하거나 제거할 수 있다.
배열은 메모리 효율성이 높고 빠른 접근 속도를 가지지만, 삽입이나 삭제가 빈번한 경우에는 다른 자료구조를 고려해야 할 수도 있다.