Array
배열은 가장 흔하게 사용되는 자료구조입니다. 파이썬에서는 리스트라고 부르기도 합니다. C++과 파이썬의 배열은 차이가 있습니다. C++의 배열은 처음 지정한 크기를 벗어나지 못하고 한 종류의 자료형만 저장할 수 있습니다. 파이썬에서는 insert, remove등 메소드를 이용해 값을 추가하거나 삭제할 수 있습니다.
배열은 메모리에 일자로(연속으로) 나열되어 있는 형태를 가지고 있습니다. 예를 들어 4바이트 int배열 a의 0번째 요소가 0x100에 있었다면 1번째 요소는 0x104에 있게 됩니다. 이런 특성 덕분에 시작 요소의 주소를 알고, 몇 번째 요소에 접근하고 싶은지 알고 있다면 그 요소의 주소를 바로 알 수 있게 됩니다. 이런 특성 덕분에 i 인덱스에 있는 값을 가져오는 연산은 \( O(1) \)에 처리됩니다. 즉, 맨 앞 요소부터 하나씩 순회하며 찾지 않아도 됩니다. 이런 배열을 ArrayList라고 부르기도 합니다. 대신, 연속된 메모리를 할당해야 하기 때문에 너무 큰 크기의 배열을 요청하면 실패할 수도 있습니다. 이런 경우 Segmentation Fault를 내며 프로그램이 죽습니다. 대부분 너무 큰 배열을 선언하는 코드는 잘못되었을 확률이 높으니 다른 방법을 찾는게 좋습니다.
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의 값이 10으로 초기화되기를 기대했지만 실제로 실행해 보면 168430090이라는 값을 가지고 있습니다. 이를 2진수로 나타내 보면
00001010 00001010 00001010 00001010이렇게 각 바이트가 모두 10으로 초기화된 것을 볼 수 있습니다. 즉, memset은 바이트 단위로 데이터를 씁니다. 따라서 특정 값을 제외하면 원하는 값으로 채울 수 없습니다. 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으로 초기화됩니다.
vector<int> a(10, -1);또, 메모리를 전부 쓸 때마다 다시 할당하는 것을 막기 위해 얼마나 사용할지 미리 알려줄 수 있습니다. 그러면 한 번의 메모리 할당만 진행하고 불필요한 재할당을 피할 수 있습니다.
vector<int> a;
a.reserve(10);여기서 reserve는 실제로 값을 초기화 하지는 않습니다. 즉, 저 배열 a는 0개의 요소를 가지고 있지만 10개 만큼의 메모리를 미리 할당해 놓게 됩니다.