배열 (Array)

프로그래밍에서 배열(Array)은 동일한 타입의 데이터를 연속적으로 저장하는 자료구조이다. 배열은 데이터를 효율적으로 관리하고 접근할 수 있게 해주며, 다양한 알고리즘의 기초가 된다. 이번에는 배열의 기본 개념부터 자바에서의 사용법, 그리고 배열을 활용한 알고리즘까지 단계별로 다룬다.

배열을 잘 이해하고 활용하면 복잡한 문제를 간단하게 해결할 수 있다. 하나씩 알아보자.

배열의 정의와 특징

배열은 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조이다. 각 데이터는 인덱스를 통해 접근할 수 있으며, 인덱스는 0부터 시작한다. 배열의 크기는 선언 시 고정되며, 한 번 정해진 크기는 변경할 수 없다. 이는 배열의 주요 특징이자 제약사항이다.

배열의 장점은 다음과 같다:

• 빠른 접근: 인덱스를 사용해 O(1) 시간에 원하는 요소에 접근할 수 있다.
• 메모리 효율성: 연속된 메모리 공간을 사용하므로 메모리 관리가 용이하다.
• 간단한 구현: 기본적인 자료구조로, 많은 프로그래밍 언어에서 내장 지원한다.

반면, 단점도 존재한다:

• 고정된 크기: 크기를 변경할 수 없어, 데이터의 양이 변동될 때 비효율적일 수 있다.
• 삽입/삭제의 어려움: 중간에 요소를 삽입하거나 삭제할 때, 이후 요소들을 이동시켜야 한다.

자바에서 배열 선언 및 초기화

자바에서 배열을 선언하는 방법은 여러 가지이다. 기본적으로 배열은 참조 타입으로, 선언과 초기화를 분리할 수 있다.

배열 선언:

int[] arr;  // int 타입의 배열 참조 변수 선언

배열 초기화:

arr = new int[5];  // 크기가 5인 int 배열 생성

선언과 동시에 초기화:

int[] arr = {1, 2, 3, 4, 5};  // 크기가 5인 int 배열 생성 및 초기화

배열의 각 요소는 기본값으로 초기화된다. 예를 들어, int 배열은 0, boolean 배열은 false로 초기화된다.

배열의 기본 연산

배열을 사용하기 위해서는 기본적인 연산을 알아야 한다. 주요 연산은 접근, 수정, 순회이다.

1. 접근

인덱스를 사용해 특정 요소에 접근한다. 인덱스는 0부터 시작하며, 배열의 길이보다 작아야 한다.

int firstElement = arr[0];  // 첫 번째 요소 접근

2. 수정

특정 인덱스의 값을 변경한다.

arr[0] = 10;  // 첫 번째 요소를 10으로 변경

3. 순회

배열의 모든 요소를 순회하기 위해 for 루프나 for-each 루프를 사용할 수 있다.

// for 루프 사용
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
}

// for-each 루프 사용
for (int num : arr) {
    System.out.println(num);
}

다차원 배열

자바에서는 2차원, 3차원 등 다차원 배열을 지원한다. 다차원 배열은 배열의 배열로 구현된다.

2차원 배열 선언 및 초기화:

int[][] matrix = new int[3][3];  // 3x3 크기의 2차원 배열

특정 요소에 접근:

matrix[0][0] = 1;  // 첫 번째 행, 첫 번째 열에 1 저장

다차원 배열은 행렬 연산, 이미지 처리 등에 유용하게 사용된다.

배열과 메모리 관리

배열은 연속된 메모리 공간에 저장된다. 이는 인덱스를 통한 빠른 접근을 가능하게 하지만, 크기 변경이 불가능하다는 단점이 있다. 자바에서 배열의 크기는 length 필드를 통해 확인할 수 있다.

int size = arr.length;  // 배열의 크기 확인

배열의 크기를 변경하려면 새로운 배열을 생성하고 기존 데이터를 복사해야 한다. 이는 성능 저하를 일으킬 수 있으므로, 크기가 자주 변하는 데이터에는 동적 배열인 ArrayList를 사용하는 것이 좋다.

배열을 활용한 알고리즘

배열은 다양한 알고리즘에서 핵심적인 역할을 한다. 정렬, 검색, 동적 프로그래밍 등 많은 알고리즘이 배열을 기반으로 구현된다.

1. 정렬

배열을 정렬하는 알고리즘에는 버블 정렬, 퀵 정렬, 병합 정렬 등이 있다. 자바에서는 Arrays.sort() 메서드를 제공한다.

int[] numbers = {5, 3, 8, 1, 2};
Arrays.sort(numbers);  // 오름차순 정렬

2. 검색

배열에서 특정 값을 찾는 검색 알고리즘에는 선형 검색, 이진 검색 등이 있다. 이진 검색은 정렬된 배열에서 O(log n) 시간에 검색할 수 있다.

int index = Arrays.binarySearch(numbers, 3);  // 3의 인덱스 반환

3. 동적 프로그래밍

동적 프로그래밍에서는 배열을 사용해 중간 결과를 저장하고, 이를 활용해 효율적으로 문제를 해결한다. 예를 들어, 피보나치 수열을 배열로 계산할 수 있다.

public int fibonacci(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

배열의 한계와 대안

배열은 크기가 고정되어 있어, 데이터의 양이 변동될 때 비효율적일 수 있다. 또한, 중간에 요소를 삽입하거나 삭제할 때 O(n) 시간이 소요된다. 이를 보완하기 위해 자바에서는 ArrayList와 같은 동적 배열을 제공한다.

ArrayList는 내부적으로 배열을 사용하지만, 크기가 자동으로 조정된다. 삽입과 삭제도 보다 효율적으로 처리할 수 있다.

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.remove(0);  // 첫 번째 요소 삭제

하지만 ArrayList도 내부적으로 배열을 사용하므로, 빈번한 크기 변경은 성능 저하를 일으킬 수 있다. 따라서 데이터의 특성에 맞는 자료구조를 선택하는 것이 중요하다.

예제 문제

배열을 활용한 알고리즘을 연습하기 위해 난이도별로 문제를 제시하고, 자바 코드로 해답을 제공한다.

5
20 10 35 30 7

7 35

import java.util.Scanner;

public class MinMax {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        int min = arr[0];
        int max = arr[0];
        for (int i = 1; i < N; i++) {
            if (arr[i] < min) min = arr[i];
            if (arr[i] > max) max = arr[i];
        }
        System.out.println(min + " " + max);
        sc.close();
    }
}

4 9
2 7 11 15

0 1

import java.util.HashMap;
import java.util.Scanner;

public class TwoSum {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int target = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int complement = target - arr[i];
            if (map.containsKey(complement)) {
                int idx1 = map.get(complement);
                int idx2 = i;
                if (idx1 < idx2) {
                    System.out.println(idx1 + " " + idx2);
                } else {
                    System.out.println(idx2 + " " + idx1);
                }
                sc.close();
                return;
            }
            map.put(arr[i], i);
        }
        sc.close();
    }
}

9
-2 1 -3 4 -1 2 1 -5 4

6

import java.util.Scanner;

public class MaxSubArray {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        int maxSoFar = arr[0];
        int maxEndingHere = arr[0];
        for (int i = 1; i < N; i++) {
            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        System.out.println(maxSoFar);
        sc.close();
    }
}

마무리

배열은 프로그래밍의 기초가 되는 자료구조로, 데이터를 효율적으로 저장하고 접근할 수 있게 해준다. 자바에서 배열을 선언하고 사용하는 방법, 기본 연산, 다차원 배열, 메모리 관리, 그리고 배열을 활용한 알고리즘까지 다뤘다. 또한, 배열의 한계와 대안으로 ArrayList를 소개했다. 문제를 통해 배열을 실제로 활용하는 방법을 익혔으니, 이를 바탕으로 더 복잡한 문제를 해결해보자.