출처https://www.codetree.ai/missions/8/problems/section-with-maximum-overlap/introduction들어가면서코드트리 문제를 풀다보면 수직선 상 특정 한 점에서 겹치는 서로 다른 선분의 개수를 구하는 문제를 만나게 된다. 단순하게 for문으로 해결한다면 시간초과가 발생하므로 코드트리에서 설명하는 '+1-1 Technique' 알고리즘을 사용해야만 한다.+1-1 Technique 알고리즘이란?모든 선분에 대한 시작점과 끝점에 가중치 +1과 -1을 각각 부여함으로써 x의 값이 증가하는 순서대로 정렬하는 방법을 의미한다. 각각의 가중치는 1차원 배열에 저장함으로써 특정 한 점에서 겹치는 선분의 개수를 구할 수 있게 된다.가장 많이 겹치는 구간 | C++#..
C++
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) 시간으로 ..
들어가면서Swift 언어의 주석 처리 방법은 C++나 Java에서 사용하는 한 줄 주석 처리(//)와 여러 줄 주석 처리(/* */) 방법을 모두 사용할 수가 있다.다만, Swift에서 한 가지 다른 점이 있는데 이번 글에서 살펴보도록 하자.주석 방법 1 | 한 줄 주석은 //를 사용한다.C++와 Java의 한 줄 주석 처리 방법과 모두 동일하다.주석 방법 2 | 여러 줄 주석은 /* */를 사용한다.C++와 Java의 여러 줄 주석 처리 방법과 모두 동일하다.주석 방법 3 | C++, Java와 다르게 Swift는 중첩 주석을 사용할 수 있다.중첩 주석이란 여러 줄 주석 안에 또 다른 여러 줄 주석을 중첩하여 사용할 수 있는 것을 말한다.C++나 Java에서는 중첩 주석을 사용할 수 없는데, 아래 C+..
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 ..
들어가면서이번 글은 아래 글의 후속편이다. this 포인터에 대해 잘 모르겠으면 아래 글을 보고 다시 오자! https://logicallaw.tistory.com/entry/C-클래스-내부의-this-포인터의-역할 C++ : 클래스 내부의 this 포인터의 역할(this->멤버, (*this).멤버)this 포인터 클래스 내부에서 this 포인터는 모든 멤버함수의 default 매개변수이다. (자세히 말하면, friend 함수를 제외하고 모든 멤버함수에 존재한다.) 즉, 모든 멤버함수(또는 생성자)에서 this 포logicallaw.tistory.comCascaded Function Calls이란?Cascaded Function Calls는 멤버함수 체이닝 또는 연쇄호출이라고 불리기도 한다.(이하 멤버..
