알고리즘이란? 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것
즉 알고리즘이란 문제 해결 방식, 문제 풀이 패러다임
빅오 표기법
시간,공간 복잡도를 표현하는 점근적 표기 방식
최악의 경우를 생각하여 계산한다.
시간, 공간 복잡도의 가장 영향력 있는 항으로 표현하고 계수는 무시한다.
- 공간 복잡도
프로그램을 실행 및 완료하는 데 필요한 저장공간의 양
총 공간 요구 = 고정 공간 요구 + 가변 공간 요구 S(P) = c+Sp(n)
고정 공간 : 입력과 관계없는 공간의 요구(상수취급)
가변 공간 : 입력과 연관이 있음(알고리즘의 공간 복잡도 계산)
재귀 팩토리얼:
공간 복잡도는 파라미터에 1이 들어올 때까지 차곡차곡 쌓이다가 종료되므로 O(n)
반복 팩토리얼:
그냥 값을 계속 곱하기 때문에 구지 많은 공간을 차지하지 않아서 O(1)
- 시간 복잡도
1초는 곧 1억번의(=10^8) 연산이 가능하다고 가정
반복문 총합 구하기
반복문을 1부터 n까지 돌리니 시간복잡도 O(n)
그냥 고익 쓰기
한번만 계산하니 O(1)
탐욕법 greedy algorithm
그냥 순진하게 모든 경우를 하면 시간, 공간 복잡도 측면에서 비효율적
모든 선택지를 고려하지 않고, 각 단계마다 지금 가장 좋은 방법만을 선택 -> 즉 사용자가 처음부터 어떤 케이스만을 고려하게 된다.
이때 정당성 증명이 굉장히 중요하다.
그리디 알고리즘이 항상 성립할까? 우리가 선택한 방법의 경우로만 탐색하기 때문에 최적해가(실제 정답) 나오지 않을 수도 있다.
그래서 그리디 알고리즘의 정당성을 증명하는 것이 중요하다. 증명하는 방법은 다음 두가지 방법이 사용된다.
- 탐욕적으로 선택하더라도 문제의 최적해를 구할 수 있다.
- 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있다.
탐욕적 선택 속성 : 각 단계에서 탐욕적으로 내리는 선택은 항상 최적해로 가는 길 중 하나
최적 부분 구조(중요) : 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있다. 대부분 자명한 경우가 많다.
문제는 어떤 방법을 선택하고 그것의 정당성을 증명하는 과정이 어렵다.
문제
1931 회의실 배정
결국에는 끝나는 시간이 중요한 문제이다. 그렇기 때문에 끝나는 시간을 우선 정렬하고 회의가 끝나자마자 다음 회의를 시작하면 된다.
회의실 배정문제가 최적해 보장 문제인지를 증명
- 어떤 회의 선택시 시간이 겹치는 회의는 선택 불가능
- 남은 회의들 집합에 대해서도 최대한 많은 회의가 진행되어야 한다.
따라서 최적 부분 문제이다.
방법을 생각해보자
- 시작 시간은 기준이 될 수 없다.
- 짧은 회의를 그리디하게 풀 수도 없다.
- 끝나는 시간으로 그리디하게 풀 수 있다.
증명을 위해 귀류법을 이용
우리 선택이 최적화로 가지 못하고 최적화가 P라는 경우뿐일때 최적해가 존재하는 선택은 그리디하지 못하다.
귀류법이 결론에 모순이 있다 가정하고 가정의 모순이 있는 것을 증명해서 결론이 참임것을 증명하는 방법이다.
여기에서는 끝나는 시간으로 그리디하게 풀면 최적해를 구할 수 있다는 것이다. 만약에 끝나는 시간으로 그리디하게 풀 수 없다고 하면 빨리시작하는 회의 혹은 짧은 회의를 선택해야 하는데 이러한 풀이로는 최적회를 구할 수 없다.
//입출력 속도 향상
//c문법과 동기화를 멈추겠다.
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);암튼 풀이
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstring>
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <string>
#define ll long long
#define len 1001
using namespace std;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 0;
vector<pair<int, int>> a(t);
cin >> t;
for (int i = 0; i < t; ++i) {
cin >> a[i].second >> a[i].first;
}
sort(a.begin(), a.end());
int ans = 1;
pair<int, int> pos = a[0];
for (int i = 1; i < t; ++i) {
if (pos.first < a[i].second) {
ans += 1;
pos = a[i];
}
}
cout << ans;
}14659 한조서열정리하고옴ㅋㅋ
계속해서 큰 놈만 업데이트 해주고 값을 구해주면 되는 문제이다.
여기에서 중요한 것 중 하나가 PS분야 문제 풀이는 전역변수를 많이 사용한다. 보통 전역변수는 초기화 해주지 않아도 0으로 초기화 되어있다.
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstring>
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <string>
#define ll long long
#define len 1001
using namespace std;
int ans, big,i;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 0;
cin >> t;
vector<int> a(t);
for (i = 0; i < t; ++i) {
cin >> a[i];
}
for (i = 0; i<t; ++i) {
if (a[big] <= a[i]) {
ans = max(ans,i - big-1);
big = i;
}
}
ans = max(ans, i - big - 1);
cout << ans;
}20044 Project Teams
문제는 두 명이 한 팀이 될때 일정한 밸런스를 맞추게 하고 최대가 되는 최솟값을 찾아내는 문제이다.
그냥 정렬하고 맨 뒤와 앞을 합쳐주면 최적해가 나온다.
ax<ay 이고 bx<by 이면 ax+bx<ax+by 인 것이 당연하다. 우리는 최솟값이 최대가 되어야 하기 때문에 섞는 것이 오히려 최대인 최솟값을 보장한다.
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstring>
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <string>
#define ll long long
#define len 1001
using namespace std;
int ans, big,i;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 0;
cin >> t;
t *= 2;
vector<int> a(t);
for (int i = 0; i < t; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
ans = -1;
for (int i = 0; i < t; ++i) {
if (ans == -1 || a[t - 1 - i] + a[i] < ans) {
ans = a[t - 1 - i] + a[i];
}
}
cout << ans;
}