기록을

#include <bits/stdc++.h>
using namespace std;

bool cmp(int a, int b) { //정렬
	//return a > b;
	if (a > b)
		return true;
	else
		return false;
}

void vectorPrac(){ //벡터
	vector<int> v;
	v.push_back(0);
	v.push_back(1);
	v.push_back(-1);

	sort(v.begin(), v.end(), cmp); //정렬 함수 사용자 정의

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << ' ';
	}
	cout << '\n';

	v.erase(v.begin() + 1); //특정 인덱스 원소 제거

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << ' ';
	}


	vector<string> strv;
	strv.push_back("abc\n");
	cout << strv[0];

	string a = "abcdef";
	string subs = a.substr(1, 3); //1번째부터 시작해서 길이 3만큼
	cout << subs << '\n';
}


void stackPrac(){ //스택
	stack<int> stk;
	stk.push(1);
	stk.pop();
	stk.push(5);
	stk.push(4);
	cout << "스택크기 = " << stk.size() << '\n';
	while(!stk.empty()){
		cout << stk.top() << ' ';
		stk.pop();
	}
	cout << '\n';
}

void queuePrac(){ //큐
	queue<int> q;
	q.push(1);
	q.push(2);
	cout << "큐 크기 = " << q.size() << '\n';
	while(!q.empty()){
		cout << q.front() << ' ';
		q.pop();
	}
	cout << '\n';
}

void mapPrac(){
	map<string, int> mp;
	mp.insert({"abc", 1});
	mp.insert({"def", 2});
	mp.insert({"abc", 3}); //이미 존재하는 key에 대해서 insert 하면 무시된다
	mp["abc"] = 3; //하지만 이렇게 수정하면 반영된다.
	for(auto itr = mp.begin() ; itr != mp.end() ; itr++){
		cout << itr->first << " " << itr->second << '\n';
		cout << itr->first << " " << mp[itr->first] << '\n';
	}
	cout << "맵 크기 = " << mp.size() << '\n';
	
}

void setPrac(){
	vector<int> v = {4,4,4,5,1,1,1,2,3};
	for(int i = 0 ; i < v.size() ; i++){
		cout << v[i] << ' ';
	}
	cout << '\n';
	
	set<int> st;
	for(int i = 0 ; i < v.size() ; i++){
		st.insert(v[i]);
	}
	for(auto itr = st.begin() ; itr != st.end() ; itr++){
		cout << *itr << ' ';
	}
	cout << '\n';
	
	set<int, greater<int> > bigSt;
	for(int i = 0 ; i < v.size() ; i++){
		bigSt.insert(v[i]);
	}
	for(auto itr = bigSt.begin() ; itr != bigSt.end() ; itr++){
		cout << *itr << ' ';
	}
	cout << '\n';
}
void priority_queuePrac(){
	priority_queue<int, vector<int>, less<int> > pq; //내림차순으로 나오는
	pq.push(9);
	pq.push(1);
	pq.push(4);
	pq.push(5);
	pq.push(2);
	while(!pq.empty()){
		cout << pq.top();
		pq.pop();
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	vectorPrac();
	stackPrac();
	queuePrac();
	mapPrac();
	setPrac();
	priority_queuePrac();
	
}

퀵소트: 

평균 nlogn, 

최악 n^2(데이터가 이미 거의 정렬되어 있는 경우)

머지소트: 

평균: nlogn보장

단점: 메모리 비효율적이라는 문제-> 힙소트로 해결

힙소트:

일단 데이터를 가지고 힙구조를 만들어야함. 이 부분의 복잡도 == NlogN

그리고, 루트의 값을 맨 뒤로 보내면서, 보낸 값을 제외하고 다시 힙을 만드는 비용이 logN. 이걸 N번 반복하니까 NlogN

결국 합치면 총 시간 복잡도는 NlogN이 된다.

장점: 메모리 효율적.

삽입 정렬에 대해 정리해보자.

삽입 정렬은, 선택 정렬 그리고 버블 정렬과 함께 대표적인 시간 복잡도 O(n^2) 알고리즘이다.

하지만 삽입 정렬은, 필요할 때까지만 삽입(스왑)이 일어나기 때문에, 정렬할 배열이 거의 정렬되어 있는 상태라면 다른 선택 정렬, 버블 정렬보다 훨씬 빠른 속도를 보여준다.

버블 정렬 알고리즘에 대해 정리해보자.

이름에서도 알 수 있듯이, 하나의 원소와, 인접원소를 한 칸씩 움직이면서 비교해가는 모습이 거품이 생기는 것 같아서 버블 정렬이다.

굉장히 비효휼적인 알고리즘이고, 시간 복잡도가 O(n^2)이다.

가장 먼저 정리할 정렬 알고리즘은 선택 정렬(insertion sort) 알고리즘이다.

이름에서도 알 수 있듯이, 오름차순으로 정렬한다고 하면, 매 수행에서 가장 작은 값을 선택해서 가장 앞으로 보내는 것이다.

시간 복잡도는 O(n^2)이다.

다음은 특정 배열을 오름차순으로 정렬하는 코드이다.

https://www.acmicpc.net/problem/15688

위 문제를 counting sort로 구현해 봤다.

주어지는 수의 절댓값이 1,000,000 이하이기 때문에 배열의 인덱스를 활용할 때 음수 처리를 위해 1000000을 더해준 인덱스에 저장한다.

1의 갯수는 1000001에 저장되는 것이다. 

따라서 출력할 때, 1000000을 빼고 출력해주면 된다.

먼저 최대 공약수 gcd는 재귀로도 구현할 수 있고, 아래와 같이 반목문으로 구현할 수도 있다.

어느쪽이 큰 수인지 지정해줘야 한다.

이후에 큰수를 작은수로 나누고, 나눈 수를 다음에 나눠질 수로 정한다. 나머지는 다음에 나눌 수가 된다.

0으로 나눌 수는 없기 때문에 루프를 빠져 나간다고 외워도 좋고, 나머지가 0이 되었다는 것은 약수를 찾았다는 뜻이니까 루프를 빠져 나간다고 기억해도 좋겠다.

( ll은 long long 타입을 의미한다)

int gcd(ll a, ll b) {
    if (a < b) swap(a, b); //a를 큰수로
    while (b != 0) {
        ll r = a % b;
        a = b;
        b = r;
    }
    return a;
}

다음으로, gcd를 활용해서 최소 공배수 lcm을 구하는 과정도 간단하게 구현할 수 있다.

ll lcm(ll a, ll b) {
    return (a * b) / gcd(a, b);
}

최소 공배수의 정의대로, 두 수의 곱을 최대 공약수로 나눠주면 된다.

이를 활용해서, 여러개의 숫자의 최소 공배수를 구하는 과정을 보자.

ll finY = Y[0];
    for (int i = 1; i < Y.size(); i++)
        finY = lcm(finY, Y[i]);

finY에 벡터 Y의 원소들의 최소 공배수가 들어가게 된다. 먼저 벡터 Y의 0번째 값으로 finY를 초기화 한다.

그리고 다음 원소와 lcm을 구해서 저장하고, 또 저장한 lcm과 다음 원소의 lcm을 구하는 과정을 반복해주면 된다.

*기하

그라함 스캔 과정

1. 극값 찾기(y값 작은거, 같다면 x값 작은거)

2. 극값기준 각도순 정렬

3. n번 루프돈다. 스택 크기 2이상 유지하면서 b[i] 0이하이면 pop. 밖에서 push

4. 필요에 맞게 마지막에 처음점 추가(다각형의 선분으로 무언가 할 때)

볼록껍질 최단거리 찾는법

1. 그라함 스캔을 돌려서 볼록 껍질을 형성한다. (마지막에 첫점 추가)

2. n번 루프돈다. j=1부터, j가 1이랑 다를때만 방향벡터 ccw가 양수이면 j++해준다.

j==s.size()-1이 되면 0으로 낮춰준다.

3. 양수가 아니게 되면 i와 j의 거리를 비교해서 최대인지 확인한다

-----------------------------------------------------------------------

*그래프

플로이드 와샬

1. n <= 500일때만 사용하자.

2. 바깥부터 k i j 순으로 루프 돌리고, k거쳐가는거랑 그냥가는거 길이 비교해서

작은 값으로 갱신해준다.

3. 모든 정점사이의 비용 계산에 용이 -> 모든 정점의 연결상태 파악 가능

벨만포드 -> 시작점 존재

0. 초기에 비용 무한대로 초기화. 시작점 비용은 0으로

1. 음수가중치가 존재할 때 사용. 사이클이 없어야한다.

2. 가장 바깥에서 n번 돌린다.(n번째에 갱신이 발생하면 음수사이클 존재)

3. 그 안쪽에서 정점 개수만큼 루프를 돈다.

4. 정점마다 연결된 간선 크기만큼 루프 돌면서, 목적지가 갖고 있는 거리가,

이곳에서 그 정점으로 가는 거리보다 크다면 갱신한다.

5. 이걸 확인할 때, 현재 위치까지의 비용이 무한이 아니어야 한다.

다익스트라

1. 가중치가 양수인 그래프의 최단거리를 젤 수 있다.

2. 방문처리와 우선순위큐가 필요하다(민힙), pii 배열의 인덱스가 시작점, first 비용, sec 목적지 

3. 비용을 무한대로 초기화해주고, 시작점은 0으로 만든다.

4. 시작점을 pq에 넣고, pq가 빌 때까지 실행한다.

5. pq에서 확인하는 지점을 방문처리 한다.(top)

6. 그 지점과 연결된 간선들을 확인할 것인데, 그 연결된 지점이 방문한 지점이면 스킵한다.

7. 거리비교해서 갱신조건 만족할 때만 push한다.

LCA (최소공통조상)

1. DFS로 각 노드의 깊이 계산, 2^0번째 부모 계산

2. 2^k번째 부모는 2^k-1번째 부모의 2^k-1번째 부모임을 이용해서 배열 채우기

3. 비교하고자 하는 노드의 높이를 같게 맞추기(탑다운으로) (뭐가 깊고 뭐가 얕은 노드인지 구분해서)

4. 이때 최대 높이는 (int)floor(log2(n))

5. 높이차이가 2^k보다 커질때마다 깊은점을 k번째 부모로 갱신

6. 높이를 맞춘 이후에, 두 노드가 같다면 그게 답

7. 이번에도 kmax부터 내려오면서 deep과 swall의 부모가 다르다면 둘다 k번째 부모로 갱신

8. 루프를 빠져나오면 0번째 부모가 답

두 선분이 주어질 때 선분의 교차를 판별하는 법에 대해서 알아보자.

각 선분은 2개의 정점으로 주어질 것이다.

각 선분을 가지고 다른 선분과 ccw를 돌린다. 

ccw(선분 하나와 다른선분의 정점) * ccw(선분 하나와 다른 선분의 다른 정점) <=0 and ccw(다른 선분과 선분 하나의 정점) * ccw(다른 선분과 선분 하나의 다른 정점) <=0

등호는 선분이 서로 관통하지는 않고 딱 만났을 경우이다. 여기서는 이 경우 또한 교차했다고 본다.

위의 조건까지 성립하게 되면, 물리적으로는 아니지만 두 선분이 이루는 각도 상으로는 만날 수 있는 조건을 충족한다.

선분이 아니라 직선이었다면 위의 조건까지만 충족해도 만나는 것이다. 하지만 선분이기 때문에, 어떻게 놓여있느냐에 따라서 만날 수도 있고 아닐 수도 있다.

선분 하나의 두 x좌표가 다른 선분의 두 x좌표보다 모두 작거나, y좌표 또한 이렇다면 두 선분은 만나지 못한다. 이를 코드로 표현하면 다음과 같다.

(ccw, isCross 함수를 보면 된다. main에서 특별히 뭘 하는 건 없음)

벡터의 외적을 이용하여, 평면상에 세 점이 주어질때, 점들의 위치관계를 파악할 수 있다.

점 세개로 선분 두개를 만들어서 CCW를 적용했을 때, 결과가 양수라면 회전 방향이 시계 방향인 것이다.

(참고로 벡터의 외적은 교환법칙이 성립하지 않는다.)

중학 수학에 사용했던 신발끈 공식을 생각하면 기억하기 쉽다.

또한 CCW를 위와 같이 선분들이 놓여져있는 상태를 파악할 때 사용할 수도 있고, 면적을 구할때도 사용할 수 있다.

특정 다각형의 면적을 구하고자할 때, 외부의 점을 잡고 다각형 상의 두개의 점을 순차적으로 이용해서 CCW를 돌려줘서 더하고, 그 결과에

절댓값을 취한 후에 2로 나누면 넓이를 구할 수 있다.

음수 결과와 양수결과가 중간중간에 상쇄되는 것을 이용한 것이다.

아래의 코드는, 세점의 위치관계를 CCW를 이용해서 파악해보는 것이다.

점 p1, p2, p3가 차례로 입력이 주어지면, 선분 p1p2에 대해서 선분 p2p3가 어떻게 놓여 있는지 알 수 있다.

동일선상에 있으면 0을 반환하고, 반시계 방향으로 위치해있으면 1을 반환한다.