336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.
입력으로 용액의 특성값이 주어진다. 두용액을 더했을 때 0에 가까운 값을 가지는 두 특성값을 작은 값, 큰 값을 출력한다.
[문제 풀이]
먼저 입력으로 주어지는 수를 정렬을 한다.
- 그런 후 양쪽에 있는 수(새로운 합)를 더한다.
- 더한 수가 현재 저장하고 있는 값(이전 합)보다 작다면 갱신한다.
- 만약 새로운 합이 양수라면 양수쪽 값을 더 작게하기 위해 뒤 위치에서 하나내린다.
- 만약 새로운 합이 음수라면 음수쪽 값을 더 작게하기 위해 앞 위치에서 하나올린다.
- 값을 출력한다.
위 과정으로 구할 수 있다.
[C++ source code]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include<iostream> struct minheap { int d[1<<18]; int e; minheap() { e = 0; } void clear() { e = 0; } bool empty() { return e == 0; } bool full() { return (e + 1) == (1 << 18); } void push(int i) { if (full()) return; d[++e] = i; int cur = e; while (cur / 2 > 0) { if (d[cur] < d[cur / 2]) swap(d[cur], d[cur / 2]); else break; cur /= 2; } } void pop() { if (empty()) return; d[1] = d[e]; e--; int cur = 1; while (2 * cur <= e) { int child; if (2 * cur + 1 > e) { child = 2 * cur; } else { child = (d[2 * cur] < d[2 * cur + 1]) ? 2 * cur : 2 * cur + 1; } if (d[cur] < d[child]) break; swap(d[cur], d[child]); cur = child; } } void swap(int& a, int& b) { int t = a; a = b; b = t; } int top() { if (empty()) return -1; return d[1]; } }; int mabs(int a) { return (a > 0) ? a : -a; } int im[1 << 18]; minheap PQ; int main() { int N; scanf("%d", &N); for (register int i = 0; i < N; ++i) { scanf("%d", &im[i]); PQ.push(im[i]); } for (register int i = 0; i < N; ++i) { im[i] = PQ.top(); PQ.pop(); } int s = 0; int e = N - 1; int c_diff = 2000000001; int ans[2]; while (s < e) { int diff = im[s] + im[e]; if (diff == 0) { ans[0] = im[s]; ans[1] = im[e]; break; } else if (diff > 0) { if (mabs(c_diff) > mabs(diff)) { c_diff = diff; ans[0] = im[s]; ans[1] = im[e]; } e--; } else if (diff < 0) { if (mabs(c_diff) > mabs(diff)) { c_diff = diff; ans[0] = im[s]; ans[1] = im[e]; } s++; } } printf("%d %d\n", ans[0], ans[1]); return 0; } | cs |
336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.
최소 힙을 구현해보았다.
최소 힙은 완전이진트리를 구조를 기본으로 한다.
최소 힙은 아래 속성을 만족하면 된다.
- 부모노드가 자식노드보다 키값이 더 작아야 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | #include<iostream> const int ROOT = 1; const int MAX = 1 << 15; struct minheap { int data[MAX]; int element; int capacity; minheap() { element = 0; capacity = MAX; } bool empty() { return element == 0; } bool full() { return element == MAX; } void push(int input) { if (full()) return; data[++element] = input; int child = element; bool is_ok = true; while ((child / 2) > 0 && is_ok) { if (data[child] < data[child / 2]) { swap(child, child / 2); child = child / 2; } // 부모노드와 비교 else { is_ok = false; } } } void pop() { if (empty()) return; data[ROOT] = data[element]; element--; int parent = ROOT; int is_ok = true; while (2 * parent <= element && is_ok) { if (data[2 * parent] <= data[2 * parent + 1] && data[2 * parent] < data[parent]) { swap(parent, 2 * parent); parent = 2 * parent; } // 좌측자식노드와 비교 else if (data[2 * parent + 1] < data[2 * parent] && data[2 * parent + 1] < data[parent]) { swap(parent, 2 * parent + 1); parent = 2 * parent + 1; } // 우측자식노드와 비교 else { is_ok = false; } // 아닌 경우 } } int top() { if (empty()) return -1; return data[ROOT]; } private: void swap(int a, int b) { int temp = data[a]; data[a] = data[b]; data[b] = temp; } }; int main() { minheap H; for (int i = 21; i > 0; i /= 2) { H.push(i); printf("%d\n", H.top()); } puts("pop"); for (int i = 0; i < 10; i++) { printf("%d\n", H.top()); H.pop(); } return 0; } | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | struct minheap { int d[1 << 18]; int e; minheap() { e = 0; } bool empty() { return e == 0; } bool full() { return (e + 1) == (1 << 18); } void push(int i) { if (full()) return; d[++e] = i; int cur = e; while (cur / 2 > 0) { if (d[cur] < d[cur / 2]) swap(d[cur], d[cur / 2]); else break; cur = cur / 2; } } void pop() { if (empty()) return; d[1] = d[e]; e--; int cur = 1; while (2 * cur <= e) { int child; if (2 * cur + 1 > e) { child = 2 * cur; } else { child = (d[2 * cur] < d[2 * cur + 1]) ? 2 * cur : 2 * cur + 1; } if (d[cur] < d[child]) break; swap(d[cur], d[child]); cur = child; } } int top() { if (empty()) return -1; return d[1]; } void swap(int& a, int& b) { int t = a; a = b; b = t; } void clear() { e = 0; } }; | cs |
336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.
비-비교정렬로서 낮은 자리수 부터 비교하여 정렬해 간다는 것을 기본으로 한다.
시간복잡도는 O(d*n) : n은 데이터의 개수, d는 가장 큰 데이터의 자리수 이다.
0 보다 크거나 같은 정수를 정렬하는 코드를 첨부한다.
수도코드를 참고한 것이 아니다. 그러므로 코드가 상이할 수 있다.
가장 작은 자릿수부터 넣고 다시 꺼내어 하나 더 높은 자릿수를 넣고, 이 과정이 끝날 때까지 정렬한다는 생각으로 코드를 작성했다.
- 가장 작은 자릿수부터 [0,9] 에 해당하는 값을 구한다.
- 구한 값에 해당하는 위치에 radix[자릿수] 에 값을 추가한다.
- 모든 값을 추가하고 radix[0]부터 radix[9] 순서로 먼저 값을 넣은 것부터 꺼내어 자릿수로 정렬된 수열을 꺼낸다.
- 주어진 수열에서 가장 큰 값보다 구할 자릿수 값이 커진 경우 종료한다.
- 다음으로 큰 자릿수를 구한다. 1-1을 다시 진행한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include<iostream> #include<vector> using namespace std; typedef vector<int> vi; vi radix_sort(vi v, int mx) { int rem = 10; bool ok = false; vi radix[10]; while (!ok) { int num_ok = 0; for (int i = 0; i < 10; i++) { radix[i].clear(); } // radix init for (int i = 0; i < v.size(); i++) { int here = (v[i] % rem) / (rem / 10); radix[here].push_back(v[i]); } v.clear(); for (int i = 0; i < 10; i++) { for (auto it : radix[i]) { v.push_back(it); } } if (rem > mx) ok = true; else rem *= 10; } return v; } // radix sort int main() { int n; cin >> n; vi numbers = vi(n, -1); int mx = -1; for (int i = 0; i < n; i++) { cin >> numbers[i]; if (mx < numbers[i]) mx = numbers[i]; } vi ret = radix_sort(numbers, mx); for (auto it : ret) { cout << it << endl; } return 0; } /* input 7 102 54 524 13 2 1 0 */ | cs |
336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.
이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입한다.
아래 그림을 보면 이미 정렬되어 있는 부분이 어느정도 있다고 가정하자.
이후 sort된 부분과 X를 비교한다.
그리고 X가 큰 값이 나오기 전의 위치에 값을 삽입한다.
아래는 python 로 작성한 코드이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | def insertion_sort(unsort_data): sort_data = [] for unsorted_index in range(len(unsort_data)): position = -1 pivot = unsort_data[unsorted_index] for sorted_index in range(len(sort_data)): if(sort_data[sorted_index] > pivot): position = sorted_index break if(position == -1): position = len(sort_data) sort_data.insert(position, pivot) ##print("sorting..",sort_data) return sort_data if __name__ == "__main__": ll = [31, 25, 121, 22, 11] print(insertion_sort(ll)) | cs |
336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.
모든 순열을 출력하는 문제이다.
N이 입력된다. 이때 N은 N개 수열을 뜻하며
수열은 1,2,...,N 로 구성되어 있다. 이때 사전순으로 모든 순열을 출력하면 된다.
[C++ source code]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include<cstdio> #include<vector> #define din1(a) scanf("%d", &a) using namespace std; typedef vector<int> vi; void change(vi& v, int here, int there) { int temp = v[here]; v[here] = v[there]; v[there] = temp; } void permutation(vi v, int depth, int depth_end) { if (depth == depth_end) { for (auto it : v) { printf("%d ", it); } puts(""); return; } for (int i = depth; i < depth_end; i++) { change(v, depth, i); permutation(v, depth + 1, depth_end); } } int main() { int n; din1(n); vi v = vi(n); for (int i = 0; i < n; i++) { v[i] = i + 1; } permutation(v, 0, n); return 0; } | cs |
