[자료구조] 배열(Array) 완벽 정리: 작동 원리와 코딩 테스트 활용 전략
카테고리: Algorithm Theory
1. 🔍 배열 개념
연속된 메모리 공간에 동일한 타입의 데이터를 순차적으로 저장하는 자료구조이다. 각 요소는 인덱스를 통해 접근 가능하다.
학생 1,000명의 수학 점수를 각각 정수형 변수 1,000개로 관리할 수도 있지만 시간이 오래 걸리고 따로 관리해야 하는 어려움이 있다. 배열은 하나의 변수 이름으로 동일한 타입의 데이터를 그룹화하여 관리할 수 있고 인덱스를 활용해 원하는 데이터에 임의 접근할 수 있다는 장점이 있다.
💯 배열의 특징
- 빠른 접근 속도: 인덱스를 통해 $O(1)$ 시간 복잡도로 접근이 가능하다.
- 메모리 효율성: 연속된 메모리 공간에 저장되어 메모리 낭비가 적다.
- 데이터 타입 제한: 배열은 동일한 타입의 데이터만 저장할 수 있다.
🚀 배열의 효율성
배열 연산의 시간 복잡도를 확인하고 배열의 효율성을 알아보자.
배열 연산의 시간 복잡도
- 배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근할 수 있다. 따라서 데이터에 접근하기 위한 시간 복잡도는 $O(1)$이다.
- 배열에 데이터를 삽입하는 경우는 어디에 저장하느냐에 따라 삽입 연산에 대한 시간 복잡도가 달라진다.
- 삭제 연산의 경우도 삽입과 같은 시간 복잡도를 가진다.
맨 뒤에 삽입할 경우
- 다음과 같은 배열이 있을 때 2를 추가한다고 가정하자. 맨 뒤에 삽입할 때는
arr[3]에 임의 접근을 바로 할 수 있으며 데이터를 삽입해도 다른 데이터 위치에 영향을 주지 않는다. 따라서 시간 복잡도는 $O(1)$이다. - 배열 뒤에 메모리가 예약되어 있을 경우 $O(1)$의 시간 복잡도를 가지며, 예약되지 않으면 메모리 이동이 필요하므로 더 많은 연산이 필요하다.
맨 앞에 삽입할 경우
맨 앞에 삽입할 경우 기존 데이터들을 뒤로 한 칸씩 밀어야 한다. 즉, 미는 연산이 필요하다. 데이터 개수를 $N$개로 일반화하면 시간 복잡도는 $O(N)$이 된다.
중간에 삽입할 경우
3 앞에 데이터를 삽입한다면 3 이후의 데이터를 뒤로 한 칸씩 밀어야 한다. 다시 말해 현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 밀어내는 연산을 해야 한다. 밀지 않아도 되는 데이터가 있어서 시간 복잡도가 $N$보다 작다고 생각할 수 있지만 시간 복잡도는 데이터 개수인 $N$을 기준으로 상수를 빼고 더하더라도 $O(N)$이다.
💡 배열을 선택할 때 고려할 점
데이터에 자주 접근하거나 읽어야 하는 경우 배열을 사용하면 좋은 성능을 낼 수 있다. 하지만 배열은 메모리 공간을 충분히 확보해야 하는 단점도 있다. 따라서 코딩 테스트에서는 다음 사항을 고려해 배열을 선택해야 한다.
- 할당할 수 있는 메모리 크기를 확인해야 한다. 배열로 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당에 실패할 수 있다. OS마다 배열을 할당할 수 있는 메모리의 한계치는 다르지만 보통 정수형 1차원 배열은 1,000만 개, 2차원 배열은 3,000 * 3,000 크기를 최대로 생각한다.
- 중간에 데이터 삽입이 많은지 확인해야 한다. 배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아져 실제 시험에서 시간 초과가 발생할 수 있다. 마지막에 삽입하는 경우라도 메모리가 예약되어 있지 않다면 다른 위치의 메모리로 이전 데이터들을 복사해야 하는 비용이 발생하므로 좋지 않다.
💡 배열의 메모리 구조
- 왼쪽은 2차원 배열을 사람이 이해하기 쉽도록 2차원으로 표현한 것이고, 오른쪽은 실제 메모리에 2차원 배열이 저장된 상태를 표현한 것이다.
- 배열로 선언한 변수들은 메모리의 연속된 공간에 할당된다. 배열의 원소 간 주소값은 변수 크기만큼 차이난다.
- C++에서는 배열의 원소 간 주소값은 변수 크기만큼 차이나지만 Python에서는 배열의 원소 간 주소값이 변수 크기만큼 차이나지 않는다.
C++
변수명 앞에
&를 붙이면 해당 변수의 주소값을 연산한다.
#include <iostream>
#include <string>
int main() {
int int_arr[3] = {1, 2, 3};
double double_arr[3] = {1.1, 2.2, 3.3};
char char_arr[3] = {'a', 'b', 'c'};
std::string string_arr[3] = {"hello", "world", "foo"};
for (int i = 0; i < 3; i++) {
std::cout << &int_arr[i] << " " << &double_arr[i] << " "
<< static_cast<void*>(&char_arr[i]) << " " << &string_arr[i]
<< std::endl;
}
return 0;
}
// int_arr double_arr char_arr string_arr
// 0x7ffc00be5244 0x7ffc00be5250 0x7ffc00be5231 0x7ffc00be5270
// 0x7ffc00be5248 0x7ffc00be5258 0x7ffc00be5232 0x7ffc00be5290
// 0x7ffc00be524c 0x7ffc00be5260 0x7ffc00be5233 0x7ffc00be52b0
Python
# Python equivalent
int_arr = [1, 2, 3]
float_arr = [1.1, 2.2, 3.3]
char_arr = ['a', 'b', 'c']
string_arr = ["hello", "world", "foo"]
for i in range(3):
print(f"int_arr[{i}]: {hex(id(int_arr[i]))}, ", end="")
print(f"float_arr[{i}]: {hex(id(float_arr[i]))}, ", end="")
print(f"char_arr[{i}]: {hex(id(char_arr[i]))}, ", end="")
print(f"string_arr[{i}]: {hex(id(string_arr[i]))}")
# 출력 예시:
# int_arr[0]: 0x7f8b1c0141b0, float_arr[0]: 0x7f8b1c014230, char_arr[0]: 0x7f8b1c0142a0, string_arr[0]: 0x7f8b1c014310
# int_arr[1]: 0x7f8b1c0141d0, float_arr[1]: 0x7f8b1c014250, char_arr[1]: 0x7f8b1c0142c0, string_arr[1]: 0x7f8b1c014330
# int_arr[2]: 0x7f8b1c0141f0, float_arr[2]: 0x7f8b1c014270, char_arr[2]: 0x7f8b1c0142e0, string_arr[2]: 0x7f8b1c014350
- 위 코드에서
int_arr를 그림으로 그리면 다음과 같다. - 이렇게 메모리 주소가 연속적이라는 특징이 있어 배열은 인덱스를 활용하여 특정 원소에 임의 접근(random access)할 수 있다.
2. 📦 배열 사용하기
⚡ 1차원 배열
C++
#include <iostream>
int main() {
// all arr are have size 5
int arr1[] = {1, 2, 3, 4, 5};
int arr2[5] = {1, 2}; // only the first 2 elements are initialized to 1 and 2
int arr3[5] = {}; // every element is initialized to 0
int arr4[5]; // no initialization & every element is garbage value
return 0;
}
Python
# Python에서의 배열(리스트) 선언
arr1 = [1, 2, 3, 4, 5] # 리스트 직접 초기화
arr2 = [1, 2] + [0] * 3 # [1, 2, 0, 0, 0]
arr3 = [0] * 5 # 모든 원소를 0으로 초기화
arr4 = [None] * 5 # None으로 초기화
⚡ 다차원 배열
- 배열은 2차원 배열, 3차원 배열과 같이 다차원 배열을 사용할 수 있다.
- 컴퓨터 메모리의 구조는 1차원이므로 2차원, 3차원 배열도 실제로는 1차원 공간에 저장한다.
- 2차원 배열은 1차원 배열을 확장한 형태이다. 2차원 배열 데이터에 접근하는 방법은 1차원 배열과 비슷하다. 행과 열을 명시해
[ ]연산자를 2개 연이어 사용한다는 점만 다르다.
C++
#include <iostream>
int main() {
// 2 dimensional array assignment
int arr[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
};
// print the last element of the last row
std::cout << arr[2][3] << std::endl; // 12
arr[2][3] = 13; // assign 13 to the last element of the last row
// print the last element of the last row
std::cout << arr[2][3] << std::endl; // 13
return 0;
}
Python
# 2 dimensional array (list) assignment
arr = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]
# print the last element of the last row
print(arr[2][3]) # 12
arr[2][3] = 13 # assign 13 to the last element of the last row
# print the last element of the last row
print(arr[2][3]) # 13
C++로 코딩 테스트를 풀 때는 직접 배열을 사용하기보다 STL에서 제공하는 std::vector를 사용한다. 배열 자체만으로 문제가 많이 나오지 않으므로 면접 준비를 위해 개념을 이해하자.