알고리즘 일지

문제 링크23054번: 누텔라 트리 (Hard) (acmicpc.net)  문제 풀이 코드를 어디서 잘못 작성했는지 모르겠다. 일단 initDp 부터 잘못된것은 확인 하였다. 풀이는 간단하다. 센트로이드 트리를 사용하여, 분할정복을 하면 된다. 센트로이드 분할을 사용하여, 각 정점을 지나는 경로만을 관리한다.이때 경로관리를 위해, 각 센트로이드 정점에서의 하위 트리로 향하는 트리들에 대한 정보를 잘 저장하면 된다.이때 하위 트리 방향으로 관리해야 할 것은, 그 방향으로 갔을 때, 만날 수 있는 빨간 정점들과, 검정색 정점들을 관리하면 된다. 특정 정점 $V$ 에서 특정 방향으로 갔을 때, 빨간 정점들과 검정색 정점들을 빠르게 구하는 방법은, 하위 센트로이드를 이용하여 구할 수 있다.$V$에서 바로 연결 ..

옛날에 나와 지금의 내가 어느정도 차이가 있는지 확인하고 싶어, 옛날에 접근도 못했던 1006번 초라기 문제를 자력솔 하고, 그 연계문제를 풀게 되었다. 보통 이런 넓혀나가면서 dp를 응용하는 풀이는 구간 단위로도 적용할 수 있다. 문제를 보자마자 구간 dp를 정의하고 분할 정복하면 되겠구나를 떠올렸고 이런 거는 세그먼트트리나 제곱근 분할로 해야 한다. 제곱근 분할을 사용해도 구간합을 구현해야 하기에 그냥 구현량이 적은 세그를 선택했다. 구간단위로 dp 되어있는 최적값들을 활용하여, 새로운 구간을 만들 때, 필요한 dp는 합쳐지는 경우의 수를 다 표현하는 dp를 찾으면 된다. 비트마스킹을 이용하여, 구간마다 왼쪽 위 왼쪽아래 오른쪽 위 오른쪽 아래를 쓰는 경우를 표현하여 dp최적값을 적용한다. 합칠 때 ..

문제 링크https://www.acmicpc.net/problem/31226https://www.acmicpc.net/problem/23049 문제 풀이 임의의 점에서 최대로 이동하면 사이클에 포함된 임의의 노드의 번호를 알 수 있다. 이 번호를 v라고 하자. 개수가 N일때, 2sqrt(N)의 질의로 찾을 순 있는데 900번으로는 어케 찾는거지 ㅜ 24.3. 4 쿼리를 날릴 때 거리가 굉장히 길다. 왜 길까? 정답은 1부터 1,000,000 까지 있다. 1,000,000! 을 k라고 하자. query(v, k) = v 가 된다. 이것을 응용하는 것 아닐 까? 답이 될 수 있는 정답의 경우의 수를 적절히 압축하여 곱한뒤, 거리 쿼리를 날리고 자기 자신으로 되돌아오는 쿼리를 적절히 빨리 발견하여, 소인수 분..

문제 링크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/1250 1250번: 색칠된 공들첫째 줄에는 공의 개수인 N과, 자신이 언제 없어지는지 알고 싶은 공의 번호 k가 주어진다. 그 다음 줄에는 공의 색이 연속된 N개의 문자열로 주어진다. (1 ≤ N ≤ 10000000)www.acmicpc.net 메모리 관리가 주된 어려움이다. 이문제를 푸는건 어렵지 않지만, 말 그대로 언어에 정통한 이해를 가지고 있어야 한다. 난 그정도는 아니다. 책을 펼치고 정석으로 공부한게 아닌게 좀 부끄럽다. 기존에 내 풀이로 짠 코드에 필요한 리소스만 땡겨서 제출했는데, 메모리 초과가 난다. 다른 풀이를 여기에 적었다. 이 문제는 128MB이라는 극악한 환경에서 수행되어야 하는 코드를 짜야한다. 체감이 안될 수도 있는데,..

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이상일 때그래프가 원형 사이클을 이..