[C++] STL queue
C++ STL의 queue는 먼저 들어온 원소가 가장 먼저 나가는 FIFO(First In, First Out) 구조를 구현한 컨테이너 어댑터(container adapter) 이다. 기본 컨테이너는 deque이며, queue 자체가 컨테이너는 아니다. 주요 멤버 함수 함수명 설명 push(val) 맨 뒤에 원소 삽입 pop() 맨 앞 원소 제거 front() 맨 앞 원소 반환 back() 맨 뒤 원소...
C++ STL의 queue는 먼저 들어온 원소가 가장 먼저 나가는 FIFO(First In, First Out) 구조를 구현한 컨테이너 어댑터(container adapter) 이다. 기본 컨테이너는 deque이며, queue 자체가 컨테이너는 아니다. 주요 멤버 함수 함수명 설명 push(val) 맨 뒤에 원소 삽입 pop() 맨 앞 원소 제거 front() 맨 앞 원소 반환 back() 맨 뒤 원소...
C++ STL의 stack은 나중에 들어온 원소가 가장 먼저 나가는 LIFO(Last In, First Out) 구조를 구현한 컨테이너 어댑터(container adapter) 이다. stack 자체는 컨테이너가 아니며, vector, list, deque와 같은 실제 컨테이너 위에서 stack처럼 동작하도록 만든 인터페이스라고 생각하면 된다. stack[2]와 같은 임의 접근은 불가능하며, 오직 맨 위(top) 원소를 통해서만 접근이 가능하다. 주요 멤버...
동적 계획법(Dynamic Programming)은 코딩 테스트를 준비하는 사람이라면 반드시 알고 있어야 할 알고리즘 기법이다. 더 작은 size의 문제를 푼다. 푼 문제의 해답을 저장해두고, 필요할 때마다 가져다 쓴다. 이를 이용해 더 큰 문제의 해답을 도출한다. DP 로 줄여서 부르며, 1차원 배열, 딕셔너리, 트리 등 다양한 형태를 이용하여 기록하지만 가장 많이 쓰는 형태는...
C++ STL의 unordered_set은 중복되지 않는 원소들을 저장하는 해시 기반 컨테이너이다. 다만, 이름 그대로 순서를 보장하지는 않는다. 주요 특징 중복된 원소는 저장되지 않는다. 예를 들어, 같은 값을 두 번 넣으려고 하면 두 번째 삽입은 무시된다. 순서가 없다. 즉, 컨테이너의 원소들은 정렬되지 않는다. 내부적으로 해시 테이블을 사용해 평균 O(1) 시간에 삽입, 삭제,...
C++ STL의 set은 중복되지 않는 원소들을 정렬된 상태로 저장하는 자료구조이다. 주요 특징 중복된 원소는 저장되지 않는다. 예를 들어, 같은 값을 두 번 넣으려고 하면 두 번째 삽입은 무시된다. 원소들은 자동으로 오름차순 정렬된다. (기본 비교 함수: std::less) 내부는 Red-Black Tree로 구현되어 있다. 삽입, 삭제, 탐색 모두 평균 O(logn) 인덱스 접근이 불가능하며...