dh_0e

지금 자면 꿈을 꾸지만 (백준 32029번) 2024 UCPC 예선 E번으로, 대회 당시에 내가 풀었던 문제다. 간단한 그리디 문제지만 접근을 잘못해서 시간을 많이 소비했었다. 대회가 끝나고 다시 풀어보니 너무 간단해서 앞으로 난이도를 알 수 없는 문제에 너무 쫄지 말자는 교훈을 줬던 문제이다. 해결 방법$A$를 기준으로 정렬하고, n개의 문제에 대해 브루트 포스 형식으로 먼저 끝낼 과제를 정한 뒤, 단축된 시간으로 풀 수 있는 문제의 수들을 구하면 되는 간단한 로직이다. n값이 아주 작기 때문에 $O(n^3)$도 가능하다.#include#includeusing namespace std;int t[101], vi[101];int main(){ int n, a, b, answer=0, c, solve; s..

이진 검색 트리 복원하기 (백준 32028번) 2024 UCPC 예선 D번 문제로, 팀원이 아쉽게 해결하지 못한 문제였다. 대회가 끝나고 풀어보니 본인도 2시간 넘게 걸렸 해결 방법 사실 이분 탐색, 자료 구조를 활용한 트리를 만드는 구현 문제에 가까운데 너무 복잡하다. 정리하는데 노트가 2장...1. 입력에서 받는 노드 정보를 저장해 놓고, 노드의 깊이($H_{i}$)를 기준으로 정렬한다.2. 깊이가 낮은 노드(root)부터 시작하여 모든 노드의 위치를 구한다.이때, 내 부모 노드에 저장된 값을 바탕으로 해당 노드의 자식이 될 노드들의 최솟값과 최댓값을 구하여 저장한다.ex. root노드의 왼쪽 자식 노드인 n노드가 있다 가정하면, n노드의 왼쪽 자식들은 n노드의 값보다 작아야 하며, 오른쪽 자식 노드..

세미나 배정 (백준 28305번) 2023 UCPC 예선 K번 문제로, 처음엔 그리디 + 우선순위 큐를 사용하여 시도해 봤지만, 큐가 정렬이 되는 기준을 잡는 것이 힘들었을뿐더러, $a_{i}$값이 중복되는 경우에 항상 답을 도출한다는 보장이 없었다. 해결 방법 답으로 출력될 세미나 수의 최솟값($c$)에 대하여 이분 탐색으로 접근해서 bst 함수에서 그리디하게 $i$번째 세미나의 시작 시간을 정한다. 이때 로직은 $c$가 답으로 도출될 수 있게끔 세미나의 시작 시간을 최대한 빠르게 지정한다 (물론 $a_{i}$가 속하게끔). 이후 모든 세미나의 범위에 $a_{i}$가 속하는지 확인하여 true or false를 반환한다. 반환한 값을 바탕으로 이분 탐색이 끝나면 세미나 수의 최솟값을 구할 수 있으며 ..

동전 쌍 뒤집기 (백준 32034번) UCPC 2024 예선 J번 문제로, 대회 도중에 팀원이 풀던 문제를 이어받아 반례를 찾았고, 이를 해결한 뒤 제출했지만 끝내 풀지 못하고 아쉬워하며 대회를 마쳤다.#include #include #include using namespace std;int n;int ans = 0;string coins;vector tPos;int f(int left, int right) { for (int i = left + 1; i > t; while (t--) { tPos.clear(); cin >> n; cin >> coins; ans = 0; int leng = coins.length(); ..

N수매화검법 (백준 25315번) 2022 UCPC 예선 B번, 그리디로 풀 수 있는 선분 교차 판정 문제로, N 해결 방법 가중치를 기준으로 정렬한 뒤 가중치가 낮은 베기부터 ccw 알고리즘으로 교차되는 선분의 개수를 구하여 가중치에 곱한 값을 모두 더하여 답을 도출했다. [알고리즘] CCW(Counter Clockwise) 알고리즘CCW 알고리즘CCW(Counter Clockwise)는 세 점의 방향 관계를 판별하는 알고리즘이다.주로 기하학적 문제에서 사용되며, 점 A, B, C가 있을 때 이 세 점이 시계 방향으로 배열되어 있는지, 반 시계 방향으dh-0e.tistory.com #include #include #include using namespace std;typedef long long ll..

수 정렬하기, 근데 이제 제곱수를 곁들인 (백준 25323번) 2022년 UCPC 예선 J번 문제로, 문제를 처음 읽고 나서 STL sort에 cmp 함수 만들어서 제약을 걸어주면 되는 거 아닌가?라는 생각에 쉽게 풀릴 것 같았지만 제약이 생각대로 걸리지 않았고, 다음과 같은 방법으로 해결했다. 해결 방법 (에드혹) 원래 배열을 정렬이 끝난 배열과 비교하는 과정에서 A(정렬 전 배열의 i번째에 있던 값)와 B(정렬 후 배열의 i번째에 있는 값)가 있다고 가정하자.A = B라면 위치가 변하지 않은 것으로 확인할 게 없이 넘어가면 된다.A ≠ B라면 B의 정렬 전 위치에 있던 수가 C라고 하자. C = A라면 A와 B의 위치가 바뀐 것이므로 A x B가 제곱수인지 확인하면 된다. 하지만 C가 A가 아니라면..