devbelly

문제 https://www.acmicpc.net/problem/5867 알고리즘 Sorting 풀이 뒤섞인 문장의 가능한 높은 등수와 낮은 등수를 찾는 문제입니다. 가장 높은 등수는 다른 문장들이 거꾸로 정렬되어있을 때, 자신은 정렬된 문장을 통해 순서를 찾는 것이고 가장 낮은 등수는 다른 문장들이 올바르게 정렬되어있을 때, 자신은 거꾸로 정렬된 문장을 통해 순서를 찾는 것입니다. 코드 #include #define rep(i, n) for (int i = 0; i N; rep(i, N) { string s; cin >> s; arr.emplace_back(s); sort(s.begin(), s.end()); fi.em..

문제 https://www.acmicpc.net/problem/20366 알고리즘 정렬 풀이 서로 다른 네 수를 뽑아 두 개씩 짝지었을 때, 차이를 최소화 하는 문제입니다. NC2를 통해 가능한 조합을 뽑고 나서 인덱스들이 가리키는 수들의 합을 기준으로 정렬한 후 풀면 됩니다. 정렬된 배열(벡터)에서 각 수의 조합이 서로 다른 인덱스로 이루어졌는지 확인하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i N; rep(i, N) { int x; cin >> x; vt.emplace_back(x); } for (int i = 0; i < vt.size() - 1; ++i) { ..

문제 www.acmicpc.net/problem/18784 알고리즘 정렬 풀이 $N$개의 좌표가 주어질 때, 3개를 골라 만들 수 있는 삼각형의 넓이의 총 합 * 2을 구하는 문제입니다. 단, 만든 삼각형은 X, Y축에 평행하는 변이 존재해야합니다. 각 축에 평행해야하는 조건을 만족하려면 한 점에서 직교해야합니다. $(x1, y1)$ 에서 직교하는 삼각형을 찾기 위해 x좌표가 $x1$인 모든 좌표들과 y좌표가 $y1$인 모든 좌표들을 구해야합니다. 각각의 집합을 A, B라고 하겠습니다. $\sum (|A_i-y1|)$을 통해 y축에 평행한 모든 길이의 합을 구할 수 있고 x축에 평행한 변도 마찬가지로 풀면 됩니다. 남은 문제는 길이의 합을 구하는 것입니다. $x1$을 공유하는 $y$좌표 $a, b, c ..

문제 www.acmicpc.net/problem/1517 알고리즘 펜윅트리 풀이 $N$제한이 50만이고 배열의 inversion들을 카운트 하는 문제입니다. 버블소트에서의 교환횟수는 inversion의 수와 동일합니다. inversion이란 $i$$A[j]$ 인 상황을 의미합니다. inversion을 찾으면 swap을 진행하고 inversion의 수가 하나 줄어들고 inversion이 0이 되면 소트가 종료됩니다. 이중포문을 통해 $O(N^2)$에 inversion의 수를 구할 수 있지만 $N$제한이 50만이므로 더 빠른 알고리즘이 필요합니다. 이 문제와 비슷하다고 생각되어 좌표압축 + 세그먼트 트리로 해결하여 풀었지만 좀더 간단하게 푸는 방법을 설명해드리겠습니다. inversion을 카운트 하기 위해선..