자료구조 3장

1. 배열(Array) 개요

배열은 컴퓨터 과학에서 가장 기본적이고 널리 사용되는 자료구조 중 하나입니다. 연속된 메모리 공간에 동일한 데이터 타입의 원소를 저장하는 방식으로, 모든 프로그래밍 언어에서 기본적으로 제공하는 자료구조입니다. 배열은 데이터에 빠르게 접근할 수 있는 방법을 제공하기 때문에 다양한 알고리즘과 프로그램에서 자주 사용됩니다.

1.1 배열의 구조

배열은 정해진 크기의 연속된 메모리 공간에 원소를 순차적으로 저장합니다. 배열의 크기는 초기화 시에 결정되며, 배열에 할당된 메모리 공간은 크기가 고정되어 변경할 수 없습니다. 배열의 각 원소는 인덱스를 통해 접근할 수 있으며, 이 인덱스는 0부터 시작합니다. 예를 들어, int arr[5]라는 배열이 있다면, 이 배열의 첫 번째 원소는 arr[0], 두 번째 원소는 arr[1]과 같이 접근할 수 있습니다.

1.2 배열의 장점과 단점

장점:

• 빠른 접근 속도: 배열은 인덱스를 통해 O(1)의 시간 복잡도로 특정 원소에 접근할 수 있습니다.
• 메모리 효율성: 배열은 연속된 메모리 공간을 사용하기 때문에 오버헤드가 적습니다.

단점:

• 크기 고정: 배열의 크기는 초기화 시에 결정되며, 이후에 변경할 수 없습니다. 따라서, 배열이 필요 이상으로 크다면 메모리 낭비가 발생하고, 너무 작다면 데이터를 추가할 수 없는 문제가 생깁니다.
• 삽입과 삭제의 비효율성: 배열 중간에 원소를 삽입하거나 삭제할 경우, 나머지 원소들을 이동시켜야 하므로 시간 복잡도가 O(n)으로 비효율적입니다.

2. 배열의 주요 연산

배열에서 가장 기본적인 연산은 검색, 추가, 제거입니다. 각각의 연산은 배열의 성능에 큰 영향을 미치며, 이를 이해하는 것은 배열을 효과적으로 사용하는 데 매우 중요합니다.

2.1 검색(Search)

검색은 배열에서 특정 값을 찾아 그 값이 위치한 인덱스를 반환하는 연산입니다. 배열의 검색 방법에는 선형 검색과 이진 검색이 있습니다.

2.1.1 선형 검색(Linear Search)

선형 검색은 배열의 첫 번째 원소부터 마지막 원소까지 차례대로 검색하여 목표 값을 찾는 방법입니다. 이 방법은 배열이 정렬되어 있지 않은 경우에도 사용할 수 있으며, 알고리즘이 단순하다는 장점이 있습니다. 그러나, 최악의 경우 배열의 모든 원소를 검사해야 하므로 시간 복잡도는 O(n)으로 비효율적입니다.

선형 검색 예시:

int linear_search(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x)
            return i; // 값을 찾으면 인덱스를 반환
    }
    return -1; // 값을 찾지 못한 경우 -1 반환
}

2.1.2 이진 검색(Binary Search)

이진 검색은 배열이 정렬되어 있는 경우에만 사용할 수 있는 효율적인 검색 방법입니다. 배열의 중간 원소와 목표 값을 비교하여, 목표 값이 중간 원소보다 작으면 왼쪽 반쪽을, 크면 오른쪽 반쪽을 검색하는 방식으로 진행합니다. 이렇게 검색 범위를 절반으로 좁히면서 반복하므로, 시간 복잡도는 O(log n)으로 매우 효율적입니다.

이진 검색 예시:

int binary_search(int arr[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x)
            return mid; // 값을 찾으면 인덱스를 반환
        if (arr[mid] < x)
            left = mid + 1; // 오른쪽 반쪽을 검색
        else
            right = mid - 1; // 왼쪽 반쪽을 검색
    }
    return -1; // 값을 찾지 못한 경우 -1 반환
}

2.2 추가(Insert)

추가는 배열의 특정 위치에 새로운 원소를 삽입하는 연산입니다. 배열에 원소를 추가하는 방법은 삽입 위치에 따라 크게 두 가지로 나뉩니다: 배열의 마지막에 추가하거나 중간에 추가하는 경우입니다.

2.2.1 배열의 마지막에 추가

배열의 마지막에 원소를 추가하는 것은 비교적 간단합니다. 배열의 크기를 1만큼 늘리고, 새로운 원소를 마지막 위치에 저장하면 됩니다. 이 경우 시간 복잡도는 O(1)입니다.

2.2.2 배열의 중간에 추가

배열의 중간에 원소를 추가할 경우, 삽입 위치 이후의 모든 원소를 오른쪽으로 한 칸씩 이동시켜야 합니다. 따라서, 이 작업의 시간 복잡도는 O(n)입니다.

추가 연산 예시:

void insert(int arr[], int& n, int x, int pos) {
    // 배열의 크기를 1 증가시킴
    n++;
    // 삽입 위치 이후의 원소들을 한 칸씩 오른쪽으로 이동
    for (int i = n - 1; i >= pos; i--) {
        arr[i] = arr[i - 1];
    }
    // 새로운 원소 삽입
    arr[pos - 1] = x;
}

2.3 제거(Delete)

제거 연산은 배열에서 특정 원소를 삭제하는 작업입니다. 삭제 작업 역시 배열의 중간에서 원소를 제거하는 경우가 더 복잡하며, 시간 복잡도가 O(n)입니다.

2.3.1 배열의 중간에서 제거

배열의 중간에서 원소를 제거하면, 제거된 위치 이후의 모든 원소를 한 칸씩 왼쪽으로 이동시켜야 합니다. 이로 인해 배열의 크기는 1 감소합니다.

제거 연산 예시:

void delete_element(int arr[], int& n, int pos) {
    // 삭제할 원소 이후의 원소들을 한 칸씩 왼쪽으로 이동
    for (int i = pos - 1; i < n - 1; i++) {
        arr[i] = arr[i + 1];
    }
    // 배열의 크기를 1 감소시킴
    n--;
}

3. 배열의 성능 분석

배열의 성능은 주로 시간 복잡도로 평가됩니다. 앞서 설명한 검색, 추가, 제거 연산의 시간 복잡도는 다음과 같습니다:

• 검색:
  • 선형 검색: O(n)
  • 이진 검색: O(log n) (정렬된 배열에서만 가능)
• 추가:
  • 배열의 마지막에 추가: O(1)
  • 배열의 중간에 추가: O(n)
• 제거: O(n)

이러한 시간 복잡도를 고려하면, 배열은 크기가 크지 않은 경우나 빈번한 삽입과 삭제가 발생하지 않는 경우에 효과적으로 사용할 수 있습니다. 반면, 대규모 데이터나 빈번한 삽입/삭제가 필요한 경우에는 연결 리스트(Linked List)와 같은 다른 자료구조를 고려할 수 있습니다.

4. 배열과 연결 리스트 비교

배열과 연결 리스트는 리스트를 구현하는 두 가지 기본적인 방법입니다. 이 두 가지 자료구조는 각각의 장단점이 있으며, 사용 목적에 따라 선택됩니다.

4.1 배열(Array)

• 장점:
  • 인덱스를 통한 빠른 접근(O(1))
  • 메모리 사용이 효율적
• 단점:
  • 크기가 고정됨
  • 삽입/삭제 시 전체 원소의 이동이 필요함(O(n))

4.2 연결 리스트(Linked List)

• 장점:
  • 크기가 동적으로 변함
  • 삽입/삭제 시 전체 원소의 이동이 필요 없음(O(1)에서 O(n)까지)
• 단점:
  • 인덱스 접근이 불가능하여 탐색 시 O(n) 필요
  • 추가적인 메모리 사용(포인터를 위한 공간 필요)