배열 (Array)

Array란?

같은 자료형의 요소들이 순차적으로 나열된 자료구조
각 요소는 고유의 인덱스로 접근할 수 있음
배열은 메모리의 연속된 공간에 데이터를 저장하여, 빠른 데이터 접근과 효율적인 메모리 관리를 제공

주요 특징

1. 정적 크기: 배열의 크기는 선언 시점에 고정되며, 변경할 수 없음
2. 연속된 메모리: 배열의 요소들은 메모리 상에서 연속적으로 배치되므로, 특정 인덱스로 빠르게 접근 가능
3. 인덱스 기반 접근: 배열의 요소는 0부터 시작하는 인덱스를 통해 접근할 수 있음

장점

1. 빠른 접근: O(n)의 시간 복잡도로 특정 인덱스에 접근 가능
2. 간편한 메모리 관리: 연속된 메모리 공간을 사용하므로 데이터 관리가 용이함

단점

1. 크기 변경 불가: 배열의 크기는 선언 후 변경할 수 없어, 데이터 추가 및 삭제가 비효율적
2. 삽입 및 삭제의 비용: 특정 요소의 삽입 및 삭제 시, 다른 요소들을 이동해야 하므로 O(n)의 시간 복잡도가 발생

배열의 장단점과 활용 사례를 이해하고, 특정 문제 상황에서 가장 적합한 자료구조로 선택하는 것이 중요

최적화 기법

1. 이중 포인터 (Two-pointer):
   • 배열의 양 끝에서 시작하여 중앙으로 이동하며 조건을 만족하는 요소를 찾는 방식
2. 슬라이딩 윈도우 (Sliding Window):
   • 일정한 범위의 부분 배열을 이동하며, 최대값, 최소값 등을 찾는 최적화 기법
3. 분할 정복 (Divide and Conquer):
   • 배열을 분할하여 문제를 해결하는 방식으로, 대표적으로 Merge Sort, Quick Sort가 있음

종류

1. 1차원 배열 (One-dimensional Array): 단순한 일렬 배열로, 요소들이 한 줄로 나열됨
2. 2차원 배열 (Two-dimensional Array): 행과 열로 구성된 배열로, 매트릭스 형태로 사용
3. 다차원 배열 (Multi-dimensional Array): 3차원 이상 배열로, 복잡한 데이터 구조를 표현

주요 연산

1. 검색 (Search):
   • 특정 인덱스의 요소를 찾거나, 원하는 값을 배열 내에서 검색
   • 시간 복잡도: O(n) (인덱스 검색), O(n) (값 검색)
2. 삽입 (Insert):
   • 배열의 특정 위치에 요소를 추가
   • 시간 복잡도: O(n)
3. 삭제 (Delete):
   • 배열의 특정 위치의 요소를 제거
   • 시간 복잡도: O(n)
4. 업데이트 (Update):
   • 배열의 특정 위치의 요소를 변경
   • 시간 복잡도: O(1)

Array의 구현 예시

C++ 예제

#include <iostream>
using namespace std;

int main() {
    int arr[5] = {10, 20, 30, 40, 50};  // 크기 5의 정수 배열 생성

    // 배열 출력
    for(int i = 0; i < 5; i++) {
        cout << "arr[" << i << "] = " << arr[i] << endl;
    }

    // 특정 인덱스 접근
    cout << "Element at index 2: " << arr[2] << endl;

    return 0;
}

Python 예제

# 파이썬에서는 리스트가 배열과 같은 역할을 함
arr = [10, 20, 30, 40, 50]

# 배열 출력
for i in range(len(arr)):
    print(f"arr[{i}] = {arr[i]}")

# 특정 인덱스 접근
print(f"Element at index 2: {arr[2]}")

라이브러리

std::array

std::array를 사용하면 배열을 객체로 다룰 수 있으며, 크기를 컴파일 시에 지정하여 정적으로 사용

#include <iostream>
#include <array>
using namespace std;

int main() {
    array<int, 5> arr = {10, 20, 30, 40, 50};  // 크기 5의 정수 배열 생성

    // 배열 출력
    for (int i = 0; i < arr.size(); i++) {
        cout << "arr[" << i << "] = " << arr[i] << endl;
    }

    // 특정 인덱스 접근
    cout << "Element at index 2: " << arr[2] << endl;

    return 0;
}

std::vector

std::vector는 동적 배열로 크기를 유연하게 변경할 수 있고, 삽입 및 삭제 연산이 더 용이

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec = {10, 20, 30, 40, 50};  // 초기화 리스트를 사용하여 벡터 생성

    // 벡터 출력
    for (int i = 0; i < vec.size(); i++) {
        cout << "vec[" << i << "] = " << vec[i] << endl;
    }

    // 요소 추가
    vec.push_back(60);
    cout << "After push_back: " << vec.back() << endl;  // 마지막 요소 출력

    // 요소 삭제
    vec.pop_back();
    cout << "After pop_back: " << (vec.empty() ? "Vector is empty" : "Vector is not empty") << endl;

    return 0;
}