배열 (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도 내부적으로 배열을 사용하므로, 빈번한 크기 변경은 성능 저하를 일으킬 수 있다. 따라서 데이터의 특성에 맞는 자료구조를 선택하는 것이 중요하다.
예제 문제
배열을 활용한 알고리즘을 연습하기 위해 난이도별로 문제를 제시하고, 자바 코드로 해답을 제공한다.
난이도 하: 배열에서 최솟값과 최댓값 구하기
시간 제한: 1 초 | 메모리 제한: 256 MB | 제출: 439,066 | 정답: 200,537 | 맞힌 사람: 150,571 | 정답 비율: 44.443%
N개의 정수가 주어진다. 이때, 최솟값과 최댓값을 구하는 프로그램을 작성한다.
입력
첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다.
출력
첫째 줄에 주어진 정수 N개의 최솟값과 최댓값을 공백으로 구분해 출력한다.
입력 예시
5
20 10 35 30 7출력 예시
7 35출처: Baekjoon Online Judge 10818번
해답
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();
}
}난이도 중: 배열에서 두 수의 합이 특정 값이 되는 쌍 찾기
N개의 정수로 이루어진 배열이 주어진다. 배열에서 두 수의 합이 특정 값(target)이 되는 두 수의 인덱스를 찾는 프로그램을 작성한다. 단, 답이 반드시 존재하며 유일하다고 가정한다.
입력
첫째 줄에 두 정수 N (2 ≤ N ≤ 100,000)과 target (-10^9 ≤ target ≤ 10^9)이 공백으로 구분되어 주어진다. 둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. 모든 정수는 -10^9보다 크거나 같고, 10^9보다 작거나 같다.
출력
첫째 줄에 두 수의 인덱스를 오름차순으로 공백으로 구분해 출력한다. 인덱스는 0부터 시작한다.
입력 예시
4 9
2 7 11 15출력 예시
0 1참고 출처: LeetCode "Two Sum" (입력 형식은 다름)
해답
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();
}
}난이도 상: 연속된 부분 배열의 최대 합 구하기 (카데인 알고리즘)
N개의 정수로 이루어진 배열이 주어진다. 배열에서 연속된 부분 배열의 합 중 최대값을 구하는 프로그램을 작성한다.
입력
첫째 줄에 정수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. 모든 정수는 -1,000보다 크거나 같고, 1,000보다 작거나 같다.
출력
첫째 줄에 연속된 부분 배열의 최대 합을 출력한다.
입력 예시
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를 소개했다. 문제를 통해 배열을 실제로 활용하는 방법을 익혔으니, 이를 바탕으로 더 복잡한 문제를 해결해보자.