[CS][Data Structure] 배열 (Array)

배열(Array) 이란?

배열은 int, boolean 등 동일한 타입의 데이터 요소들이 나열된 자료구조입니다.

배열은 역속된 메모리 공간에 데이터를 저장하며, 각 요소는 인덱스를 통해 쉽고 빠르게 접근할 수 있습니다. 인덱스는 0부터 시작하며, 대부분의 프로그래밍 언어에서 사용되는 방식입니다.

배열의 특징

고정된 크기

배열은 크기가 고정되어 있습니다. 배열을 선언할 때 메모리 크기가 결정되고, 이후 크기를 변경할 수 없습니다.
만약, 배열의 크기를 변경할 경우에는 새로운 배열은 생성하고 기존 배열을 복사하여 넣어야 합니다.

빠른 검색

배열은 인덱스를 통해 각 요소에 빠르게 접근할 수 있습니다.
원하는 데이터를 인덱스를 통해 즉시 찾으며 O(1)의 시간 복잡도를 가집니다.

데이터 삽입 및 삭제

배열의 크기가 고정되어 있기 때문에 삽입하거나 삭제하려는 위치에 이미 데이터가 있을 수 있기 때문에 기존 요소들을 뒤로 이동하거나 앞으로 이동해합니다. 따라서 새 요소를 삽입하거나 삭제할 때 최대 O(n)의 시간 복잡도를 가집니다.

배열의 활용

배열은 다양한 알고리즘과 문제에 적용될 수 있습니다. 대표적으로 사용하는 예시로는

검색  알고리즘 (선형 검색, 이진 검색 등)

정렬 알고리즘 (버블 정렬, 삽입 정렬, 합병 정렬 등)

기본 데이터 저장 및 조작 (문자열 처리, 숫자 배열 처리 등)

이 있습니다.