[자료구조] 배열 (Array)이란?

1. 배열의 정의

배열은 동일한 데이터 타입을 가진 요소들의 모음으로, 인덱스(위치)를 이용하여 각 요소에 접근할 수 있는 데이터 구조입니다. 각 요소는 고유한 숫자형 인덱스를 가지며, 이 인덱스를 사용하여 해당 요소에 접근할 수 있습니다.

2. 배열 요소의 삽입과 제거

배열에 요소를 삽입하거나 제거하는 작업은 배열의 크기와 요소의 위치에 따라 달라집니다.

• 삽입: 배열의 특정 위치에 요소를 삽입하려면, 해당 위치 이후의 요소들을 오른쪽으로 이동시킨 후 새로운 요소를 추가합니다. 이로 인해 삽입 작업은 배열의 크기를 증가시키거나 재할당해야 할 수도 있습니다.
• 제거: 배열에서 요소를 제거하면, 해당 요소 이후의 요소들을 왼쪽으로 이동시켜 빈 공간을 채웁니다. 마찬가지로 제거 작업은 배열의 크기를 감소시킬 수 있습니다.

3. 배열의 장단점

3-1) 장점

1. 빠른 접근: 인덱스를 사용하여 요소에 빠르게 직접 접근할 수 있습니다.
2. 메모리 관리: 연속된 메모리 공간에 요소를 저장하기 때문에 메모리 관리가 효율적입니다.
3. 간단한 구조: 사용이 간단하며, 많은 프로그래밍 언어에서 기본적으로 지원됩니다.
4. 일관된 성능: 요소의 위치에 관계없이 접근 및 검색 시간이 일정합니다.

3-2) 단점

1. 고정된 크기: 배열의 크기를 변경하기 어렵습니다. 크기를 변경해야 할 경우, 새 배열을 할당하고 기존 요소들을 복사해야 합니다.
2. 메모리 낭비: 배열은 선언 시 최대 크기로 메모리를 할당하므로, 실제로 사용하지 않는 공간이 낭비될 수 있습니다.
3. 삽입 및 제거의 어려움: 중간에 요소를 삽입하거나 제거하는 작업은 시간과 메모리 비용이 크며 복잡합니다.

4. 배열의 활용

배열은 다양한 분야에서 활용됩니다. 몇 가지 예시를 살펴보면

1. 데이터 저장 및 관리: 리스트, 테이블, 그래프 등의 데이터를 저장하고 관리할 때 사용됩니다.
2. 알고리즘 구현: 정렬, 탐색, 그래프 등 다양한 알고리즘을 구현할 때 활용됩니다.
3. 다차원 배열: 행렬, 이미지, 다차원 데이터 등을 표현할 때 사용됩니다.
4. 컬렉션 관리: 많은 요소를 한 번에 관리하거나 순회할 때 사용됩니다.

요약하면, 배열은 데이터 구조로서 효율적인 데이터 접근과 저장을 제공하지만 크기 조정의 어려움 등 몇 가지 제약 사항도 가지고 있습니다. 적절한 상황에서 배열을 활용하면 프로그램의 성능과 효율성을 향상시킬 수 있습니다.

5. 배열의 시간 복잡도

• 배열 요소 접근: O(1) - 인덱스를 통해 바로 접근 가능합니다.
• 배열 요소 삽입: 최악의 경우 O(n), 최선의 경우 O(1) - 위치에 따라 다릅니다
• 배열 요소 제거: 최악의 경우 O(n), 최선의 경우 O(1) - 위치에 따라 다릅니다.
• 배열 검색 및 정렬: 보통 O(n), 정렬된 배열에서 이진 탐색 시 O(log n) 가능합니다.

6. 배열 활용 문제 풀어보기

public class ArrayExample {
    public static void main(String[] args) {
        // 정수 배열 생성
        int[] numbers = {5, 2, 8, 10, 3};

        // 1.
        System.out.println("배열 길이: " + numbers.length);

        // 2. 
        System.out.println("첫 번째 요소: " + numbers[0]);
        System.out.println("세 번째 요소: " + numbers[2]);

        // 3.
        numbers[1] = 7;
        System.out.print("수정된 배열: ");
        for (int num : numbers) {
            System.out.print(num + " ");
        }
        System.out.println();

        // 4. 
        int[] newNumbers = new int[numbers.length + 1];
        for (int i = 0; i < numbers.length; i++) {
            newNumbers[i] = numbers[i];
        }
        newNumbers[numbers.length] = 4;
        numbers = newNumbers;
        System.out.print("추가된 배열: ");
        for (int num : numbers) {
            System.out.print(num + " ");
        }
        System.out.println();

        // 5.
        int removedElement = numbers[2];
        for (int i = 2; i < numbers.length - 1; i++) {
            numbers[i] = numbers[i + 1];
        }
        int[] updatedNumbers = new int[numbers.length - 1];
        for (int i = 0; i < updatedNumbers.length; i++) {
            updatedNumbers[i] = numbers[i];
        }
        numbers = updatedNumbers;
        System.out.println("제거된 요소: " + removedElement);
        System.out.print("업데이트된 배열: ");
        for (int num : numbers) {
            System.out.print(num + " ");
        }
        System.out.println();

        // 6.
        int searchElement = 7;
        boolean found = false;
        for (int num : numbers) {
            if (num == searchElement) {
                found = true;
                break;
            }
        }
        if (found) {
            System.out.println(searchElement + "는 배열에 있습니다.");
        } else {
            System.out.println(searchElement + "는 배열에 없습니다.");
        }

        // 7.
        java.util.Arrays.sort(numbers);
        System.out.print("정렬된 배열: ");
        for (int num : numbers) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

• Q.1. 1번의 실행 결과는 무엇일까요?
• Q.2. 2번의 실행 결과는 무엇일까요?
• Q.3. 3번은 무엇을 출력하려 한 것일까요?
• Q.4. 4번 for문의 시간복잡도는 무엇일까요?
• Q.5. 5번 for문의 시간복잡도는 무엇일까요?
• Q.6. 6번의 실행 결과는 무엇일까요?
• Q.7. 7번의 실행 결과는 무엇일까요?

Reference

자료구조.pdf