알고리즘 일지

문제 링크https://www.acmicpc.net/problem/31226https://www.acmicpc.net/problem/23049문제 풀이 (시간에 따라서 적어 놨던 글을 공개한 것입니다. 두서가 없을 수 있습니다.) 임의의 점에서 최대로 이동하면 사이클에 포함된 임의의 노드의 번호를 알 수 있다. 우린 이 임의의 노드에서 시작해 보자.이 사이클에 포함된 임의의 번호를 $\text{s}$라고 하자.개수가 N일 때, 제곱근 분할법을 사용하면, 무조건 겹치게 할 수 있기 때문에, $2\sqrt{N}$의 질의로는 가능하다.24. 3. 4문제에 대해 접근방법을 바꿔야 할 것 같다고 생각했다. 문제를 보면, 쿼리를 날릴 때 거리가 굉장히 길다.왜 길까?정답은 1부터 1,000,000까지 있다.$1,0..

문제 링크9250번: 문자열 집합 판별 (acmicpc.net) 문제 풀이 KMP를 이용한 브루트 포스 풀이로, 문제를 제한시간내에 풀지 않았던 문제였다.클래스 8+가 깨져있길래, 살펴 보았더니, 이 문제의 데이터가 강력하게 업데이트 되어 있었다. 그래서 아호코라식을 살짝 보았다. 아호코라식은 자료구조 Trie 에서의 Kmp를 적용하는 것을 말한다.이미 kmp는 배웠었고, Trie 도 알아서, 그냥 구현했다. 아호코라식의 구현은 dfs를 통해 포인터를 리턴하는 것으로 간단하게 하였다. 말 그대로 아호코라식을 이용하면, 문자열 집합에서 매칭을 선형으로 탐색할 수 있다. 기존풀이는, 문자열 집합 $\textbf{T}$ 에 대해, $\textbf{T}$를 Trie 자료구조를 이용하여, 저장한다음, 매칭 대상 ..

풀이 1 f[x] 를 x노드의 문제에 지정된 수식값이라고 하자. 특정 노드에 i에, A[i]++ 연산이 추가되면, 모든 노드 j에 대해, f[j] += dist(j, i) 이다. 이 연산…. 서브트리에 날릴 수 있다. 그 위로는? 방법이 보이지 않는다… 풀이 2 그럼 A[i]를 직접 헤비라잇과 오일러투어로 합쳐만들고, 연산 시켜준다. Weighted centroid라는 정점이 이때, 답이 되게 되는데, 그 이유는 최대한 가중치들의 가운데에 있는 정점이 경로가 겹치는 것을 피할 수 있기 때문이다. 이거 어케구하는지 모른다;;

https://www.acmicpc.net/problem/7890 7890번: 가까운 점 찾기입력은 여러 개의 테스트 케이스로 주어진다. 첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 15)가 주어진다. 이후 각각의 테스트 케이스마다, 첫 번째 줄에 N (2 ≤ N ≤ 105) 이 주어진다. 이후 N개www.acmicpc.net델로네 삼각분할을 이용하여, 한 점이 이루고 있는 선분 중 가장 작은 값이 정답이 되겠다.Incremental Delauncy Triangulation 은, 나도 어떻게 구현 해야 할 지 모르겠다.어떤 삼각형에 속하는지 알아내야 하는데, 난 잘 모르겠다. 이것도 스위핑으로 하면 될텐데…다른 방식으로 보로노이 다이어그램을 이용한다.보로노이 다이어 그램과 삼각분할은 듀얼 그래프..

https://www.acmicpc.net/problem/2430 2430번: 거울대칭트리 그래프첫째 줄에 N과 M이 주어진다. N은 정점의 개수 M은 간선의 개수이다. 그래프의 정점은 1부터 N까지 번호가 매겨져 있다. 다음 M개의 줄에는 x와 y가 주어진다. (x ≠ y, 1 ≤ x, y ≤ N) x와 y는 하나의 간www.acmicpc.net 이걸 풀기 위해, 트리 동형을 공부하고 왔다. Case 1 : degree가 1 인 정점이 존재 할 때정점이 2개 이여만 한다두 정점을 루트로 하는 트리를 만드며, BFS를 돌려, 동시에 접하는 정점까지 트리로 만든다.동시에 접하지 않는다면, 틀린 그래프 이다.두 트리가 동형인지 비교한다. Case 2 : degree가 다 2이상일 때그래프가 원형 사이클을 이..

안녕하세요. 참가자 여러분들! 2023 SW - IT Contest에 운영진으로써 참여하게 된 황현석이라고 합니다.이번 운영진 체험(?) 비스무리한 활동을 하며, 얻어가는 것도 배워가는 것도 많은 뜻깊은 좋은 시간이었다고 생각합니다. 대회 당일날 딱봐도 군인처럼 생긴 이상한 아저씨가 한명 돌아다니고 있었는데요!.. 저였습니다.. 그냥 휴가를 나왔는데, 대회 일정이랑 겹쳐 있어서 운이 좋았네요!!... 오랜만에 학교 공기도 쐐고.. 흐음~~공기가 별로 좋지는 않았어요..    1등이.. 22학번 최약체라... 그중 최약체가 1등을 하게 되었군요. 제가 빨리 복귀해야겠어요.그리고 이번에 1등한 최약체는 내년에는 군대에 있겠지만, 출제에 참여 할 수 있도록 제가 강제 조취하겠습니다.  저는 23. 1. 17일..

https://www.acmicpc.net/problem/25353 25353번: 게임의 꽃주어진 트리에서 길이가 가장 긴 증가 경로는 번호가 4, 2, 5인 정점을 순서대로 지나는 경로이다.www.acmicpc.net 생각 나는 걸 순서대로 적어 놓은 곳입니다. 풀이 1 A [i]를 i의 서브트리로 가는 방향에서 가장 긴 증가 경로의 길이, B [i]를 증감경로 라고 하자. 그럼 정답은 모든 정점 i에 대해, max(A[i] + B[i] - 1)이다. 초반에 A와 B배열은 dfs를 이용하여 , O(N)에 찾을 수 있다. 어떻게 하면, A와 B배열을 빠른 속도로 업데이트할 수 있을까? 풀이 2 순서에 의해 연결될 수 있는 수열에 대해 가중치 1, 없는 수열에 가중치 -1e 9를 부여, 그 후 최대 연속합..

문제 링크 27989번: 가장 큰 증가하는 부분 수열 2 (acmicpc.net) 27989번: 가장 큰 증가하는 부분 수열 2 길이가 N인 수열에서 0개 이상 N-1개 이하의 원소를 지워서 만든 수열 중, 길이가 1이거나 임의의 인접한 두 항 중 뒤의 항이 앞의 항보다 큰 수열을 증가 부분 수열이라고 한다. 양의 정수 N개로 www.acmicpc.net 문제 풀이 $O(N\log N)$ $dp[x]$를 x를 마지막으로 하는 증가하는 부분 수열 의 합중 가장 큰 값이라고 하자. 1번째 수부터, 마지막 수까지, 그 숫자와 범위를 마지막으로 하는 부분 수열중 가장 큰 값을 구해보자. 즉, 모든 $i$에 대해, 구간 $[1, i]$ 에서, $A_{i}$로 끝나는 증가수열 중, 가장 큰 합을 $dp[A_{i}]..