컨테이너 어댑터(container adaptor) 기존의 컨테이너를 변형하여 꼭 필요한 인터페이스만을 제공하여 만든 컨테이너로, C++에서 제공하는 컨테이너 어댑터는 std::stack, std::queue, std::priority_queue가 있다. std::stack std::stack은 std::deque을 기본 컨테이너로 사용한다. 데이터 처리와 보관을 위해 LIFO(Last In First Out, 후입선출) 구조를 사용하고 한쪽 끝에서만 데이터의 삽입과 삭제가 이루어진다. 벡터와 덱에서 이러한 기능을 기본적으로 지원하지만, 직접 스택처럼 사용하기에는 기능이 너무 많다. 그래서 의도하지 않은 동작과 코드를 잘못 작성하는 경우를 방지하기 위해 스택에 꼭 필요한 인터페이스만을 제공한다. 아래 코드..
std::deque 벡터는 가변 길이 배열이고, push_front() 또는 pop_front() 같은 함수는 비용이 많이 든다. (다 하나씩 밀어줘야 함) std::deque를 통해 이런 단점을 극복할 수 있다. (double-ended queue) 덱(deque)의 구조 - push_front(), pop_front(), push_back(), pop_back() 동작이 O(1) 시간 복잡도로 동작해야 한다. - 모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작해야 한다. - 덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동작해야 하며, 실제로는 최대 n/2 단계로 동작한다. (n: 덱의 크기) - 덱은 자료구조가 벡터와 비슷하지만 앞쪽과 뒤쪽으로 보두 확장할 수 있다. -..
std::list std::forward_list는 아주 기본적인 형태로 구현된 연결 리스트이다. 리스트 끝에 원소 추가, 역방향 이동, 리스트 크리 반환 등의 기능은 제공하지 않는다. (메모리와 성능 유지를 위해) forward_list는 반복자의 기능도 적다. 이러한 forward_list의 단점을 보완하기 위해 C++ 은 std::list를 제공한다. std::list는 양쪽 방향으로 연결된 이중 연결 리스트(doubly-linked list) 구조로 되어 있어 더 많은 기능을 제공하지만 메모리는 조금 더 사용한다. struct doubly_linked_list_node{ int data; doubly_linked_list_node* next; doubly_linked_list_node* prev;..
std::forward_list 배열, 벡터 같은 연속된 자료 구조에서는 데이터 중간에 자료를 추가하거나 삭제하는 작업이 매우 비효율적이다. std::forward_list는 C++에서 제공하는 기본적인 연결 리스트에 대한 래퍼 클래스이다. 원소의 삽입, 삭제, 순서 뒤집기, 분할 등의 기능은 제공하지만 성능 유지를 위해 전체 리스트의 크기를 반환하거나 첫 번째 원소를 제외한 나머지 원소에 접근하는 기능은 제공하지 않는다. vector와 마찬가지로 사용자 지정 할당자를 지정하여 메모리 관리를 더욱 효율적으로 수행할 수 있다. 원소 삽입 원소 삽입은 노드 포인터 조작으로 구현되므로 삽입 후 다른 원소를 이동할 필요가 없다. 그렇기 때문에 배열 기반 구조에서의 삽입 함수에 비해 매우 빠르게 동작한다. 리스트..
std::array의 주요 단점 - array의 크기는 컴파일 시간에 결정되는 상수여야 한다. 프로그램 실행 중에는 변경할 수 없다. - 크기가 고정되어 있어서 원소를 추가하거나 삭제할 수 없다. - array의 메모리 할당 방법을 변경할 수 없다. 항상 스택 메모리를 사용한다. -> 가변 크기의 데이터를 처리할 수 있는 컨테이너가 필요하다. std::vector std::vector는 가변 크기 배열로, 초기화 과정에 데이터의 크기를 제공하지 않아도 된다. 벡터의 초기화는 아래 코드처럼 여러 방법이 존재한다. std::vector vec; // 크기 0인 벡터 std::vector vec = {1, 2, 3, 4, 5}; // 지정한 초기값으로 이루어진 크기가 5인 벡터 std::vector vec(1..
C 스타일 배열의 단점 - 메모리 할당과 해제를 수동으로 처리해야 한다. memory leak이 발생할 수 있다. - [] 연산자에서 배열 크기보다 큰 원소를 참조하는 것을 검사하지 못한다.(segmentation fault) - 배열을 중첩하여 사용할 경우, 문법이 너무 복잡하여 코드의 가독성이 떨어진다. - 깊은 복사(deep copy)가 기본으로 동작하지 않는다. 수동으로 구현해야 한다. 이와 같은 문제점을 회피할 수 있도록 C++에서는 std::array를 제공한다. std::array - std::array는 메모리를 자동으로 할당하고 해제한다. - 원소의 타입과 배열 크기를 매개변수로 사용하는 클래스 템플릿이다. std::array 의 형식으로 선언할 수 있다. #include #include..
선형 자료 구조는 크게 연속된 구조와 연결된 구조로 분류할 수 있다. 연속된 구조 (contiguous data structure) 모든 원소를 단일 메모리 청크에 저장하는 것 data[0] data[1] data[2] data[3] Base Address BA + sizeof(type) BA + 2 * sizeof(type) BA + 3 * sizeof(type) 위 그림처럼 단일 메모리 청크 내에 각각의 원소가 저장된 메모리 공간이 존재한다. 각 원소에 접근할 때에는 BA + i * sizeof(type)을 이용하여 O(1)로 데이터에 접근할 수 있다. 배열은 정적 배열(static array)와 동적 배열(dynamic array)로 나눌 수 있다. 1. 정적 배열 - 선언된 블록이 끝나면 소멸된다..
문제 링크: https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 풀이 및 코드 #include using namespace std; int dp[100][12]; int main(..
