우주수첩의 우주먼지

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

사이즈가 n인 array A가 있다. 해당 array의 inversion의 개수를 출력하는 프로그램을 작성하여라. #그냥 구현하기 #include #include using namespace std; int main(void) { int arr[10] = { 4,5,6,2,3,10,8,1,9,7 }; int inversion_count = 0; for (int i = 0; i arr[j]) inversion_count++; } } cout arr[j + 1]) { temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; inversion_count++; } } }..

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

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

구현 코드 ) #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..