정화 코딩

https://www.acmicpc.net/problem/28296 다음과 같은 순서로 생각하면 이해가 그나마 좀 쉬운 것 같다. 일단 두 창고를 연결하는 경로상의 도로 중 가장 작은 가중치가 그 경로의 상한선이 되고, 두 창고를 연결하는 여러 경로가 있을 때 상한선이 가장 큰 경로를 택한다.즉, 두 창고를 연결하는 경로가 여러 개 있을 때, 가중치가 작은 도로가 포함되지 않도록 하는 것이 최적이다. 이를 통해 가중치가 작은 간선들은 필요없고 최대 스패닝 트리를 그렸을 때 거기에 포함된 도로들만 사용하면 된다는 것을 알 수 있다. 최대 스패닝 트리를 그려야 하므로 가중치가 큰 도로부터 보면 된다. 가중치가 큰 도로부터 보면 현재 보고 있는 도로가 지금까지 봐온 도로 중 가중치가 가장 작은 도로라는 것이..

https://www.acmicpc.net/problem/20040 유니온 파인드를 이용하여 간선을 하나씩 추가하면서 사이클이 처음 생기는 순간만 찾아주면 된다.a와 b가 이미 같은 집합인데 a와 b를 연결하는 간선이 들어오면 사이클이 생긴 것이라고 판단하면 된다. #include #include using namespace std;int n, m;vector parent;int find(int a) { if (parent[a] == a) return a; else return parent[a] = find(parent[a]);}int unite(int a, int b) { a = find(a); b = find(b); if (a != b) { parent[b] =..

https://www.acmicpc.net/problem/2357 최솟값과 최댓값을 둘 다 구해야 하므로 세그먼트 트리를 구조체로 만들어보았다.세그먼트 트리를 구조체로 선언하면 세그먼트 트리가 여러개 필요한 문제에서 유용하다고 한다.이 문제에서는 MinSegTree와 MaxSegTree를 따로 만들어서 풀어보았다. 또한, init 함수 없이 update 함수만으로 세그먼트 트리를 초기화해줄 수 있다. #include #include using namespace std;int MIN_VAL = 0;int MAX_VAL = 1000000001;int n, m;struct MinSegTree { vector tree; int update(int idx, int l, int r, int target,..

https://www.acmicpc.net/problem/6549 히스토그램에서 가장 넓이가 큰 직사각형은 다음의 셋 중 하나이다. 1. 최솟값을 포함하면서 전체 구간의 직사각형 2. 최솟값 기준 왼쪽 구간에서의 가장 큰 직사각형 3. 최솟값 기준 오른쪽 구간에서의 가장 큰 직사각형 그 이유는 다음과 같다.최대 직사각형은 최댓값을 포함할 수도 있고 포함하지 않을 수도 있다. 만약 최솟값을 포함한다면 구간을 최대로 잡아도 좌우로는 잘리지 않기 때문에, 양쪽 끝까지 구간을 잡는 것이 최대이다. 만약 최솟값을 포함하지 않는다면 해당 최솟값을 기준으로 구간이 이미 잘렸다고 생각하면 된다. 그렇기 때문에 그 값 기준 왼쪽에서의 최대와 오른쪽에서의 최대를 구한다. 따라서 세그먼트 트리로 저장해야 하는 정보는 구간..

https://www.acmicpc.net/problem/2042세그먼트 트리란?세그먼트 트리는 구간에 대한 정보를 트리 구조로 저장하여, 구간의 갱신과 조회를 효율적으로 처리할 수 있도록 설계된 자료구조이다.세그먼트 트리의 원리1번 노드는 1~8 구간의 정보를 담고 있고2번 노드는 1~4 구간의 정보를, 3번 노드는 5~8 구간의 정보를 담고 있고...이런 구조로 되어 있다. 3~7 구간의 정보를 알고 싶다고 생각해보자. 우선 루트 노드에서 시작해서 쭉 내려간다. - 내 구간이 목표 구간에 완벽히 포함되지 않으면 절반으로 쪼개서 자식 노드로 전달한다.- 만약 완벽히 포함된다면 내가 가지고 있는 정보를 그대로 위로 다시 올리면 되고, 만약 전혀 겹치지 않는다면 항등원을 반환한다. 세그먼트 트리 구현아래 ..

2회차 - 선형 자료구조, 제곱 정렬  에디터https://www.acmicpc.net/problem/1406#include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); string s; cin >> s; list li(s.begin(), s.end()); int n; cin >> n; // 최초의 커서 위치는 문장의 맨 뒤 auto cur = li.end(); while (n--) { char cmd; cin >> cmd; if (cmd == 'L') { // ..

https://www.acmicpc.net/problem/12873 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector a(n); for (int i = 0; i 태그는 큐인데 나는 그냥 vector와 erase 함수를 사용했다. 근데 여기서 주의할 점이 두 가지가 있다. (내가 여러번 틀린 이유...)1. cmath에 있는 pow(i, 3)를 사용하면 값이 의도대로 나오지 않을 수 있다. pow의 반환값이 double이라서 int로 바꾸는 과정에서 문제가 생길 수 있기 때문이다. 그래서 ..

https://www.acmicpc.net/problem/1406 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); string s; cin >> s; list li(s.begin(), s.end()); int n; cin >> n; // 최초의 커서 위치는 문장의 맨 뒤 auto cur = li.end(); while (n--) { char cmd; cin >> cmd; if (cmd == 'L') { // 커서가 맨 앞이 아니라면 한 칸 앞으로 이동..