Vector

문제 인식 C++ STL의 vector는 push_back()을 통해 배열의 원소를 계속 늘릴 수 있다. 그러나, vector가 처음 선언될 때 예약되어 있던 '용량'을 초과해버리면, 그보다 더 '큰' (2배 정도) 용량의 메모리를 할당한 후 기존의 원소를 모두 복사하고, 기존의 메모리는 해제하는 작업을 거친다. 즉, 이 작업에는 할당 -> 복사 -> 해제의 비용이 들어간다. 이 작업의 시간 복잡도는 O(1)로 알려져있으나 이는 엄연히 Amotized Analysis 즉, 분할 상환 분석법을 통해 구해진 시간 복잡도일 뿐이며, 최악의 경우 O(N)까지 시간 복잡도가 커질 수 있다. 한 마디로, 재할당이 많이 일어나면 일어날 수록 성능이 매우 떨어진다는 의미이다. 실제로 BOJ 문제에서 이로 인해 시간 초..