1. 배열이란
배열이란 같은 타입의 자료를 연속적인 메모리 공간에 저장하는 구조입니다. 무작위의 공간에 하나씩 저장되는 것보다 묶음이 통째로 연속된 공간에 저장되기 때문에 공간을 덜 차지하고 찾기가 쉽습니다. 따라서 메모리 효율성이 좋고, 요소 접근이 빠르다는 장점이 있습니다. 단점으로는 요소의 삽입 및 삭제 시 요소들이 이동하기 때문에 요소의 삽입이나 삭제를 자주한다면 시간복잡도가 효율적이지 않습니다.
2. 배열의 생성
배열을 만드는 것은 자료의 개수만큼 시간과 공간이 비례하기 때문에 시간복잡도와 공간복잡도가 전부 O(n)입니다.
3. 요소의 접근
배열에서 요소의 접근은 시간복잡도와 공간복잡도 모두 O(1)입니다. 시간복잡도가 O(1)인 이유는 아무리 배열이 커도 인덱스만 알면 바로 접근이 가능하기 때문입니다. 또한 공간복잡도가 O(1)인 이유는 단 한번만 접근하기 때문에 추가적인 메모리 공간이 필요하지 않기 때문입니다.
4. 요소의 변경
배열에서 요소의 변경도 요소의 접근처럼 시간복잡도와 공간복잡도 모두 O(1)입니다. 시간복잡도가 O(1)인 이유도 인덱스만 알면 바로 접근하여 값만 변경하기 때문이며, 공간복잡도가 O(1)인 이유는 요소의 접근과 동일하게 추가적인 메모리공간이 필요하지않기 때문입니다.
5. 배열의 생성, 접근, 변경을 코드로 확인
1. 파이썬
파이썬에서는 배열과 비슷한 기능을 할때는 리스트를 사용합니다. 정확하게는 파이썬의 리스트는 정확하게는 배열이라고 할 수 없습니다. 왜냐하면 파이썬에서 리스트는 '다른 타입'의 데이터를 요소를 저장할 수 있기 때문입니다. 그래서 파이썬의 리스트는 요소의 좌표값이 담긴 배열이라고 할 수 있습니다.
arr = [27, 36, 45, 44, 21, 24, 82, 11]
print(arr[3])
# 44
arr[5] = 16
print(arr)
# [27, 36, 45, 44, 21, 16, 82, 11]
2. 자바
public class ArrayExample {
public static void main(String[] args) {
int[] arr = {27, 36, 45, 44, 21, 24, 82, 11};
System.out.println(arr[3]);
// 44
arr[5] = 16;
for (int value : arr) {
System.out.print(value + " ");
}
// 27 36 45 44 21 16 82 11
}
}6. 배열의 탐색
배열의 탐색의 시간복잡도는 O(n)이고 공간복잡도는 O(1)입니다.
시간복잡도가 O(n)인 경우에는 배열을 순회하면서 요소의 값을 찾기 때문입니다. 찾는 요소값이 첫번째일 경우 1번만에 찾겠지만, 마지막 요소의 값이 찾는 값일 경우 n번을 순회하게 됩니다. 따라서 시간복잡도는 O(n)이 됩니다.
공간복잡도가 O(1)인 이유는 이미 만들어진 배열에서 값을 찾는 것이기 때문에 추가적인 메모리공간이 필요하지 않기 때문입니다.
이를 파이썬과 자바코드로 확인해보겠습니다.
1. 파이썬
arr = [27, 36, 45, 44, 21, 16, 82, 11]
for i in range(len(arr)):
if arr[i] == 45:
print(i)
break
# 2
for val in arr:
print(val)
2. 자바
public class ArraySearchTraverse {
public static void main(String[] args) {
int[] arr = {27, 36, 45, 44, 21, 16, 82, 11};
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 45) {
System.out.println(i);
break;
}
}
// 2
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}7.요소의 삭제와 삽입
배열의 삭제와 삽입은 시간복잡도는 O(n)이며 공간복잡도는 O(1)입니다.
시간복잡도가 O(n)인 이유는 배열의 요소를 삽입하거나 삭제하면 해당 요소의 뒤부터 앞으로 당겨지거나 뒤로 밀리는 등의 움직임이 발생하기 때문입니다. 공간복잡도가 O(1)인 이유는 처음에 배열을 생성할때 정해진 공간에서 더 늘어나지 않기 때문입니다. 배열의 요소가 모두 존재하는 상태에서 요소를 삭제하면 삭제한 요소의 뒷부분부터 앞으로 당겨지며, 마지막 요소는 빈값이 됩니다.
반대로 배열의 요소가 모두 존재하는 상태에서 요소를 삽입하면 에러가 발생합니다.
이를 자바코드를 통해 확인하겠습니다.
import java.util.Arrays;
public class ArrayModify {
public static void main(String[] args) {
Integer[] arr = {27, 36, 45, 44, 21, 16, 82, 11};
for (int i = 5; i < arr.length - 1; i++) { //5번 인덱스부터 순회하면서 앞으로 이동-> 5번 인덱스를 삭제
arr[i] = arr[i + 1];
}
arr[arr.length - 1] = null;
System.out.println(Arrays.toString(arr));
// [27, 36, 45, 44, 21, 82, 11, null]
for (int i = arr.length - 1; i > 1; i--) { //마지막 인덱스부터 1번 인덱스까지 순회하면서 뒤로 이동
arr[i] = arr[i - 1];
}
arr[1] = 33; // 비어있는 1번 인덱스에 33을 대입 -> 요소의 삽입
System.out.println(Arrays.toString(arr));
// [27, 33, 36, 45, 44, 21, 82, 11]
}
}8. 정적배열과 동적배열
기본적으로 배열은 정적배열입니다. 이는 처음에 배열을 생성할때 크기가 고정되어있다는 것을 의미합니다. 그러나 배열의 크기를 변화시키는 동적배열도 존재합니다. 동적 배열은 생성, 수정, 탐색, 삽입, 삭제 모두 시간복잡도는 정적배열과 동일하지만, 삽입시 공간복잡도만 정적배열보다 조금 큽니다. 동적배열은 요소를 삽입하여 배열의 크기가 증가하면 기존의 모든 요소를 새 메모리 공간으로 이동시킵니다. 그러나 공간복잡도는 O(1)이라고 할 수 있는데, 삽입되어 증가한만큼의 메모리공간만 더 필요하기 때문입니다. 즉, 메모리공간이 삽입만큼 증가된 공간에 새로운 배열을 생성하여 요소를 옮기고 기존 메모리공간을 비운다고 볼 수 있습니다..
이를 자바코드로 표현해보겠습니다.
import java.util.Arrays;
public class InsertIntoArray {
public static void main(String[] args) {
int[] original = {27, 33, 36, 45, 44, 21, 82, 11};
int[] result = new int[original.length + 1]; //original배열보다 1개 더 많은 배열을 생성
int insertIndex = 2;
int insertValue = 10;
for (int i = 0; i < insertIndex; i++) { // 삽입할 인덱스 앞은 그대로 유지
result[i] = original[i];
}
result[insertIndex] = insertValue; //삽입할 인덱스에 값 대입
for (int i = insertIndex; i < original.length; i++) { // 삽입할 인덱스의 뒤부터 한칸씩 뒤로 이동
result[i + 1] = original[i];
}
System.out.println(Arrays.toString(result));
// [27, 33, 10, 36, 45, 44, 21, 82, 11]
}
}
이 동적배열을 자바의 클래스로 구현해보겠습니다.
import java.util.Arrays;
class DynamicArray {
private int[] data = new int[8]; //처음에는 요소의 개수가 8개인 배열을 생성
private int size = 0; //
public void add(int value) {
ensureCapacity();
data[size++] = value;
}
public void insert(int index, int value) {
ensureCapacity();
for (int i = size; i > index; i--) {
data[i] = data[i - 1];
}
data[index] = value;
size++;
}
// size와 data배열의 크기를 비교하는 메서드 -> 배열의 크기가 다 차면 더 넒은 메모리공간으로 이동함
private void ensureCapacity() {
if (size >= data.length) { // size의 값이 data배열의 크기보다 클때
int[] newData = new int[data.length * 2]; // 기존크기보다 2배 큰 배열을 생성
for (int i = 0; i < size; i++) { // 배열을 순회하면서 요소를 복사함
newData[i] = data[i];
}
data = newData; // data의 주소값을 새 데이터의 주소값으로 넣어줌
}
}
public String toString() {
return Arrays.toString(Arrays.copyOf(data, size));
}
}
public class InsertExample {
public static void main(String[] args) {
DynamicArray arr = new DynamicArray(); // 동적배열 인스턴스 생성
int[] initial = {27, 33, 36, 45, 44, 21, 82, 11}; // 배열값 초기화
for (int num : initial) arr.add(num);
arr.insert(2, 10);
System.out.println(arr);
// [27, 33, 10, 36, 45, 44, 21, 82, 11]
}
}
이를 직접 구현하기에는 너무 복잡하고 어렵습니다. 따라서 자바에서는 ArrayList라는 동적배열을 제공하는 내장 라이브러리가 있습니다.
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>(
Arrays.asList(27, 33, 36, 45, 44, 21, 82, 11)
);
list.add(2, 10);
System.out.println(list);
//[27, 33, 10, 36, 45, 44, 21, 82, 11]
}
}
파이썬으로 표현하지 않은 이유는 파이썬의 리스트는 기본적으로 동적배열과 동일한 효과를 가지고 있기 때문입니다.
9. 2차원 배열
배열은 2차원으로 만들 수 있습니다. 보통 행렬의 형태를 2차원 배열이라고 합니다.
예를 들면 아래와 같습니다.
파이썬
arr = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]]
print(arr[1][2]) # 7
arr[1][2] = 99
print(arr[1][2]) # 99
for i in range(3):
for j in range(4):
if arr[i][j] == 10:
print((i, j))
# (2, 1)
for val in arr[1]:
print(val, end=' ')
# 5 6 99 8
for i in range(3):
print(arr[i][2], end=' ')
# 3 99 11
for row in arr:
for val in row:
print(val, end=' ')
# 1 2 3 4 5 6 99 8 9 10 11 12
자바
public class Array2DExample {
public static void main(String[] args) {
int[][] arr = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9,10,11,12}
};
System.out.println(arr[1][2]); // 7
arr[1][2] = 99;
System.out.println(arr[1][2]); // 99
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
if (arr[i][j] == 10) {
System.out.println("(" + i + ", " + j + ")");
// (2, 1)
}
}
}
for (int j = 0; j < 4; j++) {
System.out.print(arr[1][j] + " ");
// 5 6 99 8
}
System.out.println();
for (int i = 0; i < 3; i++) {
System.out.print(arr[i][2] + " ");
// 3 99 11
}
System.out.println();
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
System.out.print(arr[i][j] + " ");
// 1 2 3 4 5 6 99 8 9 10 11 12
}
}
}
}
C나 C++에서는 다차원 배열이 연속된 공간에 배치되기 때문에 내부 배열의 크기가 전부 동일해야 합니다.
그러나 자바나 파이썬 같은 언어는 외부 배열에 담기는 내부배열은 실제로 배열의 값이 아닌 주소값이 담기게 됩니다. 따라서 내부 배열의 크기가 전부 동일하지 않아도 생성이 가능합니다.
예를 들면 아래와 같습니다.
파이썬
arr = [
[1, 2],
[3, 4, 5],
[6]
]
for row in arr:
print(row)
# [1, 2]
# [3, 4, 5]
# [6]
자바
import java.util.Arrays;
public class JaggedArrayExample {
public static void main(String[] args) {
int[][] arr = {
{1, 2},
{3, 4, 5},
{6}
};
for (int[] row : arr) {
System.out.println(Arrays.toString(row));
}
// [1, 2]
// [3, 4, 5]
// [6]
}
}
1) 시간복잡도와 공간복잡도
배열의 생성에는 행과 열을 모두 만들어야 하므로 시간복잡도와 공간복잡도 모두 O(mxn)이 됩니다. m과 n이 동일하다고 가정했을땐 O(n^2)이 됩니다.
배열을 탐색하는 것 또한 행렬을 모두 순회해야 하므로 시간복잡도는 O(n^2)이 됩니다.
그러나 특정인덱스의 값을 찾거나 수정하는 것은 모두 시간복잡도가 O(1)입니다.
이외에도 3차원 이상의 배열도 있습니다. 다만 실무적으로 3차원 이상의 배열은 잘 사용되지않습니다.
참조: 얄코의 가장 쉬운 자료구조와 알고리즘
https://inf.run/Th7xU
'CS(Computer Science) 이론 > 자료구조' 카테고리의 다른 글
| [자료구조] 트리 (0) | 2025.09.07 |
|---|---|
| [자료구조] 큐(QUEUE) (0) | 2025.09.07 |
| [자료구조] 스택 (0) | 2025.09.06 |
| [자료구조] 연결리스트 (0) | 2025.09.04 |
| [자료구조] 그래프 (0) | 2024.05.13 |