백준 알고리즘 중급 - 정렬

차곡차곡

기본 중에 기본이 되는 알고리즘. 그만큼 중요하다.

중요하고 자주 사용되는 만큼, 대부분의 정렬 함수는 C++에서 표준 함수로 제공한다.

하지만 정렬 자체로는 그리 의미 있는 문제가 많이 없어서

간단하게 중요한 개념 정리하고, 풀면서 조금 헷갈렸던 문제를 꼽아 정리했다.

정리 시작!

-

* 정렬 (Sorting) : 리스트에 담긴 자료를 어떠한 순서로 나열하는 것. 선택, 버블, 삽입, 퀵, 힙, 병합 등 다양한 정렬 알고리즘이 있는데.. 그냥 빠른 걸 사용하면 된다. 확장성을 가지려면 O(nlogn)이 걸리는 정렬을 사용해야 한다. 보통 STL로 제공되는 sort 함수를 사용하는데, 이는 퀵 정렬을 기반으로 한다.

 - 기본값은 오름차순이지만, 여러 값을 기준으로 정렬하고 싶으면 함수를 따로 만들면 된다. 결과에 따라 bool 값을 리턴하며, 인자에는 const와 &를 꼭 포함해야 한다.

 - stable sorting : 같은 것이 있는 경우, 정렬하기 전의 순서가 유지되는 정렬 알고리즘을 말한다.

 - 아래엔 단순히 sort만 사용해서 풀 수 없는 예제들만 정리해봤다.

 

* 수 정렬하기 3 (low) : 10^7개까지 가능한 수를 정렬하려면 단순히 sort 함수를 사용해서는 풀 수 없다. 

10989번: 수 정렬하기 3

 - 수의 개수는 10^7개지만, 입력 가능한 수의 범위는 10^4까지다. 따라서 배열을 만들고 그 수가 나온 만큼 순서대로 출력해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	int cnt[10001] = { 0, };
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		cnt[t] += 1;
	}

	for (int i = 1; i <= 10000; i++) {
		if (cnt[i] != 0) {
			for (int j = 0; j < cnt[i]; j++) {
				cout << i << '\n';
			}
		}
	}

	return 0;
}

 

* 카드 (mid) : 가장 많이 갖고 있는 정수를 출력한다. 정수의 범위가 -2^62에서 2^62까지다..

11652번: 카드

- 일단 정렬하고, 앞에서부터 세주면 된다. 알고리즘을 이쁘게 짜는 요령을 익히고 넘어가자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<long long> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	
	long long ans = a[0];
	int cnt = 1;
	int mcnt = 1;
	for (int i = 1; i < n; i++) {
		if (a[i] == a[i - 1]) {
			cnt += 1;
		}
		else {
			cnt = 1;
		}
		if (mcnt < cnt) {
			mcnt = cnt;
			ans = a[i];
		}
	}
	cout << ans << '\n';
	return 0;
}

- cnt 값은 1로 항상 초기화 한다. 다음 항이 같으면 +1 해주고, 최댓값과 계속 비교해주면 된다.

 

* 버블 소트 (mid) : 주어진 버블 소트 코드를 돌리면 나오는 출력값을 구하는 문제다.

1377번: 버블 소트

- 문제에 주어진 코드는 다음과 같다.

bool change = false;
for (int i=1; i<=n+1; i++) {
    change = false;
    for (int j=1; j<=n-i; j++) {
        if (a[j] > a[j+1]) {
            change = true;
            swap(a[j], a[j+1]);
        }
    }
    if (change == false) {
        cout << i << '\n';
        break;
    }
}

- 버블 소트를 계속 하다가 출력이 되는 타이밍은 change가 false일 때, 즉 더이상 정렬이 필요 없을 때다.

- 이 문제의 핵심은 버블 소트를 할 때 swap이 되는 원리를 파악하는 것이다. 버블 소트의 특성상, 앞쪽에서 뒤쪽으로의 이동은 자유롭다. 크기에 따라 맨 뒤까지 이동할 수도 있다. 하지만 뒤쪽에서 앞쪽으로의 이동은 한 턴에 한 칸씩으로 제한된다. 따라서 더이상 이동할 필요가 없을 때를 찾으려면, 뒤쪽에서 앞쪽으로 이동한 거리가 가장 큰 값을 생각해주면 된다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<pair<int, int> > a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a.begin(), a.end());
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (a[i].second - i > 0) {
			if (ans < a[i].second - i) {
				ans = a[i].second - i;
			}
		}
	}

	cout << ans + 1 << '\n';

	return 0;
}

- 최대 이동 거리에 1을 더해주는 이유는, 정렬을 마친 다음 인덱스, 즉 더이상 정렬이 필요 없는 지점을 출력해야 하기 때문이다.

-

정렬 자체로만 다룰 수 있는 문제는 제한적이어서 그렇게 많은 예시가 없었다.

하지만 거의 모든 알고리즘 문제에서 활용한다고 해도 과언이 아닌 중요한 알고리즘이다.

기본 옵션(?)이라고 생각하면 되겠다.

이렇게 간단하게 정리 끝!