대학 연합 알고리즘 윈터 스쿨 4회차

TonyHan·2021년 1월 27일

21) 대학연합 알고리즘 캠프

목록 보기

4/7

정렬

원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘

얼마나 빠른 시간 내에 정렬할지
메모리를 얼마나 써야 하는지

정렬의 종류

선택정렬 (빅오메가 : n^2 / 빅세타 : n^2 / 빅오 : n^2), 공간 O(1)
삽입정렬 (빅오메가 : n / 빅세타 : n^2 / 빅오 : n^2), 공간 O(1)
버블정렬 (빅오메가 : n^2 / 빅세타 : n^2 / 빅오 : n^2), 공간 O(1)
퀵 정렬 (빅오메가 : nlogn / 빅세타 : nlogn / 빅오 : n^2), 공간 O(1) : pivot을 기준으로 좌측에는 pivot보다 작은 수 우측에는 큰 수를 위치한다. 이때의 nlogn은 정렬이 왠만해서는 된다. 조건중에 N=10^5이라면 NlogN 알고리즘을 쓰라는 이야기이기도 하다. 하지만 퀵 정렬을 안쓰는 이유는 빅오가 n^2이기 때문이다. 하지만 반대로 평균속도가 가장 빠르다.
병합정렬 (빅오메가 : nlogn / 빅세타 : nlogn / 빅오 : nlogn), 공간 O(1) : 정렬되지 않은 리스츠의 크기가 1이 될때까지 절반으로 가른다. 인접한 두 개의 리스트를 정렬하면서 합친다.

STL

sort 함수(굉장히 빠른 nlogn), algorithm 헤더

하지만 STL을 쓸 수 없는 경우가 존재는 하기에 기본적인 정렬알고리즘에 대해서 어느정도 구현할 수 이어야 한다.

sort(a.begin(),a.end(), greater<> ());

이분 탐색

정렬된 리스트에서 특정한 값의 위치를 찾아내는 알고리즘

키워드

마지막 부분 혹은 끄트머리를 어떻게 처리하느냐에 따라 결과가 달라지는 경우에 사용하게 된다.

upper_bound & lower_bound

upper_bound : 찾고자 하는 값을 최초로 초과하는 값 index의 주소를 반환
lower_bound : 찾고자 하는 값보다 크거나 같은 최초의 값 index의 주소를 반환
정렬되어 있을때만 사용가능, O(logn)

#include <iostream>

문제

2750 수 정렬하기

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j,n,m;
int main(void) {
	freopen("input.txt", "r", stdin);
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);cout.tie(0);
	cin >> n;
	vector<int> a(n);
	for (i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	for (i = 0; i < n; ++i) {
		cout << a[i] << '\n';
	}
}

2805 나무 자르기

절단기의 높이를 최대한 높게해서 나무를 최대한 적게 잘라 원하는 만큼의 나무를 가져가게 하는 문제이다.

높이가 이제 중간수가 되는 문제이다.

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i, j, n, m;

vector<int> a;

int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	int high=0, low=0,mid=0;
	for (i = 0; i < n; ++i) {
		int temp;
		cin >> temp;
		a.push_back(temp);
		low = max(low, temp);
	}

	int ans = 0;
	int sum = 0;
	while (high <= low) {
		mid = (low+ high) / 2;
		sum = 0;
		for (int i = 0; i < a.size(); ++i) {
			if (a[i] > mid) {
				sum+= (a[i] - mid);
			}
		}
		if (sum < m) {
			low = mid - 1;
		}
		else {
			ans = max(ans, mid);
			high=mid+1;
		}
	}
	cout << ans << '\n';

}