문제) n개의 수열로 이루어진 수열에 대해 버블 소트를 할 때, 스왑이 몇 번 발생했는지 알아내는 프로그램을 만들어보자. 첫째 줄에 n이 주어진다. 다음 줄에는 a[1]...,a[n]만큼의 수가 주어진다. 시간제한은 1초, 메모리 제한은 512MB이다. 버블 소트지만 곧이 곧대로 버블 소트를 했다간 시간 초과가 발생한다. 병합 정렬과 동일하게 진행하지만 정렬 과정에서 인덱스가 이동한 거리를 결과값에 저장하는 게 포인트다. 더보기#include #include #include using namespace std;static vector a;static vector tmp;static long res;void mergeSort(int s, int e){ if (e - s tmp[index2]) ..
문제) n개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 만들어보자.n이 1000000까지니 nlogn으로 풀면 된다. 알고리즘의 sort도 풀수 있고 병합정렬을 이용해 풀어보았다. 더보기#include using namespace std;int arr[1000001], sorted[1000001];void merge(int left, int mid, int right){ int i = left, j = mid + 1, k = left, l; while (i mid) { for (l = j; l > n; int j = n; while (j--) { cin >> tmp; arr[i++] = tmp; } mergeSort(0, n - 1); for (j = 0; j
문제) 수 n개가 주어졌을 때, 오름차순으로 정리하고 앞에서부터 k번째에 있는 수를 구하는 프로그램을 만들어보자. 알고리즘의 sort만 있으면 어디든지 갈 수 있어... 더보기#include #include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; cin >> n >> k; vector a(n, 0); for (int i = 0; i > a[i]; } sort(a.begin(), a.end()); cout
문제) ATM기에 줄을 뽑기 위해 사람들이 서있다. 각 사람마다 인출하는 데 걸리는 시간이 다르다고 했을 때, 필요한 시간의 합의 최솟값을 구하는 프로그램을 만들어보자. 첫째 줄에 사람의 수 n과 인출하는데 걸리는 시간 Pi가 주어진다. 시간 제한은 1초, 메모리 제한은 256MB이다. n의 범위가 1000으로 작기 때문에 O(n^2) 정렬을 써도 무방하다. 여기서는 그냥 알고리즘 헤더파일의 sort로 nlogn을 사용했다. 먼저 사용하는데 걸리는 시간이 작은 순으로 정렬하고 합배열로 각 시간의 합을 더해주면 풀 수 있는 문제다. 더보기#include #include #include using namespace std;int main(){ ios::sync_with_stdio(false); c..
문제) 버블 소트의 모든 데이터가 정렬 되었을 때, i 값을 출력하도록 한 소스를 C++로 작성해보았다. 해당 코드를 실행했을 때의 결과값을 출력하는 프로그램을 만들어보자. 입력으로 500,000보다 작거나 같은 n이 주어지고, 둘째줄 부터 n번째 줄까지 배열의 수가 주어진다. 시간제한은 2초, 메모리 제한은 128MB이다. 문제는 버블소트지만 n이 500000까지이기 때문에 진짜 버블소트로 풀면 시간 초과가 난다. nlogn으로 정렬을 우선 한 후 데이터의 정렬 전 인덱스와 정렬 후 인덱스의 최대값을 찾으면 i값을 구할 수 있다.더보기#include #include #include using namespace std;int main(){ ios::sync_with_stdio(false); c..
문제) n(1 입력으로 첫째 줄에 수의 개수 n, 둘째 줄부터 n개의 수가 주어진다. 절대값이 1000보다 작거나 같은 정수이다. 시간 제한은 1초, 메모리 제한은 128MB 이다. n이 1000까지 밖에 안되기 때문에 아무 정렬이나 써도 상관없다. 가장 쉬운 버블정렬을 이용해 구현해봤다.더보기#include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; vector arr(n, 0); for (int i = 0; i > arr[i]; } for (int i = 0; i arr[j + 1]) { int tmp = arr..
