우주수첩의 우주먼지

Map pair를 관리하기 위한 data structure set과 마찬가지로 c++에서는 red-black tree로 map library를 구현하기에 searching 과 update 모두 O(log n)시간 에 수행 가능하다. Map에서 각 key는 반드시 unique해야하며 C++에서는 중복된 key값을 허용하는 multimap library를 따로 지원한다. unordered_set과 마찬가지로 c++에서는 hash table로 구현 된 unordered_map library 또한 지원한다. # example map m; m["monkey"] =4; m["banana"] =3; cout

Set 집합을 관리하기 위한 data structure Set library는 중복을 허용하지 않는다. C++에서는 set library가 balanced binary search tree (== red-black tree)로 구현되어 있기 때문에 기본적인 searching과 update 모두 O(log n) 시간에 수행 가능하다. c++에서는 set의 element간에 순서가 정해지지 않은 경우 사용할 수 있는 unorderd_set_library를 지원한다. 이는 hash table로 구현되어 있으며 모든 연산을 average O(1)에 구현 가능하다 근데 이제 경진대회에서는 쓰지 않음을 곁들인... #include 헤더파일 include 진행 namespace 를 사용하면 더 효율적으로 사용 가능 ..

https://codeforces.com/problemset/problem/1092/B Problem - 1092B - Codeforces codeforces.com # JAVA import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { public static void main(String args[]) throws IOException{ BufferedReader br = new BufferedReader(n..

# Stack (FILO) push: 끝부분 (stack top)에 원소를 추가 pop : 끝부분의 원소를 제거 == Stack top의 원소 반환 모두 평균 O(1) stack s; s.push(2); // 2 s.push(5); // 2 5 cout

Deque 양 끝 부분에 원소를 추가, 삭제를 평균 O(1)시간에 할 수 있는 자료구조 push_back : 끝부분에 추가 pop_back : 끝부분 삭제 push_front : 처음 부분에 추가 pop_front : 처음부분 삭제 insert : 중간에 추가 O(n) Doubled linked list에 비해서 access가 빠르다는 장점이 있다. 근데 링크드 리스크 자체를 경진대회에서 거의 안쓴다는 왈ㄹ랄라가 있지. #include // 헤더 파일 스윽 써주께에 deque d; d.push_back(5); //5 d.push_back(2); //5 2 d.push_front(3); // 3 5 2 d.pop_back(); // 3 5 d.pop_front();// 5

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 에 있는 모든 원..

사이즈가 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 ..

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