Array

배열 (Array)

• 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조

왜 사용하는가?

• 인덱스를 통해 O(1)로 임의 접근이 가능한 자료구조가 필요할 때
• 메모리를 연속적으로 사용하여 캐시 효율을 높이고 싶을 때
• 크기가 고정된 데이터를 다룰 때

장점

항목	설명
빠른 접근	인덱스를 통한 O(1) 임의 접근
메모리 효율	연속 메모리 배치 → 캐시 히트율 높음
단순한 구조	구현 및 사용이 간단

단점

항목	설명
고정 크기	선언 시 크기 결정, 동적 변경 불가
삽입/삭제 비용	중간 삽입·삭제 시 요소 이동 필요 O(n)
메모리 낭비	크기를 크게 잡으면 미사용 공간 발생

특이점

• 배열의 인덱스 조회 공식: 배열의 시작 참조 + (자료의 크기 * 인덱스 위치)
• 메모리가 연속 배치되므로 CPU 캐시 효율이 LinkedList보다 뛰어남

시간 복잡도

연산	위치	복잡도
인덱스 조회	임의 위치	O(1)
검색	순차 탐색	O(n)
추가	마지막	O(1)
추가	처음	O(n)
추가	중간	O(n/2) → O(n)
삭제	처음/중간	O(n)

어떻게 사용하는가?

// 선언과 초기화
int[] arr = new int[5];
int[] arr2 = {1, 2, 3, 4, 5};

// 인덱스 접근
int value = arr2[2]; // O(1)

// 배열 복사
int[] copy = Arrays.copyOf(arr2, arr2.length);
System.arraycopy(arr2, 0, copy, 0, arr2.length); // 고속 복사

// 정렬
Arrays.sort(arr2);

// 출력
System.out.println(Arrays.toString(arr2));

어떨 때 많이 쓰는가?

• 크기가 고정된 데이터를 다룰 때 (요일, 월, 방향 등)
• 인덱스 기반의 빠른 랜덤 접근이 필요할 때
• 내부적으로 ArrayList, HashMap 등의 자료구조 구현에 사용
• 알고리즘 문제에서 기본 자료구조로 활용