2026.01.12일차 입니다.
알바하고 어쩌고 하느라 좀 많이 밀렸습니다.
어제는 시간이 꽤 있었는데 지쳤는지 기운이 안 나서 좀 쉬었습니다.
요즘 잡생각이나 괜한 걱정도 많아지고 좋아하던 게임을 해봐도 오히려 더 지치는게 상태가 많이 안 좋은 거 같습니다.
그래도 오늘은 락 수혈하니까 좀 괜찮은 거 같아요.
아무튼 정렬 풀어보았습니다.
알고리즘만 정리해도 글이 너무 길어져 글을 두 개로 나누었습니다.
정렬(1)에서는 알고리즘에 대해 설명하고 정렬(2)에서는 정렬 내장 함수를 이용해 코테 문제들을 풀어보았습니다.
2750번 수 정렬하기
문제 링크
시간 복잡도 O(n2)인 정렬 알고리즘을 사용하는 문제입니다. 버블 정렬, 선택 정렬, 삽입 정렬 등이 있습니다.
정렬 알고리즘을 공부하며 해당 블로그를 많이 참고하였습니다.
버블 정렬(Bubble sort)
인접한 두 수를 비교/정렬하는 알고리즘 입니다.
이미지 출처
첫 번째 원소와 두 번째 원소를 비교/정렬, 두 번째 원소와 세 번째 원소를 비교/정렬, ..., n-1 번째 원소와 n 번째 원소를 비교/정렬합니다.
가장 큰 원소가 맨 뒤로 이동했으므로 다시 처음부터 n-2 번째 원소와 n-1 번째 원소까지 비교/정렬하고 정렬 안된 원소 중 가장 큰 원소를 맨 뒤로 보내는 것을 모두 정렬될 때까지 반복합니다.
실행 횟수는 총 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2로 O(n2)의 시간복잡도를 가집니다.
또한 최선의 경우든 최악의 경우든 어떠한 상황에서도 O(n2)의 복잡도를 가집니다.
가장 구현이 쉽지만 인접 원소를 일일이 비교하며 불필요한 비교 반복이 자주 일어나 매우 비효율적인 알고리즘입니다.
#include <iostream>
using namespace std;
void bubble_sort(int a[], int n) {
for (int i = n - 1; i > 0; --i) for (int j = 0; j < i; ++j) if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}
int main() {
int N; cin >> N; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i];
bubble_sort(a, N); for (int i = 0; i < N; ++i) cout << a[i] << '\n';
}
다음과 같이 구현하며 인접 원소의 대소를 비교 후 정렬합니다.
선택 정렬(Selection sort)
최솟값/최댓값을 찾아 맨 앞으로 정렬하는 알고리즘입니다.
이미지 출처
처음부터 끝까지 훑으며 최솟값/최댓값을 찾아냅니다. 찾아낸 최댓값/최솟값을 맨 앞의 값과 교환합니다.
최댓값/최솟값이 맨 앞으로 이동했으므로 두 번째 원소부터 끝까지 훑으며 정렬이 안된 원소 중 최댓값/최솟값을 찾아 두 번째 원소와 교환합니다.
해당 방법을 모두 정렬될 때까지 계속 반복합니다.
실행 횟수는 총 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2로 O(n2)의 시간복잡도를 가집니다.
또한 최선의 경우든 최악의 경우든 어떠한 상황에서도 O(n2)의 복잡도를 가집니다.
버블 정렬과 동일한 시간복잡도를 가지지만 선택 정렬은 불필요한 교환이 일어나지 않아 버블 정렬보다 조금 더 빠릅니다.
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void selection_sort(vector<int>& v) {
const int n = v.size();
for (int i = 0; i < n - 1; ++i) {
int m = i; for (int j = i + 1; j < n; ++j) {
if (v[j] < v[m]) m = j;
} if (i != m) swap(v[i], v[m]);
}
}
int main() {
int N; cin >> N; vector<int> v(N); for (int i = 0; i < N; ++i) cin >> v[i];
selection_sort(v); for (int n : v) cout << n << '\n';
}
다음과 같이 작성할 수 있으며 배열을 훑으며 최솟값의 인덱스를 갱신합니다.
교환은 맨 마지막에 한 번 일어납니다.
삽입 정렬(Insertion sort)
요소를 이미 정렬된 부분과 비교하여 해당하는 위치를 찾아 삽입하는 알고리즘입니다.
이미지 출처
두 번째 원소부터 시작하며 앞의 원소는 정렬된 부분으로 간주합니다.
앞의 원소와 비교하며 해당하는 위치가 발견되면 루프를 종료하며 해당 위치에 원소를 삽입합니다.
실행 횟수는 총 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2로 O(n2)의 시간복잡도를 가집니다.
하지만 해당 위치가 발견되면 앞은 검사하지 않고 종료하는 특성 때문에 삽입 정렬은 최선의 경우에는 n-1번으로 O(n)의 시간복잡도를 가질 수 있습니다.
#include <iostream>
using namespace std;
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; ++i) {
int k = a[i], j = i - 1; while (j >= 0 && a[j] > k) { a[j + 1] = a[j]; j--; } a[j + 1] = k;
}
}
int main() {
int N; cin >> N; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i];
insertion_sort(a, N); for (int i = 0; i < N; ++i) cout << a[i] << '\n';
}
다음과 같이 작성할 수 있으며 정렬된 부분 뒤에서부터 비교하며 해당 위치가 발견되기 전까지 원소를 차례 차례 뒤로 옮깁니다.
위치가 발견되면 루프가 종료되며 해당 위치에 원소를 삽입합니다.
수 정렬하기 2
문제 링크
시간 복잡도 O(n log n)인 정렬 알고리즘을 사용하는 문제입니다. 병합 정렬, 힙 정렬, 퀵 정렬 등이 있습니다.
병합 정렬(Merge sort)
배열을 반으로 쪼갠 후 정렬 한 후 합쳐나가는 알고리즘 입니다.
이미지 출처
어떠한 상황에서도 O(n log n)의 시간복잡도를 가지지만 정렬된 데이터를 담을 배열이 추가적으로 필요하기에 메모리 사용이 비효율적입니다.
#include <iostream>
using namespace std;
int s[1000001];
// O(n)
void merge(int a[], int l, int m, int r) {
int i = l, j = m + 1, k = l;
while (i <= m && j <= r) s[k++] = a[i] <= a[j] ? a[i++] : a[j++];
if (i > m) for (int n = j; n <= r; ++n) s[k++] = a[n];
else for (int n = i; n <= m; ++n) s[k++] = a[n];
for (int n = l; n <= r; ++n) a[n] = s[n];
}
// O(n log n)
void merge_sort(int a[], int l, int r) {
if (l < r) {
int m = (l + r) / 2;
merge_sort(a, l, m); merge_sort(a, m + 1, r); merge(a, l, m, r);
}
}
int main() {
int N; cin >> N; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i];
merge_sort(a, 0, N - 1); for (int i = 0; i < N; ++i) cout << a[i] << '\n';
}
배열을 분할하고 분할한 배열 내에서 또 분할하기를 반복하기 때문에 재귀 함수를 통해 구현합니다.
나누어진 두 배열을 합치며 정렬을 진행합니다.
여기서 a[i] <= a[j] ? a[i++] : a[j++]; 값이 크거나 같다면 a[i++] 왼쪽 배열의 값이 앞으로 정렬됩니다.
값이 같을 때 왼쪽에 있던 것을 먼저 배치함으로써 입력 순서가 유지되고 이러한 정렬을 안정 정렬(stable sort)이라고 합니다.
힙 정렬(Heap sort)
최대힙/최소힙을 이용한 정렬 알고리즘입니다. 힙이란 완전 이진트리 형태의 자료구조로 부모 노드가 자식 노드보다 큰 구조를 최대 힙, 작으면 최소 힙이라고 합니다.
최대힙/최소힙은 단계별로 풀어보기 우선순위 큐에서 자세히 설명하도록 하겠습니다.
이미지 출처
최대힙/최소힙을 사용하면 최댓값/최솟값이 배열의 맨 앞에 위치하게 되므로 배열의 최댓값/최솟값을 빠르게 찾을 수 있습니다.
힙 정렬은 최대힙/최소힙으로 찾은 최댓값/최솟값을 맨 앞에 위치시키며 배열을 정렬해나가는 방식입니다.
선택 정렬에서 최댓값/최솟값을 찾는 방식을 힙으로 사용한 것이라고도 볼 수 있습니다.
전체를 훑으며 최솟값을 찾기 때문에 O(n)이 소요되며 힙 정렬을 사용하며 O(log n)이 소요되어 총 O(n log n)이 소요됩니다.
힙 정렬은 어떠한 상황에서도 O(n log n)의 시간복잡도가 소요됩니다.
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
void heap_sort(vector<int>& v) {
priority_queue<int, vector<int>, greater<int>> pq;
for (int n : v) pq.push(n);
v.clear();
while (!pq.empty()) { v.push_back(pq.top()); pq.pop(); }
}
int main() {
int N; cin >> N; vector<int> v(N); for (int i = 0; i < N; ++i) cin >> v[i];
heap_sort(v); for (int n : v) cout << n << '\n';
}
<queue> 헤더를 사용하여 다음과 같이 풀 수 있습니다.
priority_queue를 선언하여 우선순위 큐를 만듭니다. greater<int>로 선언하게 되면 오름차순으로 설정되며 이는 최소 힙이 됩니다.
이 우선순위 큐에 정렬할 배열의 원소들을 넣으면 가장 작은 값이 맨 위에 위치하는 최소 힙이 만들어집니다.
최소 힙의 가장 위에 위치한 값, 즉 최솟값을 차례 차례 배열로 옮기며 정렬을 완성합니다.
우선순위 큐를 직접 구현할 수도 있습니다.
코드를 설명하기에 앞서 우리는 해당 사실을 짚고 넘어가야 합니다.
힙을 배열으로 표현하게 되면
- 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2
- 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1
- 부모 노드 인덱스 = 자식 노드 인덱스 / 2
로 표현할 수 있습니다.
코드는 다음과 같습니다.
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void heapify(vector <int>& v, int n, int i) {
int m = i, l = 2 * i + 1, r = 2 * i + 2;
if (l<n && v[l]>v[m]) m = l;
if (r<n && v[r]>v[m]) m = r;
if (m != i) { swap(v[i], v[m]); heapify(v, n, m); }
}
void heap_sort(vector<int>& v) {
int n = v.size();
for (int i = n / 2 - 1; i >= 0; --i) heapify(v, n, i);
for (int i = n - 1; i > 0; --i) { swap(v[0], v[i]); heapify(v, i, 0); }
}
int main() {
int N; cin >> N; vector<int> v(N); for (int i = 0; i < N; ++i) cin >> v[i];
heap_sort(v); for (int n : v) cout << n << '\n';
}
heapify 함수를 통해 배열을 최대 힙으로 반환하고 heap_sort 함수에서 최대 힙의 맨 앞의 값, 즉 최댓값을 뒤로 보내며 정렬합니다.
뒤에서부터 정렬하며 정렬되지 않은 부분을 계속 최대 힙으로 반환하며 최댓값을 찾아 뒤로 보냅니다.
오름차순 정렬인데 최대 힙을 사용한 이유는 제자리 정렬(In-place)을 하기 위함입니다.
최대 힙의 맨 앞의 값, 즉 루트(v[0])에 최댓값이 있으므로 이를 뒤로 보내기만 하면 정렬이 이루어집니다.
추가적인 메모리 공간이 필요하지 않고 정렬되지 않은 부분만 힙 정렬을 진행하면 되므로 이는 제자리 정렬에 해당합니다.
퀵 정렬(Quick sort)
피벗(pivot)이라는 한 원소를 설정하여 피벗을 기준으로 왼쪽에는 작은 원소, 오른쪽에는 큰 원소를 배치시킵니다.
이 과정에서 떨어진 원소끼리의 교환이 일어나 입력 순서를 보장 받지 못해 불안정 정렬 알고리즘에 해당합니다.
이미지 출처
평균적으로 퀵 정렬의 시간복잡도는 O(n log n)이지만 최악의 상황에서는 O(n2)의 시간복잡도가 소요될 수도 있습니다.
이거 때문인지 제출하니까 시간 초과 뜨더라고요.
#include <iostream>
using namespace std;
void quick_sort(int a[], int i, int j) {
if (i >= j) return;
int p = a[(i + j) / 2]; int l = i, r = j;
while (l <= r) {
while (a[l] < p) ++l; while (a[r] > p) --r;
if (l <= r) { swap(a[l], a[r]); ++l; --r; }
} quick_sort(a, i, r); quick_sort(a, l, j);
}
int main() {
int N; cin >> N; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i];
quick_sort(a, 0, N - 1); for (int i = 0; i < N; ++i) cout << a[i] << '\n';
}
피벗을 중간값으로 설정하여 피벗의 왼쪽에는 피벗보다 작은 값, 오른쪽에는 피벗보다 큰 값을 위치시킵니다.
이후 왼쪽과 오른쪽으로 나누어 그 속에서 피벗을 설정하고 배치하기를 반복합니다.
사실 백준에서는 해당 문제를 내장 함수를 이용하여 푸는 것을 추천하고 있습니다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n, tmp; cin >> n;
vector<int> arr;
for (int i = 0; i < n; i++) {
cin >> tmp; arr.push_back(tmp);
}
sort(arr.begin(), arr.end());
for (int i = 0; i < n; i++) cout << arr[i] << '\n';
}
1년 전에 작성한 코드라 그런지 많이 기네요.
하지만 다양한 정렬 알고리즘을 직접 타이핑 하고 블로그를 작성하며 정렬 알고리즘에 대해 이해할 수 있었습니다.
정렬 알고리즘에 이해가 부족했던 1년 전에 비하면 꽤나 성장한 것 같다는 생각이 듭니다.
근데 다른 문제들은 그냥 내장 함수 쓰겠습니다.
구현해서 쓰고 하려면 귀찮아서
Top comments (0)