배열(Array)
카테고리: Algorithm Theory
1 배열 개념
배열은 같은 타입의 원소들을 효율적으로 관리할 수 있는 기본 자료형이다. 같은 타입의 변수가 여러 개 필요한 경우 사용한다.
학생 1000명의 수학 점수를 각각 정수형 변수 1000개로 관리할 수도 있지만 시간이 오래걸리고 따로 관리해야 하는 어려움이 있다. 배열은 하나의 변수 이름으로 동일한 타입의 데이터를 그룹화하여 관리할 수 있고 인덱스를 활용해 원하는 데이터에 임의 접근할 수 있다는 장점이 있다.
배열 선언
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
파이썬에서는 리스트(list)를 사용하여 배열을 구현
# 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차원 공간에 저장한다. 다시 말해 배열은 차원과는 무관하게 메모리에 연속 할당된다.
배열의 접근 및 제어
배열로 선언한 변수들은 메모리의 연속된 공간에 할당된다. 배열의 원소 간 주소값은 변수 크기만큼 차이난다. 변수명 앞에 &를 붙이면 해당 변수의 주소값을 연산한다.
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차원 배열
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
왼쪽은 2차원 배열을 사람이 이해하기 쉽도록 2차원으로 표현한 것이고, 오른쪽은 실제 메모리에 2차원 배열이 저장된 상태를 표현한 것이다. 실제 메모리에는 1차원 공간에 연속적으로 저장한다.
2 배열의 효율성
배열 연산의 시간 복잡도를 확인하고 배열의 효율성을 알아보자.
배열 연산의 시간 복잡도
배열 데이터에 접근할 때의 시간 복잡도를 알아보자. 배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근할 수 있다. 따라서 데이터에 접근하기 위한 시간 복잡도는 $O(1)$이다. 배열에 데이터를 추가하는 경우는 어디에 저장하느냐에 따라 추가 연산에 대한 시간 복잡도가 달라진다. 삭제 연산의 경우도 추가와 마찬가지의 시간 복잡도를 가진다.
맨 뒤에 삽입할 경우
다음과 같은 배열이 있을 때 2를 추가한다고 가정하자. 맨 뒤에 삽입할 때는 arr[3]에 임의 접근을 바로 할 수 있으며 데이터를 삽입해도 다른 데이터 위치에 영향을 주지 않는다. 따라서 시간 복잡도는 $O(1)$이다.
맨 앞에 삽입할 경우
맨 앞에 삽입할 경우 기존 데이터들을 뒤로 한 칸씩 밀어야 한다. 즉, 미는 연산이 필요하다. 데이터 개수를 $N$개로 일반화하면 시간 복잡도는 $O(N)$이 된다.
중간에 삽입할 경우
3 앞에 데이터를 삽입한다면 3 이후의 데이터를 뒤로 한 칸씩 밀어야 한다. 다시 말해 현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 밀어내는 연산을 해야 한다. 밀지 않아도 되는 데이터가 있어서 시간 복잡도가 $N$보다 작다고 생각할 수 있지만 시간 복잡도는 데이터 개수인 $N$을 기준으로 상수를 빼고 더하더라도 $O(N)$이다.
배열의 경우 삽입하는 위치에 따라 시간 복잡도가 다르지만 전반적으로 $O(N)$이므로 추가 삭제에 드는 비용이 크다.
배열을 선택할 때 고려할 점
데이터에 자주 접근하거나 읽어야 하는 경우 배열을 사용하면 좋은 성능을 낼 수 있다. 하지만 배열은 메몰 공간을 충분히 확보해야 하는 단점도 있다. 따라서 코딩 테스트에서는 다음 사항을 고려해 배열을 선택해야 한다.
- 할당할 수 있는 메모리 크기를 확인해야 한다. 배열로 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당에 실패할 수 있다. OS마다 배열을 할당할 수 있는 메모리의 한계치는 다르지만 보통 정수형 1차원 배열은 1,000만 개, 2차원 배열은 3,000 * 3,000 크기를 최대로 생각한다.
- 중간에 데이터 삽입이 많은지 확인해야 한다. 배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아져 실제 시험에서 시간 초과가 발생할 수 있다. 마지막에 삽입하는 경우라도 메모리가 예약되어 있지 않다면 다른 위치의 메모리로 이전 데이터들을 복사해야 하는 비용이 발생하므로 좋지 않다.
C++로 코딩 테스트를 풀 때는 직접 배열을 사용하기보다 STL에서 제공하는 std::vector를 사용한다. 배열 자체만으로 문제가 많이 나오지 않으므로 면접 준비를 위해 개념을 이해하자.