거북이의 IT 공부

STL이란? 표준 C++ 라이브러리(Standard Template Library)로 프로그램에 필요한 자료구조와 알고리즘을 Template으로 제공하는 라이브러리 C++은 template라는 걸 통해서 한 가지 타입에 특정되지 않고, 여러 타입에 일반적인 문법을 사용할 수 있게 된 데다 STL을 통해서 타입 / 컨테이너 / 알고리즘을 분리해 하나씩만 구현해도 여러 조합의 경우를 포괄할 수 있는 언어가 되었다. STL = 컨테이너 + 반복자 + 알고리즘 컨테이너(Container) 특정한 타입의 원소들을 담아 다루기 위한 객체 Vector - 동적 배열이므로 배열의 크기를 변경할 수 있다. - 임의 접근이 가능하며, 뒤에서의 삽입이 빠르다. - 삽입, 삭제, 탐색 O(n), 임의 원소 접근 O(1) 보장..

우선순위 큐란? 기존 큐는 넣은 순서대로 빠지는 반면, 우선순위 큐는 넣는 것은 동일하지만 빠지는 건 최소 또는 최대부터 빠진다. 여기서 최대부터 빠지는 걸 Max Heap이라 칭하고, 최소부터 빠지는 걸 Min Heap이라고 칭한다. 우선순위 큐의 작동원리 Max Heap과 Min Heap은 자료구조 시간에 배운 기억이 난다. 다음 그림을 보면 더 생각이 잘 날것이다. 우선순위 큐는 자료구조 상 배열, 연결리스트, 힙으로 구현이 가능하다.(따라서 백터와 덱 컨테이너와 붙어서 사용이 가능하다 - 리스트 불가능) 내부적으로 에 있는 힙 관련 함수들을 사용하여 구현되어있다. 내부구조는 default로 vector container 기반으로 설정되어 있다. 정렬기준 default는 내림차순(less) 기반으로..

스택(stack) #include stack 변수이름; stack의 기본 함수 참고)) https://twpower.github.io/75-how-to-use-stack-in-cpp 추가 및 삭제 push(element) : top에 원소를 추가 pop() : top에 있는 원소를 삭제 - C언어는 맨 위에 원소를 반환하고 삭제하는 것이지만 C++은 그냥 삭제 emplace() - 데이터를 top에 삽입 조회 top() : top(스택의 처음이 아닌 가장 끝)에 있는 원소를 반환 기타 empty() : 스택이 비어있으면 true 아니면 false를 반환 size() : 스택 사이즈를 반환 큐(queue) #include queue 변수이름; queue의 기본 함수 참고)) https://twpower.g..

본 글은 씹어먹는 C++(https://modoocode.com/223)를 참고하여 여기서 내가 모르고 새로운 부분을 정리하는 용도로 작성했다. 나중에 c++ 문제 풀 때 또 모르면 참고하려고!!! 반복자 : 반복자는 컨테이너에 iterator 멤버 타입으로 정의되어 있습니다. begin() 함수는 예상했던 대로, vector 의 첫번째 원소를 가리키는 반복자를 리턴합니다. 그런데, 흥미롭게도 end() 의 경우 vector 의 마지막 원소 한 칸 뒤를 가리키는 반복자를 리턴하게 됩니다. 이에 여러가지 이유가 있겠지만, 가장 중요한 점이 이를 통해 빈 벡터를 표현할 수 있다는 점입니다. 만일 begin() == end() 라면 원소가 없는 벡터를 의미하겠지요. 만약에 vec.end() 가 마지막 원소를 ..