본 시리즈는 프로그래밍 자료구조의 개념을 정리하고 실습을 진행해보는 시리즈입니다.
- 실습은 다음과 같은 개발환경 및 버전에서 진행하였습니다.
- IDE : IntelliJ IDEA (Ultimate Edition)
- Java : JDK 21 (corretto-21)
- Python : 3.9 (conda env)
자료구조 - 배열(Array)
1. Array란?
배열은 가장 기본적인 선형 자료구조로, 연속적인 메모리 공간에 동일한 타입의 데이터를 저장하는 구조입니다.
- 각 데이터는 인덱스(index)를 통해 접근할 수 있으며, 이로 인해 배열은 랜덤 액세스가 가능하고, 특정 인덱스에 있는 데이터를 빠르게 읽거나 수정할 수 있습니다.
주요 특징:
- 인덱스를 통한 빠른 접근: 특정 인덱스에 직접 접근할 수 있어 시간 복잡도는
O(1)입니다. - 고정된 크기: 배열의 크기는 선언 시 결정되며, 변경할 수 없습니다.
- Python에서는
list자료형이 배열을 대신해서 동적으로 크기가 조절됩니다.
- Python에서는
- 동일한 타입의 데이터: 배열은 동일한 타입의 데이터만 저장할 수 있습니다.
- Python에서는 더 유연하게 다양한 타입을 저장할 수 있습니다.
1.1 메모리 주소와 배열의 연산 속도
배열의 빠른 연산 속도는 데이터가 연속적인 메모리 공간에 저장되기 때문에 가능해집니다.
- 예를 들어, 정수형 배열의 첫 번째 요소가 메모리의
x1000번지에 저장되었다면, 그 다음 요소는 메모리의x1004번지에 저장됩니다.- 이는 각 요소가 정수형(
int)일 경우,4바이트크기의 메모리 공간을 차지하기 때문입니다.
- 이는 각 요소가 정수형(
따라서 배열의 특정 인덱스에 접근하는 연산이 O(1)로 매우 빠른 이유는, 배열의 시작 주소와 인덱스를 이용해 직접 해당 요소의 메모리 주소를 계산할 수 있기 때문입니다.
예시
배열의 시작 주소가 x1000번지라면, numbers[2]에 접근할 때의 메모리 주소는 1000 + (2 * 4) = x1008번지입니다.
- 이처럼 배열은 인덱스를 이용해 해당 요소가 저장된 메모리 주소를 즉시 계산할 수 있기 때문에, O(1)의 시간이 소요됩니다.
이러한 메모리 효율성 덕분에 CPU 캐시를 효과적으로 활용할 수 있어, 데이터 처리 속도가 더 빨라집니다.
- 연속된 메모리 공간에 저장된 데이터는 캐시 효율이 높아, CPU가 배열 데이터를 빠르게 읽고 처리할 수 있습니다.
1.2 배열의 장단점
장점:
- 빠른 조회 속도:
O(1)로 인덱스를 통한 데이터 접근이 매우 빠릅니다. - 메모리 효율적: 연속적인 메모리 공간을 차지하므로 캐시 효율이 높습니다.
단점:
- 고정된 크기: Java에서는 배열의 크기를 변경할 수 없기 때문에 데이터가 추가될 때 유연하지 못합니다.
- 삽입/삭제 비용: Python에서는 중간 삽입/삭제 시
O(n)의 시간이 걸리며, Java에서는 배열을 새로 만들어야 삽입/삭제를 할 수 있습니다.
2. 배열의 구현
2.1 Java에서의 배열
Java에서 배열은 고정 크기이며, 다음과 같이 선언하고 사용할 수 있습니다.
int[] numbers = new int[5]; // 크기가 5인 정수형 배열 선언
numbers[0] = 10; // 인덱스를 이용한 값 할당
System.out.println(numbers[0]); // 인덱스를 이용한 값 출력배열의 크기는 선언 시 고정되므로, 크기를 변경하거나 중간에 값을 삽입/삭제하려면 새로운 배열을 생성해야 합니다.
2.2 Python에서의 배열
Python에서는 list가 배열과 유사한 역할을 하지만, 고정 크기가 아니며 다양한 타입을 혼합할 수 있습니다. (고정된 크기의 배열을 기본적으로 제공하지 않습니다.)
numbers = [10, 20, 30, 40, 50] # 정수형 리스트 선언
print(numbers[0]) # 인덱스를 이용한 값 출력Python의 리스트는 동적 배열처럼 작동하며, 크기를 유연하게 변경할 수 있습니다.
2.3 Java & Python 비교
- Java는 배열의 크기가 고정되어 있고, 선언 시 타입을 지정해야 합니다.
- Python의 리스트는 동적으로 크기가 변경되며, 서로 다른 타입의 데이터를 저장할 수 있습니다.
Java에서도 ArrayList와 같은 동적 배열 클래스를 사용할 수 있지만, 이 역시도 타입 지정이 필요하다는 점에서 Python과 큰 차이가 있습니다.
- 이는 성능과 안전성 측면에서 다르게 작용할 수 있습니다.
- 이와 관련해선
List를 다룰때 다시 다루도록 하겠습니다.
3. 배열의 주요 연산
3.1 조회 (Access)
배열에서 특정 인덱스에 있는 값을 조회하는 연산은 O(1)입니다.
Java
int value = numbers[2]; // O(1)Python
value = numbers[2] # O(1)3.2 삽입 (Insert)
배열의 끝에 새로운 데이터를 삽입하는 연산은 O(1)입니다.
하지만 중간에 삽입할 경우 모든 데이터를 이동해야 하므로 O(n)의 시간이 소요됩니다.
Java
// 배열의 크기는 고정이므로 중간 삽입을 위해 새로운 배열을 만들어야 함Python
numbers.insert(2, 25) # 인덱스 2에 25 삽입 (O(n))3.3 삭제 (Delete)
배열에서 데이터를 삭제하는 연산 역시 O(n)입니다.
삭제 후, 뒤에 있는 데이터들을 이동시켜야 하기 때문입니다.
Java
// Java에서는 배열 크기 고정이므로 직접 배열 이동 처리가 필요Python
numbers.pop(2) # 인덱스 2에 있는 값 삭제 (O(n))3.4 배열 복사 (Copying)
Java에서는 배열의 크기를 변경할 수 없기 때문에, 크기가 다른 배열을 만들고 데이터를 복사해야 할 경우가 많습니다.
Java
int[] newNumbers = new int[10];
System.arraycopy(numbers, 0, newNumbers, 0, numbers.length); // 배열 복사Python
new_numbers = numbers.copy() # 리스트 복사- 참고로 Python에서
copy()메서드를 사용하면 얕은 복사가 이루어집니다.- 즉, 리스트 안의 중첩 리스트와 같은 가변 객체들은 원본과 같은 참조를 공유하게 됩니다.
- 만약 깊은 복사가 필요하다면,
copy.deepcopy()를 사용할 수 있습니다.
3.5 정렬 (Sorting)
배열의 정렬은 일반적으로 O(n log n) 복잡도를 가지며, Java는 Arrays.sort() 메서드, Python은 list.sort() 또는 sorted() 함수를 사용합니다.
Java
Arrays.sort(numbers); // 배열 정렬- 참고로 Java의
Arrays.sort()는 기본형 타입 배열에 대해선 내부적으로Dual-Pivot Quicksort를 사용하여 빠르게 정렬을 수행합니다.- 물론 배열 크기나 요소 타입에 따라서 다른 알고리즘들이 쓰이기도 합니다
Quicksort는 평균적으로O(n log n)의 성능을 보장하지만, 최악의 경우O(n^2)이 될 수 있습니다.
Python
numbers.sort() # 리스트 정렬- Python의
list.sort()는Timsort알고리즘을 사용하며, 이는 최악의 경우에도O(n log n)을 보장합니다.
자세한 정렬 알고리즘은 추후에 자세히 다룰 예정입니다.
4. 실습: 배열을 이용한 간단한 문제 해결
문제: 배열에서 최대값 찾기
배열에서 최대값을 찾는 문제를 Java와 Python에서 각각 구현해보겠습니다.
- Java
public class Main {
public static void main(String[] args) {
int[] numbers = {10, 50, 30, 40, 20};
int max = numbers[0];
for (int i = 1; i < numbers.length; i++) {
if (numbers[i] > max) {
max = numbers[i];
}
}
System.out.println("최대값: " + max);
}
}- Python
numbers = [10, 50, 30, 40, 20]
max_value = numbers[0]
for number in numbers[1:]:
if number > max_value:
max_value = number
print(f"최대값: {max_value}")마무리
배열은 매우 기본적인 자료구조이지만, 그 특성과 동작 원리를 이해하는 것은 효율적인 알고리즘을 설계하는 데 필수적입니다.
- Java와 Python에서 배열을 다루는 방식이 다르지만, 각 언어의 장단점을 이해하고 적절하게 활용하는 것이 중요합니다.
다음 포스팅에서는 Java의 ArrayList와 Python의 List를 비교하며, 배열 기반 동적 자료구조에 대해 심도 있게 다뤄보겠습니다.
Array가 고정 크기인 반해서, 동적 배열인Java ArrayList와Python List는 크기를 유연하게 조절할 수 있는 특징을 가지고 있어, 이를 비교 분석해볼 것입니다.
