우주수첩의 우주먼지

Vector 일반적인 dynamic array와 비슷하게 사용 가능하다. push_back : 맨 마지막 위치에 원소를 삽입 pop_back : 맨 마지막 위치의 원소를 삭제 위의 두 연산을 평균 O(1)시간에 수행 가능. insert : 원하는 위치에 element를 삽입 O(n)시간 소모. #include // 헤더파일 스윽 써주께에 vector v; v.push_back(3); // v : [3] v.push_back(2); // v : [3, 2] v.push_back(5); // v : [3, 2, 5] vector a(8) // size : 8, initial value == 0 vector b(8,2) // size : 8, initial value == 2 # Vector 에 있는 모든 원..

이전에 sorting 알고리즘 몇 가지를 직접 C++로 구현 해 보았는데 사실 다 부질없고 라이브러리 함수가 모두 존재한다. 하지만 기억 저 편 하드디스크에서 아직 디스패치 되지 않는 나의 데이터들을 적재하기위해 잠시 IO인터프리터가 되어 주었던 것으로 하겠다. 망할 운영체제. 여튼 헤더에 을 include 하면 우리가 원하는 정렬을 사용할 수 있다. #sort(a,b) sort 함수를 사용하기 위해서는 정렬할 각 원소들이 비교가능해야한다. 숫자는 크기순, 문자는 사전순, pair 나 tuple의 경우 처음 요소가 작은 순서대로 비교 연산자가 정의되어있다. 몇가지 예시를 들어주도록 하겠다. # vector 정렬 #include // 헤더파일 언급 한 번 해 드리께 vector v = {4,2,5,3,5,..

Insertion Sort 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 매 순서마다 해당 원소를 삽입할 수 있는 적절한 위치를 찾아 해당 위치에 삽입한다. 삽입정렬은 두 번째 자료부터 시작하여 해당 위치 기준 왼쪽의 자료들과 비교하여 삽입할 위치를 지정한다. 이는 기준점의 왼쪽의 자료들은 모두 sorted상태임을 알 수 있다. 처음 key 값은 두번째 자료부터 시작한다. #include #include using namespace std; int main(void) { int arr[10] = { 4,5,6,2,3,10,8,1,9,7 }; int j; for (int i = 1; i < 10; i++) { int ..

Selection Sort 제자리 정렬 알고리즘 중 하나. 정렬되지 않은 입력 배열 외에 다른 추가 메모리를 요구하지 않는다. 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘. 첫번째 자료를 두번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓는 행위를 반복하며 정렬을 수행한다. 1회전을 하고 나면 가장 작은 값의 자료가 맨 앞에 위치. 다음 회전에는 두번째 위치의 배열부터 처리한다. 정렬 과정 주어진 배열에서 최소값을 찾는다. 현재 범위 내에서 맨 앞의 값과 교환한다. 교환한 위치를 제외한 나머지 배열을 같은 방법으로 교체한다. 하나의 원소만 남을 때 까지 반복한다. #include #include using namespace s..

BUBBLE SORT 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 => 인접한 두 개의 원소를 비교하여 순서대로 되어있지 않을 경우 서로 교환한다. => array[3] 제외되는 데이터가 하나씩 늘어난다. #include #include using namespace std; int main(void) { int arr[10] = { 4,5,6,2,3,10,8,1,9,7 }; int temp; for (int i = 0; i arr[j + 1]) { temp = arr[j + 1]; arr[j ..

https://cses.fi/problemset/task/1675/ CSES - Road Reparation cses.fi 망할 알고리즘 응용 덕분에 크루스칼 제대로 머리에 기억 남을 듯 하다. 물론 얼마나 갈지는 모르겠지만. #include #include #include using namespace std; vector Edge; class UFDS { private: vector p, rank, setSizes; int numSets; public: UFDS(int N) { numSets = N; rank.assign(N, 0); p.assign(N, 0); for (int i = 0; i < N; i++) p[i] = i; setSizes.assign(N, 1); } int findSet(int ..

최소 스패닝 트리(MST)를 만들기 위한 방법 중 하나. (+ 프림알고리즘) 1. 모든 간선들의 가중치를 오름차순으로 정렬한다. 2. 가중치가 가장 작은 간선을 선택한다. 3. 선택한 간선이 연결하려는 2개의 노드가 아직 서로 연결되지 않은 상태라면 2개의 노드를 서로 연결한다. 4. 반복. => 최소가중치를 가진 간선들을 사이클이 발생하지 않게 계속 연결하여 MST를 찾는다. 시간 복잡도 : O(mlog n) 구현 가장 작은 가중치를 갖는 간선이 연결하고자 하는 두 노드가 연결되어있는지 확인해주는 과정에서 많이 사용하는 방식이 Union-Find이다. 이전에 Union_Find를 다룬 적이 있는데 이를 이렇게 적용할 줄이야 하하핳. parent[] 코드 구현시에 대중적으로 많이 사용하는 방법은 pare..

Pair : 두 객체를 하나의 객체로 취급할 수 있게 묶어주는 클래스 STL에서 데이터 쌍을 표현할 때 사용 utility 헤더에 존대 template struct pair; template struct pair; pair=,

구현 코드 ) #include #include #include using namespace std; #define maxn (int)(le9)+1 int t, n, x, ans, cnt, block; map lastseen; int main() { cin >> t; // 테스트 케이스 개수 입력 while (t--) { cin >> n; // 정수 리스트의 길이 입력 lastseen.clear(); //테스트 케이스가 1개 이상 입력 될 경우 map을 초기화 하여 입력을 받아온다. ans = 0, cnt = 0, block = 0; for (int i = 1; i > x; int lx = lastseen[x]; if (lx != 0) { block = max(block, lx); cnt = i - blo..

??? 내가 auto를 찾아보게 된 경로가 무엇인가? C++을 사용하여 set을 구현하는 도중 set의 모든 element에 접근하여 이들을 출력하는 for문을 확인하였다. cout 초기화 값에 따라 알아서 데이터 타입을 정해주는 키워드 라고 불린다. => 선언한 변수나 람다 식의 타입을 컴파일러에게 추론하도록 맡긴다. ex) auto a1 = 10; // int 타입 auto a2 = 10.0f; // float 타입 auto a3 = "c"; // char 타입 auto a4 = "BlockDMask"; // string 타입 auto a5 = {10, 20, 30}; //int 배열 타입 단순한 자료형 뿐만 아니라 iterator를 선언하는 데에서도 적용 할 수 있다. #include #includ..