코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 반복자는 내부적으로 포인터로 구현되어 있다. 그러므로 특정 노드 또는 원소의 주소가 바뀌면 그 주소를 갖는 반복자는 무효화될 수 있고 Crash로 이어질 수 있다. std::vector에서의 반복자 무효화 삽입 시 용량 부족으로 메모리가 재할당 된 경우 발생할 수 있다. 중간에 원소를 삽입하여 뒤 원소들의 위치가 밀린 경우 발생할 수 있다. (용량이 충분하더라도 기존 주소를 포인터가 아닌 값으로 직접 참조하는 것으로 인식하여 오류 발생) std::list에서의 반복자 무효화 삽입/삭제 시에는 원소의 이동이 필요치 않으므로 발생하지 않는다. 할당 해제된 주소를 참조하는 경우만 주의하면 된다. #include #include #include using..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ std::forward_list의 단점 성능상 이유로 마지막에 원소 추가, 역방향 진행, 크기 반환 등을 지원하지 않는다. 빠른 원소 삽입에 적합한 컨테이너는 아니다. std::list STL에서 제공하는 이중 연결 리스트 컨테이너이다. 양방향 반복자를 제공한다. 마지막에 원소 추가, 크기 반환을 지원한다. std::list의 성능 삽입, 삭제 연산시 2개의 포인터를 처리해야 하므로 std::forward_list보다는 시간이 좀 더 걸린다. 크기를 저장하므로 크기 반환은 O(1)에 수행된다. 원소의 삽입 삭제는 O(1)에 수행된다. (삽입할 위치 전의 반복자를 알고 있다는 전제 하에) 특정 위치의 원소를 참조하기 위해서는 반복자를 직접 진행해야 ..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 임의 접근 반복자(Randon Access Iterator) 특정 위치의 원소에 바로 접근할 수 있는 반복자 vector, array 등에서 사용된다. 순방향 반복자(Forward Iterator) 한 쪽 방향으로만 진행하고 증가 연산만 가능한 반복자 forward_list에서 사용된다. 양방향 반복자(Bidirectional Iterator) 양쪽 방향으로 진행 가능하고 증감 연산을 지원하는 반복자 대부분의 STL 컨테이너에서 지원한다. 반복자의 성능 vector, array에서 next(), prev()는 O(1)에 수행된다. forward_list, list에서 next(), prev()는 선형 시간이 소요된다. std::iterator 앞에..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ std::vector의 단점 중간에 원소를 추가/삭제하는 작업이 O(n)으로 매우 비효율적이다. std::forward_list STL에서 제공하는 단일 연결 리스트 컨테이너이다. 단일 연결 리스트이기 때문에 순방향 반복자만을 지원한다. (그렇기 때문에 std::sort가 아닌 컨테이너 자체적으로 sort 함수를 제공한다.) 메모리나 성능을 극단적으로 최적화해야 하는 경우가 아니라면 std::list를 사용하는 것이 보통이다. std::forward_list의 성능 성능 유지를 위해 O(n) 복잡도의 크기 반환, 중간 원소 접근을 제공하지 않는다. 원소의 삽입은 O(1) 복잡도를 갖는다. (삽입할 위치 전의 반복자를 알고 있다는 전제 하에) std..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ std::array의 문제점 Compile time에 크기가 정해져야 하며 실행 도중 변경할 수 없다. 크기가 고정되어 있어 원소의 추가, 삭제가 불가능하다. 항상 스택 영역을 사용한다. std::vector 공간이 부족할 경우 크기가 동적으로 늘어난다. - 보통 2배 크기와 용량이 별도로 존재한다. 두 벡터의 크기가 달라도 비교 연산이 지원된다. std::vector의 성능 맨 뒤에 삽입 시 크기가 충분하면 O(1), 부족하면 모든 원소를 새로운 메모리에 복사해야 하므로 O(n) 중간에 원소를 삽입하는 경우 O(n) std::vector의 원소 삽입 의사 코드 push_back(val): if size < capacity data[size++] ..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ #include #include #include using namespace std; template class dynamic_array { private: T* data; size_t n; public: dynamic_array(size_t n) : data(new T[n]), n(n) {} dynamic_array(const dynamic_array& other) { n = other.n; data = new T[n]; for (int i = 0; i < n; ++i) data[i] = other[i]; } friend dynamic_array operator+(const dynamic_array& da1, const dynamic_array&..