Brute force Study

[C++ STL] std::tuple

std::tuple이란?기존에 다른 데이터 타입의 값 2개를 저장하기 위해 pair를 사용했지만, first와 second 두 개의 요소만 관리할 수 있었다.C++11부터 STL에서 tuple을 제공하여 다수의 요소를 관리할 수 있는 tuple을 제공한다.에 정의되어 있다. 기본 사용법#include #include int main() { // 다양한 타입의 요소들을 포함하는 튜플 생성 std::tuple myTuple(1, 3.14, "Hello"); // 튜플의 요소에 접근 std::cout (myTuple) (myTuple) (myTuple)  별 특이한 점은 없지만, std::get을 사용할 수 있다. std::getstd::get 템플릿 함수를 이용해서 튜플의 요소에 접근할..

[C++ STL] std::string

std::string이란?STL에서 제공하는 문자열 처리 클래스동적 길이 문자열을 다루기 쉽게 만들어준다.에 정의되어 있다. 내부 구현?문자열의 크기에 따라 동적으로 할당하여 문자열 데이터를 저장한다짧은 문자열은 내부 버퍼에 따로 저장하여 동적 할당을 하지 않는다복사 및 연산 과정에서 기본적으로 깊은 복사를 사용한다. 포인터나 참조가 기반으로 관리되지 않는다초기화기본 생성자 : 빈 문자열 생성std::string s; C-스타일 문자열로부터 생성std::string s1("Hello");std::string s2 = "Hello";std::string s3 = ""; 반복자로부터 생성std::string s(iter1, iter2); 특정 문자 n개로 초기화std::string s(5, 's');// "..

[C++ STL] std::pair

std::pair란?두 개의 이질적인 데이터 타입의 값을 하나로 묶어서 저장하는데 사용되는 템플릿 클래스두 개의 값을 리턴해야 해야 하거나, 두 개의 값을 key와 value로 사용하는데 유용하다에 정의되어 있다. std::pair의 구현 방식실제 구현 코드는 아니지만, 이러한 방식으로 구현되어 있다template struct pair { T1 first; T2 second; // 기본 생성자 pair() : first(T1()), second(T2()) {} // 사용자 정의 생성자 pair(const T1& a, const T2& b) : first(a), second(b) {} // 복사 생성자 template pair(const pair& p) :..

C++ 해시 테이블해시 구현에서 항상 양의 정수만 취급할 수는 없다.오히려 문자열 데이터를 다루게 되는 경우가 더 많다영어 사전을 구현하려면 영어 단어를 키로 사용하고, 뜻을 값으로 사용해야 한다모듈로 함수는 문자열에는 적용할 수 없다간단한 해결책은 문자열의 모든 문자에 대한 ASCII 코드 값을 모두 더한 후에 모듈로 연산을 하는 것이다.위 방법은 충돌이 빈번하게 발생할 수 있다C++은 문자열로부터 해시 값을 생성하는 용도로 std::hash>(std::string) 함수 객체를 제공한다이 함수 객체 내부에는 해시 함수 알고리즘이 구현되어 있다.C++은 문자열 이외에도 모든 기본 데이터 타입에 대한 해시 값을 생성하는 기능도 제공한다"체이닝을 사용하는 해시 테이블"에서 구현했던 해시 테이블 코드를 템플..

그래프(graph)트리는 원형 또는 순환적인 종속성을 표현할 수 없다.하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에도로망을 생각해보자. 특정 노드에서 다른 노드로 이동하기 위한 다양한 경로가 존재할 수 있다.이러한 경우에는 그래프(graph) 구조를 사용해야 한다그래프 구분 - weight그래프는 노드 데이터뿐만 아니라 노드 사이의 에지 데이터도 저장해야 한다.도로망을 예로 들면 각각의 노드에 다른 어떤 노드들이 연결되어 있는지에 대한 정보를 가지고 있어야 한다.이런 방법으로 필요한 모든 노드와 에지가 있는 그래프를 만들 수 있다.이러한 그래프를 비가중 그래프(unweighted graph)라고 한다.에지에 가중치 또는 더 많은 정보를 부여할 수 있다.도로망에서 에지에 노드와 노드 ..

힙(heap)std::priority_queue에서 다룬 heap에 대해 더 깊이 있게 알아보자힙은 앞서 말했던 것처럼 다음과 같은 시간 복잡도를 만족해야 한다O(1) : 최대 원소에 즉각적으로 접근할 수 있어야 한다.O(log N) : 원소 삽입에 대한 시간 복잡도O(log N) : 최대 원소 삭제에 대한 시간 복잡도원소 삽입 또는 삭제에 대해 O(log N)의 시간 복잡도를 만족하기 위해 트리 구조를 사용해야 한다.특히 이 경우 완전 이진 트리를 사용해야 한다.완전 이진 트리는 트리의 데이터를 배열을 이용하여 저장할 수 있다.루트 노드를 배열 또는 벡터의 맨 처음에 저장하고, 그다음 레벨의 모든 노드는 왼쪽부터 오른쪽 순서로 저장한다포인터를 사용하지 않아서 메모리 사용 측면에서 효율적이다.부모 노드로..

컨테이너 어뎁터(container adaptor)이미 존재하는 컨테이너를 기반으로 만들어진 컨테이너에 대해 알아본다각 자료구조에 대한 기본적인 내용은 이미 알고있다고 가정하고 글을 작성합니다!래퍼를 제공하는 이유코드에 의미를 부여의도하지 않는 함수를 실수로 사용하지 못하도록 제한특별한 인터페이스를 새롭게 제공std::stackLIFO 구조를 사용하기 때문에 스택은 컨테이너의 한쪽 끝에서만 데이터를 삽입/삭제한다벡터나 덱은 이러한 기능을 기본적으로 지원하기 때문에 스택을 구현하기 위한 용도로 사용할 수 있다push_front()로 맨 앞 원소에 접근할 수 있기 때문에 벡터나 덱을 직접 사용하기에는 문제가 있다이와 달리 std::stack을 사용하여 작성된 소스 코드는 어떤 작업을 하고 있는지 직관적으로 알..

std::deque배열 기반 컨테이너와 리스트 기반 컨테이너 두 가지 방식이 섞여있는 형태각각의 장점을 적당히 가지고 있다vector에서 push_front(), pop_front() 에서 비용이 많이 드는 단점을 극복할 수 있다deque : 양방향 큐(double-ended-queue)의 약자덱의 구조C++ 표준은 덱의 동작에 있어 다음 조건을 만족해야 한다고 규정한다.push_front(), pop_front(), push_back(), pop_back() 동작이 O(1) 시간 복잡도로 동작해야 함모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작해야 함덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동작해야 하며, 실제로는 최대 n / 2 단계로 동작하며 여기서 n은 덱의 크..

std::list복습std::forward_list는 기본적인 형태로 구현된 연결 리스트임리스트 끝에 원소 추가, 역방향 이동, 리스트 크기 반환 등의 기능을 제공하지 않음빠른 원소 삽입이 필요한 모든 경우에 어울리는 container는 아니다.std::forward의 단점을 보완하기 위해 c++에서 std::list를 제공한다std::list양쪽 방향으로 연결된 리스트, 즉 이중 연결 리스트(doubly-linked-list) 구조로 되어 있다.따라서 더 많은 기능을 제공한다. (메모리는 조금 더 많이 사용한다)// 이중 연결 리스트 노드 기본 형태struct doubly_linked_list_node{ int data; doubly_linked_list_node* next; doubl..

Iterator(반복자)반복자는 포인터와 비슷하지만, STL container에 대한 공통의 interface를 제공한다.반복자를 이용한 연산은 어떤 컨테이너에서 정의된 반복자인지에 따라 결정된다.배열과 벡터의 경우 연속된 자료 구조를 사용하기 때문에 지정 위치의 원소에 바로 접근할 수 있다.이러한 반복자를 임의 접근 반복자(random access iterator)라고 한다.std::foward_list의 경우 역방향 이동을 제공하지 않으며, 이전 노드로 이동하려면 처음부터 다시 찾아가야 한다.증가 연산만 가능하며, 이러한 반복자를 순방향 반복자(foward iterator) 라고 한다.반복자 타입에 따라 사용할 수 있는 함수advance()반복자와 거리 값을 인자로 받고, 반복자를 거리 값 만큼 증가..