Array
배열은 가장 흔하게 사용되는 자료구조입니다. 파이썬에서는 리스트라고 부릅니다. 배열과 리스트의 차이는 길이가 고정되어 있느냐 아니냐의 차이입니다. 배열은 길이가 선언시에 정해지며 바꿀 수 없습니다. 반면, 리스트는 길이가 고정되어 있지 않습니다. 파이썬에서는 기본적으로 리스트를 사용하고, C++에서는 vector<T>를 통해 리스트를 사용할 수 있습니다.
배열은 메모리에 일자로(연속으로) 나열되어 있는 형태를 가지고 있습니다. 예를 들어 4바이트 int배열 a의 0번째 요소가 0x100에 있었다면 1번째 요소는 0x104에 있게 됩니다. 이런 특성 덕분에 시작 요소의 주소를 알고, 몇 번째 요소에 접근하고 싶은지 알고 있다면 그 요소의 주소를 바로 알 수 있게 됩니다. 이런 특성 덕분에 i 인덱스에 있는 값을 가져오는 연산은 \( O(1) \)에 처리됩니다. 즉, 맨 앞 요소부터 하나씩 순회하며 찾지 않아도 됩니다. 간결하게 수식으로 표현해 보면 다음과 같습니다.
배열은 연속된 메모리를 할당해야 하기 때문에 너무 큰 크기의 배열을 요청하면 실패할 수도 있습니다. 이런 경우 Segmentation Fault를 내며 프로그램이 죽습니다.
파이썬의 경우 대부분 문제가 없지만. C++에서는 지역변수로 너무 큰 배열을 선언하면 문제가 생길 수 있습니다. 메모리는 크게 스택, 힙, 데이터, 코드 영역으로 나뉘는데 지역변수는 스택 영역에 할당됩니다. 스택 영역에는 큰 메모리를 할당할 수 없기 때문에 지역변수로 너무 큰 배열을 선언하면 실행에 실패할 수 있습니다. 전역변수로 할당하거나 vector, 동적 할당(malloc, new)을 사용하면 힙 영역에 할당되기 때문에 더 큰 메모리를 선언할 수 있습니다.
C++ 배열 초기화
C++에서는 배열을 지역 변수로 만들면 값이 자동으로 초기화 되지 않고 쓰레기 값이 들어있게 됩니다. 전역변수는 기본값(0)으로 초기화되지만 지역변수는 그렇지 않으므로 항상 입력을 받거나 초기화하는 과정을 거쳐야 합니다. C++에서는 배열을 초기화하는 여러 방법이 있습니다. 하나는 algorithm 헤더의 std::fill 함수를 사용하는 것입니다.
int a[n];
fill(a, a + n, 1e9);fill은 \( O(n) \)의 시간복잡도를 가집니다. 메모리의 시작 지점부터 끝 지점까지 세번째 인자로 주어진 값으로 초기화합니다. 1차원 배열을 초기화하기 좋고 원하는 아무 값이나 초기화할 수 있다는 장점이 있습니다.
다른 방법으로 memset 함수를 사용할 수도 있습니다. memset은 이름처럼 메모리를 그대로 설정하는 방식입니다. 인자로 배열의 시작주소, 값, 크기를 전달합니다.
int a[10];
memset(a, 10, sizeof(a));위 코드는 a의 0번째 바이트부터 시작해 sizeof(a)바이트까지 10으로 채우라는 뜻입니다. 여기서 헷갈리면 안되는 부분은 *바이트*단위로 채운다는 것입니다. 따라서, 위 코드는 a의 모든 원소를 10으로 초기화하지 않습니다.실제로 실행해 보면 168430090이라는 값을 가지고 있습니다. 이를 2진수로 나타내 보면
00001010 00001010 00001010 00001010이렇게 각 바이트가 모두 10으로 초기화된 것을 볼 수 있습니다. 즉, memset은 바이트 단위로 데이터를 쓰기 때문에 1바이트 자료형이 아닌 경우 원하는 값으로 채우기 힘듭니다. 0, -1 처럼 모든 비트가 같다면 memset으로도 커버가 가능합니다. 또, 0x3f 같은 값을 넣으면 1,061,109,567으로 대략 \( 10^9 \)에 가까운 숫자로 채울 수 있습니다. 1e9는 infinity를 나타내는 값으로 자주 쓰이니 0x3f로 memset해서 같은 효과를 낼 수 있습니다.
몇몇 값밖에 채우지 못하지만 memset을 설명하는 이유는 fill이 할 수 없는 장점이 있기 때문입니다. fill은 1차원 배열밖에 채우지 못합니다. 반면 memset은 메모리 자체를 채우기 때문에 배열의 차원과는 상관이 없습니다. 그리고 많은 경우 배열을 0, -1, INF 중 하나로 초기화 하기 때문에 사용에 크게 지장이 없습니다.
Vector
C++의 vector헤더에 있는 std::vector<T>는 파이썬의 리스트와 비슷합니다.
리스트와 벡터는 길이가 정해지지 않은 배열입니다. 요소를 추가할 수도 있고 삭제할 수도 있습니다. 그렇다면 내부적으로는 어떻게 구현되어야 가능할까요? 내부적으로는 일반 배열처럼 메모리에 연속된 값을 가지는 형태로 되어 있습니다. 만약 길이가 \( n \)인 배열이 있었는데 뒤에 요소를 하나 추가하려고 합니다. 하지만, 할당받은 메모리는 \( n \)개의 데이터만 저장할 수 있습니다. 이런 경우 더 큰 메모리를 다시 할당받고 기존의 값들을 모두 복사한 뒤 맨 뒤에 새로운 값을 넣어주는 과정을 거치게 됩니다.
하지만 리스트와 벡터에서 맨 뒤에 값을 append(push) 해주는 작업은 매우 빈번하게 일어나는데 매번 \( O(\text{len}(a)) \)의 시간복잡도를 갖는 작업을 수행하기에는 굉장히 비효율적입니다. 메모리를 매번 할당, 복사, 해제하는 과정은 매우 비쌉니다. 그래서 최대한 새로운 메모리를 할당하는 것을 줄이기 위해 새로운 메모리를 할당받을 때 \( n + 1 \)개를 받는 것이 아닌 \( 2n \)개를 받습니다. 따라서 \( \lg n \)번 정도 복사가 일어날 것을 예상할 수 있습니다. (참고로 모든 언어에서 2배를 할당하지는 않습니다. 컴파일러마다 다르지만 상황에 맞게 적절한 배수를 가지고 over-allocating을 진행합니다.)
그럼 중간에 값을 추가하면 어떤 일이 벌어질까요? 중간에 값을 추가하려면 먼저 빈 공간을 만들어야 합니다. 그래서 값이 들어갈 인덱스를 비우기 위해 \( i \)번째 요소를 \( i+1 \)로 옮기게 됩니다. 만약, 배열의 메모리가 꽉 찼다면 새로운 메모리를 할당받아서 복사까지 해야겠네요. 마지막으로 빈 칸에 원하는 값을 넣으면 됩니다. 따라서 중간에 값을 추가하는 일은 \( O(n) \)의 시간복잡도를 갖습니다.
이번에는 중간에 값을 없에보겠습니다. 값을 없에면 구멍이 뚫리는데 그 구멍을 매꿔줘야 합니다. 즉, 뒤의 원소들을 한 칸씩 앞으로 끌어당겨야 합니다. 따라서 \( O(n) \)의 시간복잡도를 갖습니다.
이렇게 중간에 값을 추가, 삭제하는 과정은 꽤 오랜 시간이 걸립니다. 만약 본인이 배열에서 중간에서 추가, 제거가 빈번하게 일어난다면 정말 필요한 일인지 검토해 보고, 필요하다면 ArrayList가 아니라 LinkedList나 Queue, Stack 등 다른 자료구조를 고려해 보는 것이 좋습니다.
벡터는 선언시 템플릿으로 타입을 지정해 주어야 합니다. 그리고 생성자의 파라미터로 값의 개수, 기본값을 지정할 수 있습니다. 개수를 지정하지 않으면 빈 배열이 되고 기본값이 없으면 0으로 초기화됩니다. 아래 코드는 길이가 10인 벡터를 만들고 모든 값을 -1로 초기화합니다.
vector<int> a(10, -1);또, reserve를 통해 미리 메모리를 할당해 놓을 수도 있습니다. reserve는 벡터의 크기를 바꾸지는 않지만, 미리 메모리를 할당해 놓고 나중에 push를 수행할 때 메모리 재할당이 일어나지 않도록 도와줍니다. 들어올 데이터의 개수를 미리 알고 있는 경우 유용합니다. 아래 코드는 길이가 0인 벡터를 만들고 10개의 메모리를 미리 할당해 놓습니다.
vector<int> a;
a.reserve(10);