출처https://www.codetree.ai/missions/8/problems/section-with-maximum-overlap/introduction들어가면서코드트리 문제를 풀다보면 수직선 상 특정 한 점에서 겹치는 서로 다른 선분의 개수를 구하는 문제를 만나게 된다. 단순하게 for문으로 해결한다면 시간초과가 발생하므로 코드트리에서 설명하는 '+1-1 Technique' 알고리즘을 사용해야만 한다.+1-1 Technique 알고리즘이란?모든 선분에 대한 시작점과 끝점에 가중치 +1과 -1을 각각 부여함으로써 x의 값이 증가하는 순서대로 정렬하는 방법을 의미한다. 각각의 가중치는 1차원 배열에 저장함으로써 특정 한 점에서 겹치는 선분의 개수를 구할 수 있게 된다.가장 많이 겹치는 구간 | C++#..
PS
map 란?AVL 트리의 자료구조로 구현된 C++ STL을 의미한다. 먼저, AVL 트리(균형잡힌 이진탐색트리)란 balanced Binary Search Tree를 만족하면서 Height-balance property를 만족하는 자료구조를 의미한다. 이때, Height-balance property란 임의의 노드 v에 대하여 v의 두 자식의 height 차이가 많아야 1인 property를 말한다. 따라서, AVL 트리는 항상 트리의 높이가 점근적으로 O(logN)에 바운드가 되므로, 이 자료구조의 삽입, 삭제, 탐색 등 모든 연산의 시간 복잡도는 O(logN)을 보장한다. map의 include 방법#include 다음과 같이 map의 헤더를 include하면 사용할 수 있다.주요 메서드주요 메서드를..
priority_queue 란?최대힙으로 우선순위 큐를 구현한 C++ STL를 의미한다. 먼저, 우선순위 큐란 우선순위가 가장 높은 데이터가 먼저 나가는 자료구조를 의미한다.우선순위 큐는 Key와 Value의 쌍으로 구성된 entry를 원소로 저장하는데 이때, Key는 우선순위를 결정하는 변수가 된다.(참고로 본 게시글에서는 Key만 다룰 예정이다.) 우선순위 큐는 대표적으로 unsorted-sequence, sorted-sequence, heap 등의 방식으로 구현되는데 C++ STL에서는 최대힙(max-heap) 방식으로 구현되어 있다. 따라서, priority_queue는 삽입과 삭제의 연산이 O(logN) 시간으로 수행할 수 있고, N개의 원소에 대한 오름차순으로 정렬시 O(NlogN) 시간으로 ..
C++#include #include #include #include using namespace std;int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector keys; unordered_map map; //O(n) time while(n--) { int x; cin >> x; if(map.find(x) == map.end()) { map.insert({x, 1}); keys.push_back(x); } else { map[x] += 1; ..
sort(first, last, comp) 함수란?C++ STL의 algorithm 헤더에 정의된 정렬 함수를 의미한다. sort 함수는 여러 가지 배열 또는 컨테이너의 시작(first)과 끝(last-1)의 범위를 지정하여 사용자가 원하는 정렬 기준(comp)에 따라 O(nlogn) time으로 정렬하는 함수를 말한다. 기본적으로, comp는 사용자 정의의 비교 함수를 의미하며 비교 함수를 생략한다면 기본적으로 오름차순으로 정렬되게 된다.또한, 배열의 범위를 지정할 때 주의할 점은 인자로 first와 last를 넘겨주면, 실제로는 first부터 last-1까지만 정렬되게 된다. 정렬할 배열로는 내장 배열과 모든 컨테이너(ex:vector, list)가 가능하다. sort 함수의 include 방법#i..
unordered_set 란?정렬되지 않은 HashSet의 자료구조로 구현된 C++ STL을 의미한다. 먼저, HashSet이란 Hashing을 기반으로 데이터를 관리해주는 자료구조를 의미한다.따라서, 삽입, 삭제, 탐색 등 모든 함수의 시간 복잡도가 O(1) time 이다. https://logicallaw.tistory.com/entry/%EC%BD%94%EB%93%9C%ED%8A%B8%EB%A6%AC-unorderedmapK-V%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-C-STL 사용 방법 | C++ STL" data-og-description="unordered_map이란?정렬되지 않은 HashMap의 자료구조로 구현된 C++ STL를 의미한다. 먼저, HashMap이란 ..
1157번 | 단어 공부#include #include #include using namespace std;int main(void) { string userInput; cin >> userInput; unordered_map map; vector mapKeys; for(int i{ 0 }; i = 'A' && c max) { max = value; maxCnt = 1; result = mapKeys[i]; } else if (value == max) { maxCnt++; } } if(maxCnt > 1) ..
unordered_map이란?정렬되지 않은 HashMap의 자료구조로 구현된 C++ STL를 의미한다. 먼저, HashMap이란 Dictionary를 구현하는 방법의 일부로, pair로 구성된 entry를 원소로 저장하는 컨테이너를 의미한다.HashMap의 구현 방법은 Chaining 방식, Linear Probing 방식, Double Hasing 방식 등 여러 가지 방법이 존재하는데, unordered_map의 STL은 정렬되지 않은 HashMap으로 구현되어 있다. 이 STL의 특징은 entry의 삽입, 삭제, 탐색 등의 연산에서 O(1) time(상수 시간)으로 수행할 수가 있다.즉, 특정 entry를 접근할 때 모두 상수 시간에 수행할 수 있으므로, 이 STL을 사용하게 되면 built-in ..
C++Solution부호가 동일한 숫자면 같은 숫자로 판단한다. 따라서, 이전에 입력된 숫자와 현재 숫자가 부호가 같은 숫자인지 확인하는 isSameNumber 함수를 통해 판단하고, 동일한 숫자면 카운트하여 최댓값을 저장하는 max와 비교하여 max를 업데이트를 진행한다.#include using namespace std;bool isSameNumber(const int& preN, const int& nextN) { if((preN > 0 && nextN > 0 )|| (preN > n; int* array = new int[n]; for(int i{ 0 }; i > array[i]; } int duplicated = 1; int max = 0; for(int i..
C++#include #include using namespace std;class Tree;class CharNode {private: CharNode* par; char ele; CharNode* leftC = NULL; CharNode* rightC = NULL; friend class Tree;};class Tree{private: CharNode* root; vector nodes;public: Tree() { root = new CharNode; root->par = NULL; root->ele = 'A'; nodes.push_back(root); } ~Tree() { for(i..
