출처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/코드트리
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) 시간으로 ..
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이란 ..
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..
