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하면 사용할 수 있다.주요 메서드주요 메서드를..

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..

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) ..

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..

C++ #include //merge sort using namespace std; int arr[1000000]; void sort(int arr1[], const int first, const int last); void merge(int arr1[], const int first, const int mid, const int last); int main(void){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; for (int i{ 0 }; i > arr[i]; sort(arr, 0, n -1 ); for (int i{ 0 }; i < n; i++) printf("%d\n", arr[i]); retur..

C++ #include //merge sort using namespace std; void sort(int arr[], const int first, const int last); void merge(int arr[], const int first, const int mid, const int last); int main(void){ int arr[1000]; int n; int k; cin >> n >> k; for (int i{ 0 }; i > arr[i]; } sort(arr, 0, n - 1); cout

C++ #include //bubble_sort using namespace std; void bubble_sort(int nums[], const int& SIZE); void printNums(int nums[], const int& SIZE); void swap(int* p1, int* p2); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; int inputNumber; int nums[1000]; cin >> n; //n번째까지 입력을 받습니다. for (int i{ 0 }; i > nums[i]; } //정렬합니다. bubble_sort(nums, n); //출력합니다. printNums(n..

C++ 이 문제는 시간복잡도 때문에 여타의 소수 구하는 알고리즘과 다르게 풀어야한다. 이 문제는 '에라토스테네스의 채' 라는 알고리즘으로 해결 해야하고 해당 알고리즘 내용은 아래 위키백과에 잘 나와 있으니 한 번씩 보고 오도록 하자. https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾는 빠르고 쉬운 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] ko.wikipedia.org 전체 ..

C++ #include using namespace std; int main(void) { unsigned int size; cin >> size; unsigned int temp; cin >> temp; /* N의 값은 합성수(약수의 개수가 3 이상)이며, N의 약수 1과 N을 제외한 약수들 중에서 가장 작은 값과 큰 값을 곱하면 N을 구할 수 있게 된다. */ unsigned int min = temp, max = temp; for (int i{ 1 }; i > temp; min = (min > temp) ? temp : min; max = (max < temp) ? temp : max; } cout