다락방

알고리즘거품 정렬(Bubble Sort)서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다.과정1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를,,, 이런 식으로 (마지막-1) 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.시간복잡도O(n^2)정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^..

18870 좌표 압축 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector x1; vector x2; int n; cin >> n ; for (int i = 0; i > tmp; x1.push_back(tmp); x2.push_back(tmp); } sort(x1.begin(), x1.end()); x1.erase(unique(x1.begin(), x1.end()), x1.end()); for (int i = 0; i < n; ++i) { cout

25305 커트라인 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector num_arr; int n, k; cin >> n >> k; for (int i = 0; i > tmp; num_arr.push_back(tmp); } sort(num_arr.begin(), num_arr.end(),greater()); cout

2587 대표값2 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector num_arr(5); int sum = 0; for (int i = 0; i > tmp; sum += tmp; num_arr[i] = tmp; } sort(num_arr.begin(), num_arr.end()); cout

10814 나이순 정렬 #include using namespace std; bool compare(tuple a, tuple b) { if (get(a) == get(b)) return get(a) > n; for (int i = 0; i > x >> y; n_arr.push_back(make_tuple(x,y,i)); } sort(n_arr.begin(), n_arr.end(),comp..

11651 좌표 정렬하기2 #include using namespace std; bool compare(pair a, pair b) { if (a.second == b.second) return a.first > n; for (int i = 0; i > x >> y; n_arr.push_back({x, y}); } sort(n_arr.begin(), n_arr.end(),compare); fo..

1427 소트인사이드 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string n; vector n_arr; cin >> n; for (int i = 0; i < n.length(); ++i) { n_arr.push_back(n[i]-48); } sort(n_arr.begin(), n_arr.end(),greater()); for (auto i : n_arr) cout

Sort sort 알고리즘은 헤더파일에 속해있다. sort(start,end)를 이용해서 범위에 있는 인자 (element)를 오름차순으로 정렬해준다. quick sort(퀵 정렬)을 기반으로 함수가 구현되어있어, 평균 시간복잡도는 nlogn이다. sort(arr,arr+n); sort(v.begin(), v.end()) sort(v.begin(), v.end(), compare()); // 사용자 정의 함수 sort(v.begin(), v.end(), greater()); // 내림차순 sort(v.begin(), v.end(), less()); // 오름차순

위상정렬(Topological Sorting) 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘. 사이클이 없는 방향, 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것. 진입차수와 진출차수 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 동작과정 큐를 이용해 구현한다. 진입차수가 0 인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다 새롭게 진입차수가 0이 된 노드를 큐에 삽입한다. 위상정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프(DAG)이여야 한다. 위상정렬의 특징 위상정렬은 사..

정렬_Sorting Key를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업 오름차순 ascend_order - 값이 작은 데이터를 앞쪽에 배치 내림차순 descend_order - 값이 큰 데이터를 앞쪽에 배치 정렬 알고리즘의 안정성 정렬 알고리즘은 안정적인(stable), 안정적이지않은(unstable) 정렬로 나뉜다. 안정적인 정렬알고리즘은 값이 같은 원소의 순서가 정렬 후에도 유지된다. 안정적이지 않은 정렬은 순서가 유지 된다는 보장을 할 수 없다. 내부정렬 외부정렬 내부정렬(internal sorting) - 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우 사용하는 알고리즘 외부정렬(external sorting) - 정렬할 데이터가 많아서 하나의 배열에 저..