코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 배열, 벡터, 리스트, 덱 등의 선형 구조에서는 순방향과 역방향으로 원소를 순회할 수 있다. 하지만 다음과 같은 문제는 선형 구조로 표현할 수 없다. 계층적 문제: 회사의 조직도, 대학의 교과 과정 계층도 순환 종속성 문제: SNS의 친구 관계, 도시의 도로망 트리(Tree) 계층적 문제를 표현할 수 있는 자료 구조이다. 데이터가 저장되는 노드(Node)와 노드 사이를 잇는 간선(Edge)으로 표현된다. 자식(Child) 노드에 대한 참조를 가지며 부모(Parent) 노드에 대한 참조도 가질 수 있다. 그래프(Graph) 순환 종속성 문제를 표현할 수 있는 자료 구조이다. 데이터가 저장되는 정점(Vertex)과 정점 사이를 잇는 간선(Edge)으로..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ std::priority_queue STL에서 제공하는 우선순위 큐 컨테이너 어댑터이다. 기본적으로 std::vector가 컨테이너로 사용된다. 기본 비교자로 std::less가 사용되며, 가장 큰 수가 가장 위에서 높은 우선 순위를 갖는 최대 힙(Max Heap)을 생성한다. std::greater를 사용하면 가장 작은 수가 가장 높은 우선 순위를 갖는 최소 힙(Min Heap)이 생성된다. 순회할 필요가 없으므로 반복자를 제공하지 않는다. Root 이외의 원소는 접근할 수 없다. std::priority_queue의 성능 최대 힙에서 최대 원소, 최소 힙에서 최소 원소에 대한 접근은 O(1)에 수행된다. 원소의 삽입은 상향식 재구성(Bottom..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ std::queue STL에서 제공하는 큐 컨테이너 어댑터이다. 기본적으로 std::deque가 컨테이너로 사용된다. 선입선출(FIFO) 구조를 갖는다. 순회할 필요가 없으므로 반복자를 제공하지 않는다. Front와 Rear에서 원소에 접근할 수 있다. std::queue의 성능 모든 연산은 O(1) 시간에 수행된다. #include #include using namespace std; void main() { queue que; // 1, 2, 3 Push que.emplace(1); que.emplace(2); que.emplace(3); // Pop que.pop(); cout

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ std::stack STL에서 제공하는 스택 컨테이너 어댑터이다. 기본적으로 std::deque가 컨테이너로 사용된다. 후입선출(LIFO) 구조를 갖는다. 순회할 필요가 없으므로 반복자를 제공하지 않는다. Top 이외의 원소는 접근할 수 없다. std::stack의 성능 모든 연산은 O(1) 시간에 수행된다. #include #include using namespace std; void main() { stack stck; // 1, 2, 3 Push stck.emplace(1); stck.emplace(2); stck.emplace(3); // Pop stck.pop(); cout

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 일종의 래퍼이며, 기존 컨테이너의 인터페이스를 제한하여 만든 기능이 제한되거나 변형된 컨테이너이다. #include #include using namespace std; void main() { // 덱을 사용해 스택을 만들었다. deque stck1; stck1.emplace_back(1); stck1.emplace_back(2); stck1.pop_back(); // 스택에서는 지원하지 않는 기능이다. stck1.emplace_front(); // 스택 컨테이너 어댑터 stack stck2; stck2.emplace(1); stck2.emplace(2); stck2.pop(); // 컴파일 에러!! // stck2.emplace_front();..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ std::deque STL에서 제공하는 양방향 큐(Double-ended Queue) 컨테이너다. 크기가 같은 여러 개의 메모리 청크로 나누어 데이터를 저장하는 일종의 페이징 기법을 사용한다. std::vector와 달리 용량 부족으로 추가 메모리 할당 시 전체 원소를 이동시키지 않아도 된다. 내부적으로 첫 번째 청크가 아닌 중간 위치의 청크부터 원소를 저장하여 메모리 재할당을 최소화하는 등의 최적화 기법이 적용되어 있다. size()는 제공하나 capacity()는 구현 방법에 의존적이므로 제공하지 않는다. C++ 표준에서 규정하는 std::deque의 구현 조건 push_front(), pop_front(), push_back(), pop_ba..