☕Java — 배열, 이차원 배열, 정렬

01. 배열(Array)

1-1. 배열이란?

배열은 같은 자료형의 값을 연속된 메모리 공간에 묶어서 저장하는 자료구조다. 변수를 여러 개 선언하는 대신 하나의 이름으로 여러 값을 관리할 수 있다.

인덱스:  [0]    [1]    [2]    [3]    [4]
값:      10     20     30     40     50
        ↑
       arr[0]

• 인덱스는 항상 0부터 시작한다
• 길이는 선언 시 고정되며, 이후 크기 변경 불가
• new 키워드로 힙(Heap)에 생성되며, 참조변수가 그 주소를 가진다

---

1-2. 배열 선언과 생성

// 선언
int[] arr1;        // 권장
int   arr2[];      // 가능하지만 비권장

// 생성 (크기 지정)
arr1 = new int[5]; // int 5칸짜리 배열 생성, 기본값 0으로 초기화

// 선언과 동시에 생성
int[] arr3 = new int[5];

// 선언 + 초기화 (크기 자동 결정)
int[] arr4 = new int[]{10, 20, 30, 40, 50};
int[] arr5 = {10, 20, 30, 40, 50};  // 선언과 동시에만 사용 가능

기본값 초기화: 배열은 생성 시 자동으로 기본값이 채워진다.

• 정수형 → 0, 실수형 → 0.0, 문자형 → '�', 논리형 → false, 참조형 → null

---

1-3. 배열 접근과 수정

int[] arr = {10, 20, 30, 40, 50};

// 값 읽기
System.out.println(arr[0]);  // 10
System.out.println(arr[4]);  // 50

// 값 수정
arr[2] = 99;
System.out.println(arr[2]);  // 99

// 길이 확인
System.out.println(arr.length);  // 5

ArrayIndexOutOfBoundsException: 인덱스 범위를 벗어나면 런타임 에러가 발생한다. 유효 인덱스는 0 ~ length - 1.

---

1-4. 배열 순회

for문

int[] arr = {10, 20, 30, 40, 50};

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

향상된 for문 (for-each)

for (int num : arr) {
    System.out.println(num);  // 인덱스 없이 값만 순서대로 접근
}

for-each는 인덱스가 필요 없을 때 간결하게 쓸 수 있지만, 배열 값 수정은 불가하다. 수정이 필요하면 일반 for문을 사용해야 한다.

---

1-5. 배열 복사

배열 변수를 단순 대입하면 같은 배열을 가리키는 참조 복사가 된다. 독립된 복사본이 필요할 때는 명시적으로 복사해야 한다.

int[] original = {1, 2, 3, 4, 5};

// 참조 복사 (같은 배열을 공유)
int[] ref = original;
ref[0] = 99;
System.out.println(original[0]);  // 99 — original도 바뀜

// 방법 1: 반복문으로 직접 복사
int[] copy1 = new int[original.length];
for (int i = 0; i < original.length; i++) {
    copy1[i] = original[i];
}

// 방법 2: System.arraycopy()
// System.arraycopy(원본, 시작인덱스, 대상, 시작인덱스, 복사할 길이)
int[] copy2 = new int[original.length];
System.arraycopy(original, 0, copy2, 0, original.length);

// 방법 3: Arrays.copyOf()
import java.util.Arrays;
int[] copy3 = Arrays.copyOf(original, original.length);

참조 복사                         실제 복사
┌──────────┐                    ┌──────────┐
│ original │──┐                 │ original │──→ [1, 2, 3, 4, 5]
└──────────┘  │→ [1,2,3,4,5]   └──────────┘
┌──────────┐  │                 ┌──────────┐
│   ref    │──┘                 │  copy1   │──→ [1, 2, 3, 4, 5]  (독립)
└──────────┘                    └──────────┘

---

1-6. Arrays 유틸리티

import java.util.Arrays;

int[] arr = {5, 3, 1, 4, 2};

Arrays.sort(arr);                   // 오름차순 정렬 (원본 변경)
System.out.println(Arrays.toString(arr));  // [1, 2, 3, 4, 5]

int[] arr2 = {1, 2, 3};
int[] arr3 = {1, 2, 3};
System.out.println(Arrays.equals(arr2, arr3));  // true — 내용 비교

---

02. 2차원 배열(2D Array)

2-1. 2차원 배열이란?

2차원 배열은 배열의 배열이다. 행(row)과 열(column)로 구성된 표(table) 형태로 데이터를 관리할 때 사용한다.

       열0  열1  열2
행0  [ 10,  20,  30 ]
행1  [ 40,  50,  60 ]
행2  [ 70,  80,  90 ]

---

2-2. 선언과 생성

// 선언
int[][] arr2D;

// 생성 (행 3, 열 3)
arr2D = new int[3][3];

// 선언과 동시에 생성
int[][] grid = new int[3][3];

// 선언 + 초기화
int[][] table = {
    {10, 20, 30},
    {40, 50, 60},
    {70, 80, 90}
};

---

2-3. 접근과 순회

int[][] table = {
    {10, 20, 30},
    {40, 50, 60},
    {70, 80, 90}
};

// 값 접근
System.out.println(table[0][0]);  // 10
System.out.println(table[1][2]);  // 60
System.out.println(table[2][1]);  // 80

// 수정
table[0][0] = 99;

// 행의 수
System.out.println(table.length);     // 3
// 특정 행의 열 수
System.out.println(table[0].length);  // 3

이중 for문으로 순회

for (int row = 0; row < table.length; row++) {
    for (int col = 0; col < table[row].length; col++) {
        System.out.print(table[row][col] + "\t");
    }
    System.out.println();
}

for-each로 순회

for (int[] row : table) {
    for (int val : row) {
        System.out.print(val + "\t");
    }
    System.out.println();
}

---

2-4. 가변 배열 (Jagged Array)

자바의 2차원 배열은 각 행의 열 길이가 달라도 된다.

int[][] jagged = new int[3][];  // 열 크기를 지정하지 않음
jagged[0] = new int[2];
jagged[1] = new int[4];
jagged[2] = new int[3];

jagged[0] → [ 0, 0 ]
jagged[1] → [ 0, 0, 0, 0 ]
jagged[2] → [ 0, 0, 0 ]

---

03. 정렬 알고리즘

정렬(Sort)은 데이터를 일정한 순서(오름차순/내림차순)로 재배열하는 작업이다. 기초 정렬 알고리즘 3가지를 이해하면 알고리즘 사고의 기반이 된다.

---

3-1. 버블 정렬 (Bubble Sort)

개념

인접한 두 원소를 비교하여 순서가 맞지 않으면 교환하는 방식이다. 큰 값이 오른쪽 끝으로 하나씩 밀려나는 모습이 거품이 떠오르는 것과 같다.

[5, 3, 1, 4, 2] — 1회전 시작

5 > 3 → 교환: [3, 5, 1, 4, 2]
5 > 1 → 교환: [3, 1, 5, 4, 2]
5 > 4 → 교환: [3, 1, 4, 5, 2]
5 > 2 → 교환: [3, 1, 4, 2, 5]  ← 5가 맨 끝으로

2회전: [1, 3, 2, 4, 5]
3회전: [1, 2, 3, 4, 5]

구현

int[] arr = {5, 3, 1, 4, 2};
int n = arr.length;

for (int i = 0; i < n - 1; i++) {           // 회전 수
    for (int j = 0; j < n - 1 - i; j++) {   // 뒤쪽은 이미 정렬 완료
        if (arr[j] > arr[j + 1]) {
            int temp  = arr[j];
            arr[j]    = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}

안쪽 루프 범위가 n - 1 - i인 이유: 매 회전마다 가장 큰 값이 맨 뒤에 확정되므로 이미 정렬된 구간은 비교할 필요가 없다.

시간 복잡도

---

3-2. 선택 정렬 (Selection Sort)

개념

전체에서 최솟값을 찾아 맨 앞 원소와 교환하는 방식이다. 회전마다 정렬된 구간이 앞에서부터 하나씩 늘어난다.

[5, 3, 1, 4, 2] — 최솟값 찾아 교환

최솟값 1 → arr[0]과 교환: [1, 3, 5, 4, 2]
최솟값 2 → arr[1]과 교환: [1, 2, 5, 4, 3]
최솟값 3 → arr[2]와 교환: [1, 2, 3, 4, 5]
최솟값 4 → arr[3]과 교환: [1, 2, 3, 4, 5]

구현

int[] arr = {5, 3, 1, 4, 2};
int n = arr.length;

for (int i = 0; i < n - 1; i++) {
    int minIdx = i;                          // 현재 구간의 최솟값 인덱스
    for (int j = i + 1; j < n; j++) {
        if (arr[j] < arr[minIdx]) {
            minIdx = j;
        }
    }
    // 최솟값을 현재 위치(i)와 교환
    int temp     = arr[i];
    arr[i]       = arr[minIdx];
    arr[minIdx]  = temp;
}

최솟값 인덱스를 별도로 기록하고 루프가 끝난 뒤 한 번만 교환하므로, 버블 정렬보다 교환 횟수가 적다.

시간 복잡도

---

3-3. 삽입 정렬 (Insertion Sort)

개념

정렬된 앞부분 구간에 새 원소를 적절한 위치에 끼워 넣는 방식이다. 카드를 손에 쥐면서 순서대로 정렬하는 것과 같다.

[5, 3, 1, 4, 2]

i=1: key=3 → 5 > 3이므로 5를 오른쪽으로 이동 → [3, 5, 1, 4, 2]
i=2: key=1 → 5 > 1, 3 > 1이므로 이동          → [1, 3, 5, 4, 2]
i=3: key=4 → 5 > 4이므로 이동                  → [1, 3, 4, 5, 2]
i=4: key=2 → 5, 4, 3 > 2이므로 이동            → [1, 2, 3, 4, 5]

구현

int[] arr = {5, 3, 1, 4, 2};
int n = arr.length;

for (int i = 1; i < n; i++) {
    int key = arr[i];   // 삽입할 값
    int j   = i - 1;

    // key보다 큰 원소들을 오른쪽으로 한 칸씩 밀기
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = key;   // 적절한 위치에 삽입
}

i=0은 원소가 하나이므로 이미 정렬된 상태다. 따라서 i=1부터 시작한다.

시간 복잡도

삽입 정렬은 거의 정렬된 배열에서 세 알고리즘 중 가장 빠르다.

---

3-4. 세 알고리즘 비교

---

핵심 정리