목록Algorithm (121)
블로그 옮겼습니다
우선 이 문제를 풀기 위해서 한가지 선행 지식이 필요하다. N개의 노드를 가진 트리에서 모든 정점 쌍의 거리의 합을 O(N)에 구할 수가 있는데 size(i) = i번 노드를 루트로 갖는 서브트리의 노드의 수. 로 정의하여 재귀적으로 모든 노드에 대해 구하면서 각 간선을 지나는 경로의 수를 dfs로 구하는것이다. 이 전, 전 포스트에 설명이 되어있다. 하지만 이 문제는 점프 거리 k 라는 입력이 주어져서 한번에 k개의 간선을 뛰어넘을 수가 있고, 단순히 모든 정점쌍 사이의 거리의 합이 아니라 모든 정점 쌍 사이의 경로를 가기위한 점프 횟수의 합을 요구한다. 그렇기 때문에 최대 점프거리 k가 3일때, 거리가 3인 경로는 3이 아니라 1이 더해져야하고 4인 경로는 4가 아니라 2가 더해져야하는 식이다. 여기..
이 문제는 N개의 노드를 가지고 간선에 가중치가 있는 트리에서 중앙 정점이라는 것을 찾아서 이 중앙 정점에서 다른 정점까지의 모든 거리의 합을 구하는 문제이다.중앙 정점의 정의는 어떤 한 점에서 다른 모든 정점까지의 거리의 합이 최소가 되는 점이다. 처음에 트리의 중심과 헷갈려서 트리의 중심으로 풀 뻔 했는데 잘 생각해 보면 트리의 중심은 어떤 한 점에서 다른 모든 정점까지의 거리의 최대값이 최소가 되는 점이기 때문에 확실히 다른 개념이다. 그렇다면 이 중앙 정점이라는 것은 어떻게 구할까? naive 하게는 각 N개의 정점에서부터 BFS나 DFS를돌려서 한 점에서 다른 모든 점까지의 거리의 합을 구하고 이 값을 바탕으로 최소값을 갱신해 나가는 O(N^2) 의 방법이 있을 것이다. 하지만 N이 10000 ..
naive 하게 모든 노드쌍간의 거리의 총합을 구한다고 하면 총 N개의 노드에 대해 DFS 혹은 BFS를 돌려서 O(N^2) 에 구하는 것이지만 N이 좀더 커지만 사용할 수가 없다.이 때 발상을 조금 전환해서 모든 가능한 경로상에 각각의 간선이 총 몇번이나 포함되는지를 세어주면 이 것의 총합이 우리가 구하고자 하는 답이 될 것이다.그렇다면 트리에서 루트 노드를 제외한 다른 모든 노드들은 하나의 부모가 있으므로 부모와 연결된 간선을 하나씩 가질 것이므로 루트를 제외한 하나의 노드는 각각 하나의 간선과 짝지어질 것이다. 그렇다면 루트 노드를 제외한 각각의 노드에 대해 자신의 부모와 연결된 간선을 지나는 모든 경로의 가지수를 계산하여 누적해 준다면 답이 될것인데 이것은 어떻게하냐면, size(i) 를 i번 노..
1c, a->c 가 연결 되어있다면 a->c 가 없어도 a에서 b를 통해 c로 갈 수 있기 때문에 a->c 는 필요 없는 간선이 된다. 아무튼 이런 쓸모없는 간선들을 찾아서 지워주는게 문제의 핵심인데, 문제는 어떻게 해야하느냐이다. 우선 확실한건 같은 SCC내에 있는 노드 K개가 있다면 이 들이 SCC를 이루기 위한 최소한의 간선 수는 K개 이다. 이 것은 자명하다. 그리고 다른 SCC간의 간선은 딱 하나만 필요하므로 정점 압축을 한뒤 플로이드로 불필요한 간선을 지울 수가 있다. u -> k 이고 k -> v이면 u -> v 는 필요없다는 식으로 지울수있다. 그리고 SCC를 묶지않고 처음부터 플로이드로만 불필요한 간선을 지우면 되지않을까해서 새로 짜봤는데 틀렸는데, 생각을 좀 해보면. 같은 SCC 내에 ..
https://oj.uz/problem/view/OJUZ11_rail 2
http://codeforces.com/contest/776/problem/C 1 ≤ n ≤ 105, 1 ≤ |k| ≤ 10 sequence 의 길이 n과 k가 입력으로 주어지고 n개의 원소가 입력으로 주어질때 원소의 합이 k^x 의 형태인 non-empty, continuous subsequence 의 개수를 찾는 문제 우선 모든 경우를 다 따져준다면 O(n^2) 로 TLE 가 난다. 우선 누적합 pSum 을 모든 인덱스에 대해 다 구해준다. 그러면 [l,r] 의 subsequence 의 원소의 합은 pSum[r]-pSum[l-1] 로 나타낼수있다. 즉pSum[r] - pSum[l-1] = k^x 인 (l,r) 쌍의 수를 찾으면 되는데 만약 위의 식이 성립한다면 항을 적절히 넘겨서 이런식을 도출해 낼 ..
http://codeforces.com/problemset/problem/577/B n and m (1 ≤ n ≤ 106, 2 ≤ m ≤ 103) sequence의 길이 n과 m 이 주어지는데 원소의 합이 m 으로 나누어 떨어지는 subsequence 가 있는지 없는지 판별 하는 문제이다. 처음엔 일종의 dp 로dp[i][j] = subArray[~i] 의 subsequence 중 원소들의 합을 m으로 나눈나머지가 j 인 subsequence 가 있는지로 매 배열의 원소마다 선택을 하는 경우와 선택을 하지 않는경우로 나누어서 배열을 update 해주는 식으로 했는데생각해보니 그렇게 되면 시간 복잡도가 O(n*m) 이어서 TLE 가 난다. 좀 생각을 해봤는데 잘 모르겠어서 Editorial 을 봤는데 두가..
https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/winter-is-coming-12/description/ 1 ≤ Elements of array ≤ 109 1 ≤ T ≤ 10 1 ≤ N ≤ 100000 여러 테스트케이스에 대해 배열의 크기 N 이 주어지고 N개의 원소가 입력으로 들어온다.각각의 배열의 원소는 1~10억이다.연속된 부분 배열들 중 부분 배열의 원소의 합이 N으로 나누어 떨어지는 부분배열의왼쪽과 오른쪽 인덱스를 구하는 문제이다(인덱스는 1부터 시작)만약 답이 여러개라면 가장 작은 길이의 배열을, 그래도..
unordered_map, unordered_set 과 같은 해쉬맵 자료구조에서 해쉬값을 만드는데에 사용하는 해쉬 함수의 디폴트가 컴파일러 마다 다른데MSVC++ 에서는 어떤상황에서든 잘 돌아가는데G++ 에서는 디폴트 함수가 하위 16비트만 보고 해쉬값을 만들기때문에 해쉬값은같지만 실제 값은 다른 값들이 많이 존재하는 상황이 발생할 수가 있다고 한다. 이런 최악의경우에 시간 복잡도가 O(N) 이 걸리게 된다는 문제가있다..... 그러므로 입력 데이터가 골고루 나오는경우가 아니거나 hack 이 가능한 탑코더나, 코드포스와 같은 CP 환경에서는 직접 해쉬함수를 정의하여 unordered 의 세번째 인자로 넣어주거나, 굳이 O(1) 에 계산할 필요가없고 편하게 하려면 그냥 set, map 을 쓰자.. 세번째 ..
http://codeforces.com/contest/767/problem/C 이 문제는 트리가 주어지고 트리의 각각의 노드에 온도가 주어질 때 노드들의 온도의 합이 같은 세 개의 덩어리로 나누는 문제이다. 나눌수 없다면 -1을 출력 있다면 나누는 두 지점을 (답이 여러개일 경우 아무거나) 출력 하는것이다. 이 문제는 크게 세 단계로 나눌 수 있다. 1.루트 노드에서 dfs를 돌리면서 w[i] = i번 노드를 포함하는 서브트리 의 모든 노드들의 온도의 합을 구한다. 2.w[v] 가 w[root] 의 3분의 1이 되는 지점 v들을 모두 구하여 조상들에게 모두 전달해 준다.만약 노드 u 의 자식이 a,b,c 라고 했을때 a,b,c 를 각각 루트로 가지는 서브트리들에 대해 이러한 지점 v 를 가지는 자식들이 ..