배열(Array): 기본 개념과 효율적인 활용 방법

🔹 배열이란?

1. 배열(Array)의 정의

**배열(Array)**은 같은 유형의 데이터를 연속된 메모리 공간에 저장하는 데이터 구조입니다. 배열은 인덱스를 사용하여 요소를 직접 접근할 수 있으며, 다양한 알고리즘에서 핵심적인 역할을 합니다.

✅ 배열의 주요 특징:

• 고정된 크기(Fixed Size): 선언 시 크기가 정해지며 변경이 어렵다.
• 빠른 인덱스 접근(O(1)): 특정 요소를 즉시 참조할 수 있다.
• 메모리 효율적 사용: 연속된 메모리 할당으로 캐시 효율성이 높음.
• 삽입 및 삭제가 비효율적: 중간 요소 추가/삭제 시 데이터 이동이 필요함.

📌 배열은 데이터 접근이 빠르지만, 크기 변경과 삽입/삭제가 어렵다는 단점이 있습니다.

---

🔹 배열의 주요 연산

1. 요소 접근(Accessing Elements) - O(1)

✅ 배열의 인덱스를 사용하여 특정 요소에 빠르게 접근 가능

✔️ 배열 접근 예제 (Python):

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

📌 인덱스를 사용하면 상수 시간 내에 원하는 요소를 가져올 수 있습니다.

2. 요소 삽입(Insertion) - O(n)

✅ 배열의 특정 위치에 요소를 삽입하려면 나머지 요소를 이동해야 함

✔️ 배열 삽입 예제 (Python):

arr = [10, 20, 30, 40, 50]
arr.insert(2, 25)  # 인덱스 2에 25 추가
print(arr)  # [10, 20, 25, 30, 40, 50] (O(n))

📌 삽입 시 나머지 요소를 이동해야 하므로, 최악의 경우 O(n)의 시간이 소요됩니다.

3. 요소 삭제(Deletion) - O(n)

✅ 삭제 후 나머지 요소를 왼쪽으로 이동해야 함

✔️ 배열 삭제 예제 (Python):

arr = [10, 20, 30, 40, 50]
del arr[2]  # 인덱스 2의 요소 삭제
print(arr)  # [10, 20, 40, 50] (O(n))

📌 배열의 중간 요소 삭제는 데이터 이동이 필요하여 O(n)의 시간이 소요됩니다.

4. 배열 검색(Search) - O(n) 또는 O(log n)

✅ 특정 요소를 찾는 데 O(n) (순차 탐색) 또는 O(log n) (이진 탐색)이 필요

✔️ 순차 탐색 예제 (Python):

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

📌 정렬되지 않은 배열에서는 O(n) 시간이 걸립니다.

✔️ 이진 탐색(정렬된 배열) 예제 (Python):

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

📌 정렬된 배열에서는 O(log n) 시간 복잡도로 빠르게 검색할 수 있습니다.

---

🔹 배열의 주요 유형

1. 1차원 배열(One-Dimensional Array)

✅ 가장 기본적인 형태로, 연속된 메모리 공간에 데이터를 저장

✔️ 1차원 배열 예제:

arr = [1, 2, 3, 4, 5]

📌 배열의 크기는 변경할 수 없으며, 특정 인덱스를 통해 접근합니다.

2. 2차원 배열(Two-Dimensional Array, 행렬)

✅ 행과 열로 이루어진 배열로, 테이블 형식 데이터를 저장할 때 사용

✔️ 2차원 배열 예제 (Python):

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print(matrix[1][2])  # 6

📌 이미지 처리, 그래프 표현 등에 자주 사용됩니다.

3. 동적 배열(Dynamic Array, 리스트)

✅ 배열의 크기를 동적으로 변경할 수 있는 데이터 구조 (Python의 리스트)

✔️ 동적 배열 예제 (Python):

arr = []
arr.append(10)  # 동적 추가
arr.append(20)
print(arr)  # [10, 20]

📌 Python의 리스트(list)는 내부적으로 동적 배열을 사용합니다.

---

🔹 배열 vs. 연결 리스트

비교 항목	배열(Array)	연결 리스트(Linked List)
크기 조정	고정 크기	동적 크기 가능
접근 속도	O(1) (인덱스 사용)	O(n) (노드 탐색 필요)
삽입/삭제	O(n) (데이터 이동 필요)	O(1) (노드 포인터 변경)
메모리 사용	연속적인 메모리 할당 필요	추가적인 포인터 저장 공간 필요

📌 배열은 빠른 접근 속도가 장점이며, 연결 리스트는 삽입/삭제가 용이합니다.

---

📌 결론

✅ 배열(Array)은 연속된 메모리 공간을 사용하는 기본적인 데이터 구조입니다.
✅ 인덱스를 이용한 빠른 데이터 접근이 가능하지만, 크기 변경과 삽입/삭제가 어렵습니다.
✅ 동적 배열, 다차원 배열 등 다양한 형태가 있으며, 문제에 따라 적절한 배열을 선택해야 합니다.
✅ 배열과 연결 리스트의 장단점을 비교하여 적절한 데이터 구조를 활용하는 것이 중요합니다.