네 반갑습니다. 부록 B를 바로 시작하겠습니다.

부록답게 내용이 진짜 되게 짧습니다. 연습 문제도 따로 없습니다. 구현을 같이 해볼게 하나 있긴 하지만 그렇게 어렵지는 않을 것입니다.

초심으로 돌아가서 0x03강 – 배열에서 같이 짰던 코드를 잠깐 가져왔습니다. 당시에 이렇게 템플릿을 두고 insert 함수랑 erase 함수를 채워보라고 했는데, 그런데 insert를 여러번 해서 길이가 10 이상이 되면 어떻게 할까요? 그렇다고 하면 arr를 선언할 때 크기를 10 말고 100으로 둔다던가 하는 식으로 더 크게 둘 수 있긴한데, 좀 더 키워서 100으로 뒀다고 하면 insert가 100번 일어났을 때 또 문제가 됩니다. 사실 배열 단원에서는 이런 상황을 아예 언급을 안했습니다. 너무 초반 단원이라 이런 것까지 다루기는 조금 어려웠습니다.

그런데 그럼에도 불구하고 댓글로 혹시 insert가 계속 발생해서 배열 크기를 넘어서면 어떻게 해야하냐 이런 질문을 많이 받았습니다. 만약 본인이 이런 질문을 했거나, 혹은 질문을 댓글로 남가지는 않았더라도 배열 단원을 공부할 당시에 혼자서 이런 의문을 고민해보셨다면 진짜 완전 칭찬드립니다. 정말 좋은, 뭐랄까 프로그래머의 자질이 충분히 있다고 할까요. 이런걸 꼼꼼하게 따지고 뭔가 버그가 터질 것 같은 곳을 잘 잡아내는건 정말 중요한 역량입니다..

배열 단원에서 같이 구현한 것 처럼 단순히 최대 크기를 정해두는 방식 말고 배열의 크기를 필요에 따라 늘렸다 줄였다 하려면 동적 배열이라는 개념이 필요합니다. C에서는 malloc이 쓰입니다. 학부때 이걸 말록이라고 하니까 교수님이 기겁을 했던 그런 기억이 있네요. 아무튼 C에는 malloc과 free를 쓰는데 C++에서는 new와 delete를 씁니다. 저희가 여기서 쓸 상황에서는 둘 다 큰 차이가 없어서 malloc이랑 free만 이전에 알고 있었다라고 해도 코드를 이해하는데에는 큰 문제는 없습니다. 그런데 malloc, new 이런걸 아예 처음 보고 동적할당이라는 개념이 안 익숙하시면 지금 한 번 관련 내용을 찾아보시는걸 추천드립니다. 엄청 깊게 알 필요는 없고 그냥 구글에 C++ 배열 동적 할당 이렇게 검색해서 대충만 파악하면 괜찮습니다.

설명을 다시 이어가면 insert 횟수에 제한을 따로 두고 싶지 않다고 하면 원소들을 담을 배열을 정적 배열에서 동적 배열로 바꾸고 insert를 많이 해서 배열이 꽉 찼을 때 그 크기를 늘려주는 방식으로 해결이 쉽게 될 것 같다는 생각을 할 수 있습니다.

기본적으로는 앞에서 말한게 맞습니다. 앞에서 말한대로 구현을 하면 되는데 사실은 시간복잡도와 관련해서 조금 더 같이 확인해봐야 할게 있습니다. 일단 처음에는 insert를 하다가 공간이 꽉 차면 1칸을 늘릴 계획입니다. 그러니까 1칸을 더 키운 크기만큼의 공간을 할당받으면 됩니다.

이렇게 메모리가 있다고 할 때 처음에는 3칸짜리로 잡아뒀다고 하겠습니다. new로 3칸을 요청하면 알아서 메모리의 어딘가를 받게 됩니다. 그리고 거기에 이렇게 insert가 다 됐다고 하면 4칸을 새로 받아야 하는데 언뜻 생각하기에는 그냥 저 3칸짜리 뒤에다가 받으면 안되나 싶을 수 있습니다. 그런데 아쉽게도 그럴 수는 없습니다. 이런 동적 할당이 실제 내부에서 어떻게 동작하는지는 컴퓨터 구조 같은 더 심화된 교과목을 배우면 알 수 있지만 당장 지금 그런 내용을 다룰건 아니고 어떤 느낌으로 이해를 하실 수 있냐면 메모리는 이곳 저곳에서 다 쓰고 있으니 저 뒤의 칸이 비어있다는 보장이 없습니다. 그래서 4칸을 새로 받게 되면 아예 새로운 곳에서 4칸을 잡게 됩니다.

그래서 분홍색 4칸을 새로 할당을 받았으면 일단 바로 해줘야하는 조치가 있는데 당연히 새롭게 할당을 받으면 저기에 값이 제대로 써있지가 않습니다.

그러면 저 4, 6, 3이라는 값을 옮겨써야 합니다. 그리고 원래 배열의 길이가 N이었다고 하면 이거 자체가 이미 O(N)입니다. 그러면 예를 들어서 마치 vector의 push_back 마냥 insert를 맨 뒤에 한다고 하면 이건 O(1)이기를 기대하는데 배열이 꽉 찼을 경우에는 당장 새 배열을 잡고 데이터를 옮기는 것 만으로 O(N)이 필요합니다. 이건 전혀 원치 않는 상황입니다. 그러면 지금 상황에서는 크기를 1씩 늘리다보니 매번 insert를 할 때 마다 확장이 발생해서 이런거니까 1씩 말고 한 3씩 늘린다고 하면 해결이 가능할까요? 아쉽게도 그렇지 않습니다.

길이를 3씩 늘린다고 하면 insert를 3번 할 때 마다 전체 배열을 복사해야 하니 3번에 한 번씩 O(N)입니다. 그리고 이건 여전히 평균적으로 O(N)입니다. 3이 아니라 100, 1000 이렇게 하더라도 O(N)인건 달라지지가 않습니다.

늘리는 크기를 1000과 같이 엄청 크게 잡으면 이론적으로는 삽입이 O(N)일지언정 사실 1000번에 한 번만 O(N)이고 나머지는 다 O(1)이어서 실제 사용을 하는데에는 크게 문제가 없습니다. 하지만 이 경우에는 길이가 짧은 배열에도 너무 많은 공간을 할당하고 있어야 하는 문제가 있을 수 있습니다. 예를 들어서 길이 50 정도의 배열만 필요한데 확장이 한번 일어나면 바로 내부적으로는 크기가 1000을 넘어버리니 메모리의 관점에서 비효율적입니다.

현재 상황을 다시 정리해보면 배열이 꽉 찼을 때 배열을 1이나 1000 같은 상수 크기만큼 늘리는 방법을 쓰면 삽입의 시간복잡도가 배열의 복사 때문에 평균적으로 O(N)입니다. 늘리는 상수를 엄청 크게 두면 사실 이론적으로는 O(N)이라도 현실적으로 쓸 때에는 실행 시간이 크게 문제가 되지 않을 수 있지만 그렇게 되면 낭비하는 공간이 너무 많아질 수 있습니다.

여기서 놀랍게도 시간복잡도도 평균적으로 O(1)이고 공간도 낭비하지 않는 방법이 있습니다. 방법 자체는 되게 간단한데, 배열 크기를 상수 크기만큼 늘리는게 아니라 2배씩 늘리면 됩니다. 예를 들어서 원래 크기가 3이었다면 꽉 찼을 때 6으로 늘리고 그 다음으로 다시 꽉 차면 12로 늘립니다. 이렇게 하면 평균적으로 O(1)이 됩니다. 엄밀하게 말하면 amortized O(1)이라고 하는데 좀 낯선 단어일 것 같습니다. 일단 저게 왜 O(1)인건지 좀 감이 안올거라 설명을 더 드리겠습니다.

바로 그냥 수식을 놓고 따져볼건데 편의상 시작 길이는 1이고 크기가 2배씩 커진다고 하겠습니다. 그러면 배열의 크기는 1, 2, 4, 8, ... 이렇게 2의 거듭제곱이 되고 또 다르게 표현하면 배열의 크기가 1, 2, 4, 8, ... 일 때 확장이 이루어집니다. 그리고 insert를 총 N = 2^k번 한다고 할 때의 전체 시간복잡도를 생각해보겠습니다.

일단 N번, 즉 2^k번 insert를 할 때 마다 뒤에 대입을 하는 1번의 연산은 필요하고, 그리고 크기가 1, 2, 4, ..., 2^k일 때 확장이 발생하는데 확장이 이루어질 때 마다 현재 크기만큼의 데이터를 옮겨야 하니 시간복잡도에 1 + 2 + 4 + ... + 2^k가 추가됩니다. 다 합하면 대략 3N정도 나오고 이건 O(N)이라고 볼 수 있습니다. 즉 N번 insert를 할 때 O(N)이 들기 때문에 1번의 insert는 O(N)을 N으로 나눠서 O(1)이다, 정확히는 Amortized O(1)이다라고 표현을 합니다.  엄밀히 따졌을 때 Amortized는 평균, 즉 Average와 약간의 뉘앙스 차이가 있지만 그 디테일은 그냥 넘어가고 결론적으로 2배 확장을 하는 기법을 사용하면 삽입이 O(1)이 된다고 이해를 하겠습니다. Amortized의 정확한 정의를 여기서 다루지는 않을거지만 어떤 느낌만 가져가시면 되냐면, 딱 한번 insert를 하면 운이 나쁠 경우엔 하필 그 때 확장하는 타이밍에 딱 걸려서 O(N)이 될 수 있습니다. 하지만 insert를 여러번 하면 반드시 평균적으로 O(1)이 된다는걸 알면 됩니다.

이 동적배열을 같이 구현을 해보겠습니다. 그런데 일단 기본적으로 동적 배열이 필요하면 vector를 쓰면 됩니다. vector를 안쓰고 굳이 이걸 직접 구현을 할 일은 없습니다. 그전에는 그나마 삼성 B형 때문에 이런걸 습득하기도 했는데 2024년 1월 기준으로 이제 삼성 B형도 STL을 쓸 수 있게 해주기도 해서 더 필요가 없습니다. 그래서 그냥 vector의 동작 원리를 이해한다는 차원에서, 또 거기에 더해 구현 연습을 한다는 차원에서 같이 구현을 해보겠습니다.

배열 단원에서 했던 것과 약간은 비슷한데, 큰 차이는 배열이 동적 배열이 됐고 그리고 capacity라는 새 변수가 생겼습니다. capacity는 arr 배열이 점유하고 있는 크기를 의미합니다. 다르게 표현하면 삽입이 가능한 최대 크기입니다. 그리고 이전에는 길이를 신경쓰지 않고 그냥 막 insert 함수에서 삽입을 처리하는 12번째 줄에서 15번째 줄의 코드를 실행시키면 됐는데 이번에는 그렇지가 않고 어떤 조건이 만족되면 배열을 확장해줘야 합니다. 그 조건은 08번째 줄에 잘 채워넣으면 되고, 또 확장을 어떤 식으로 해야할지는 expand 함수에 구현을 해보면 됩니다. 실제 깃헙 링크에 들어가서 insert_test 함수를 보면 거기에 삽입이 발생할 때 마다 len, capacity 값이 어떻게 되는지를 적어놔서 상황을 이해하는데에 도움이 될 수도 있습니다. 다음 슬라이드에 바로 답이 나옵니다.

우선 22번째 줄의 조건을 보면, 확장은 len과 capacity가 같을 때 이루어져야 합니다. len과 capacity가 같다는건 더 이상 삽입이 불가능하다는 뜻이기 때문입니다. 그리고 expand를 보면 그냥 2 * capacity 크기의 새 배열 tmp를 잡고, arr에 있던 데이터를 tmp로 옮겨준 다음에 arr를 tmp로 바꾸면 됩니다. 포인터에 익숙하지 않으면 약간 헤멜 수는 있지만 제 생각에 이정도는 당장은 헷갈리더라도 약간만 시간을 들여서 보면 충분히 이해할 수 있을 것 같아서 더 설명은 하지 않겠습니다.

그런데 하나 생각해볼 점은, 문제 풀이를 할 때 사실 동적 배열을 1개 쓸거면 동적 배열을 굳이 써야 할 필요가 없습니다. 1개밖에 없으면 애초에 메모리 제한을 전혀 걱정할 필요가 없는 상황입니다. 그러면 그냥 스택/큐/덱 단원에서 하던 것 처럼 배열을 처음에 엄청 크게 잡아버리면 됩니다. 그래서 동적 배열이 여러개 필요해야 이걸 직접 구현해서 정말 쓰임새 있게 쓸 수 있는거고 그렇게 여러개를 쓰려면 이거를 클래스로 만들어놓는게 좋습니다. 새 문법을 안건드리고 싶어서 여기 구현체에서는 클래스를 안쓰고 죄다 전역 변수로 뒀지만, 진짜 동적 배열을 제대로 써먹고 싶다 하면 클래스로 만들어보는걸 추천드립니다. 그런데 사실 앞에서도 말했지만 그냥 vector를 쓰면 되고 굳이 내가 직접 동적 배열을 짤 일은 없긴 합니다. (링크)

이렇게 동적 배열 단원이 스무스하게 끝났습니다. 뭐 엄청 특별한건 없고 vector의 내부 동작 원리를 이해하는 차원에서 설명을 드렸으니 혹시 vector가 실제로는 어떻게 구현이 되어있나 궁금하셨다면 이 강의를 통해서 의문을 해결하실 수 있었을 것입니다. 연습 문제도 따로 없으니 가볍게 본걸로 만족하고 강의를 마치도록 하겠습니다..