배열 (Array)

개요

배열(Array)은 같은 자료형을 가진 요소들을 연속적인 메모리 공간에 저장하는 자료구조입니다. 배열을 사용하면 여러 개의 데이터를 하나의 변수처럼 다룰 수 있으며, 인덱스를 이용하여 특정 요소에 접근할 수 있습니다.

배열은 대부분의 프로그래밍 언어에서 기본적으로 제공하는 자료구조이며, 고정된 크기를 가지는 경우가 일반적입니다. 그러나 일부 언어에서는 동적으로 크기를 조정할 수 있는 배열도 제공합니다.

배열의 특징

1. 연속적인 메모리 공간 사용

   • 배열의 요소들은 메모리에 연속적으로 배치되므로, 인덱스를 이용한 접근 속도가 빠릅니다.

   • 임의의 위치에 있는 원소를 $O(1)$ (상수 시간)에 접근할 수 있습니다.

2. 고정된 크기

   • 일반적인 배열은 선언 시 크기가 결정되며, 이후 변경할 수 없습니다.

   • 크기를 변경하려면 새로운 배열을 할당하고 데이터를 복사해야 합니다.

3. 동일한 자료형의 요소 저장

   • 배열에 저장되는 요소들은 모두 같은 자료형을 가져야 합니다.

   • 따라서 메모리를 효율적으로 사용할 수 있습니다.

4. 빠른 조회, 느린 삽입/삭제

   • 특정 위치의 요소를 조회하는 것은 빠르지만, 중간에 요소를 삽입하거나 삭제하는 연산은 비용이 큽니다.

   • 이유는 배열은 연속된 메모리를 사용하기 때문에 중간에 데이터를 추가하면 기존 데이터를 이동해야 하기 때문입니다.

---

배열의 연산

1. 접근 (Access) - $O(1)$

배열의 특정 요소에 접근하는 시간 복잡도는 $O(1)$입니다.
인덱스를 사용하여 원하는 요소에 직접 접근할 수 있기 때문입니다.

arr = [10, 20, 30, 40, 50]
print(arr[2])  # 30

---

2. 탐색 (Search) - $O(n)$

배열에서 특정 요소를 찾기 위해서는 선형 탐색(Linear Search) 또는 이진 탐색(Binary Search, 정렬된 배열에 한정)을 사용할 수 있습니다.

• 선형 탐색(Linear Search): $O(n)$
  배열을 처음부터 끝까지 순회하면서 원하는 값을 찾습니다.

    def linear_search(arr, target):
        for i in range(len(arr)):
            if arr[i] == target:
                return i
        return -1  # 찾지 못한 경우
  
    arr = [10, 20, 30, 40, 50]
    print(linear_search(arr, 30))  # 2

• 이진 탐색(Binary Search): $O(\log n)$ (정렬된 배열에서 사용 가능)
  배열이 정렬된 경우, 중간 값을 기준으로 절반씩 탐색하여 효율적으로 찾을 수 있습니다.

    def binary_search(arr, target):
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1
  
    arr = [10, 20, 30, 40, 50]
    print(binary_search(arr, 30))  # 2

---

3. 삽입 (Insertion) - $O(n)$

배열의 끝에 요소를 추가하는 것은 $O(1)$이지만, 중간에 삽입하려면 이후의 요소들을 한 칸씩 뒤로 밀어야 하므로 $O(n)$의 시간이 걸립니다.

arr = [10, 20, 30, 40, 50]

# 중간에 삽입
arr.insert(2, 25)  # 2번 인덱스에 25 삽입
print(arr)  # [10, 20, 25, 30, 40, 50]

---

4. 삭제 (Deletion) - $O(n)$

삭제도 삽입과 유사하게, 중간의 요소를 삭제하면 이후 요소들을 한 칸씩 앞으로 이동해야 하므로 $O(n)$이 걸립니다.

arr = [10, 20, 30, 40, 50]

# 중간 요소 삭제
arr.pop(2)  # 2번 인덱스 요소(30) 삭제
print(arr)  # [10, 20, 40, 50]

---

배열과 연결 리스트 비교

특징	배열 (Array)	연결 리스트 (Linked List)
메모리 구조	연속된 공간	불연속적인 노드
접근 속도	$O(1)$ (인덱스로 접근)	$O(n)$ (순차 탐색)
삽입/삭제 속도	$O(n)$ (중간 요소 이동 필요)	$O(1)$ (포인터 변경)
크기 조정	크기 변경 불가 (새 배열 할당 필요)	동적 크기 조정 가능
메모리 사용	추가 메모리 필요 없음	포인터를 저장하는 메모리 필요

배열은 빠른 조회(검색)가 필요할 때 유리하고, 연결 리스트는 빈번한 삽입/삭제가 필요한 경우에 적합합니다.

---

배열의 활용 예시

1. 기본적인 데이터 저장: 여러 개의 같은 유형의 데이터를 저장할 때 사용

2. 정렬 (Sorting): 버블 정렬, 퀵 정렬 등의 알고리즘에서 사용

3. 이진 탐색 (Binary Search): 정렬된 배열에서 빠르게 요소 찾기

4. 다차원 배열: 행렬 연산, 그래프 표현, 이미지 데이터 처리 등에서 활용

5. 슬라이딩 윈도우 알고리즘: 연속적인 부분 배열 문제 해결

---

배열 관련 문제 예제

1. 배열 회전 (Rotate Array)

   • 배열을 오른쪽으로 K번 회전시키는 문제

```
def rotate_array(arr, k):
    k %= len(arr)  # k가 배열 길이보다 클 경우
    return arr[-k:] + arr[:-k]  # 오른쪽에서 k개를 앞으로 이동

arr = [1, 2, 3, 4, 5, 6, 7]
print(rotate_array(arr, 3))  # [5, 6, 7, 1, 2, 3, 4]
```

2. 최대 연속 부분 합 (Kadane's Algorithm)

   • 연속된 부분 배열 중 최대 합을 찾는 문제 ($O(n)$)

```
def max_subarray_sum(arr):
    max_sum = current_sum = arr[0]
    for num in arr[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(arr))  # 6 (부분 배열: [4, -1, 2, 1])
```

---

결론

배열은 가장 기본적인 자료구조 중 하나로, 빠른 조회가 필요할 때 유용하지만 삽입/삭제에는 비용이 크다는 특징이 있습니다.
연결 리스트, 해시 테이블 등 다른 자료구조와 비교하여 어떤 상황에서 배열이 적합한지 고려하여 사용하는 것이 중요합니다. 🚀