https://www.acmicpc.net/problem/7469 Persistent Segment Tree와 비슷한 Persistent Indexed Tree(?)를 구현해서 통과했다. 실제로 구현해 본 건 처음이었는데 예전에 명우씨한테 잠깐 설명들었던게 도움이 됐다. (Persistent Segment Tree에 대한 설명은 요기에) vector로 내맘대로 구현했는데, lower_bound썼으면 좀 더 깔끔했을듯.. 시간복잡도는 O(Mlog²N) 자세한 설명은 다음에... 테스트케이스 : (출처 : NEERC Subregional Contest) #include #include #include #include #define MAXN 262150#define INF 1987654321using name..

https://www.acmicpc.net/problem/1626 두 번째로 작은 스패닝 트리 방향성이 없는 그래프 G가 있고 이 그래프에서의 최소 스패닝 트리 T가 존재한다. 문제는 최소 스패닝 트리 T보다는 크면서 가장 작은 스패닝 트리인 'The second minimum spanning tree'를 구하는 것이다.MST와 second MST의 모습입력첫째 줄에 그래프의 정점 수 V(1 ≤ V ≤ 50,000)와 에지 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 에지로 연결된 두 정점과 그 에지의 가중치가 주어진다. 음수 가중치는 없으며, 답은 int 범위를 넘지 않는다.출력두 번째로 작은 스패닝 트리의 값을 출력한다. 만약 스패닝 트리나 두 번재로 작은 스패..

https://www.acmicpc.net/problem/6591 정답이 int범위 안에 들어온다는 힌트가 주어진 Combination을 구하는 문제이다. 파스칼의 삼각형을이용한 DP로 접근을 하면 n = k = 2^(31)-1 인 경우도 있기 때문에 배열자체를 잡을 메모리가 부족하다. (DP배열을 벡터로 짜보면 될것같기도한데.. 해보진않음) 간단하게 정말 조합을 구하는 손으로 구하는것처럼 계산하면 overflow없이 계산할 수 있다. 먼저 r>n/2인경우에 r=n-r로 바꿔준다. (∵ nCr = nC(n-r)) r>0인 경우만 생각해보면, n/2>=r 이고, r>0므로 (n-r+1) >= (r+1)/r > 1 을 만족한다. 따라서 (n-r+1)/r > 1 이고, nCr < 2^31 이므로 nC(r-1)..

https://www.acmicpc.net/problem/9426 예전엔 중앙값 관련 문제 풀때 PQ 2개를 두고 풀거나 (최대/최소 중앙값을 찾는경우)parametric search로 풀었던것 같은데 오랜만에 중앙값 문제를 봐서 그런지 전에 풀었던 풀이가 기억이 나지않아 좀 다른 방법으로 풀었다. counting을 체크하는 리프노드가 65536개 짜리인 indexed tree를 구성하고, 최초 k개의 입력된 숫자를 indexed tree에 update한 뒤 중앙값인(k+1)/2번째 숫자가 어디있는지를 indexed tree에서 루트부터 역방향으로 내려오면서 탐색해서 중앙값을 찾아낸다. 마찬가지로 다음 수가 주어지면 그 수를 업데이트 해주고, 반대로 제일 먼저 들어왔던 첫번째 수를 빼주고 업데이트 하는식..

https://www.acmicpc.net/problem/14432 (머그컵 E번) 이 문제의 핵심은 문제 마지막문단에 있는 "(단, 임의의 마을 A에서 B까지 무조건 한 가지 경로가 존재한다.)" 이다. 다시말해 이 마을들간의 관계는 트리형태이고, 따라서 한점을잡아 root로 간주하여 DFS로 탐색하면서 값을 갱신해주면 정답을 도출해 낼 수 있다.

https://www.acmicpc.net/problem/14437 (머그컵 A번) DP로 접근하면 D[현재위치][남은횟수]를 가지고 풀이하면 O(N*S)에 풀 수 있을 것 처럼 보인다. 다른 방법으로는 중복조합과 포함배재의 원리를 이용해서 풀 수도 있다. 중복조합을 이용하면 속도도 빠를 뿐 아니라, combination 값을 구할 때 DP가 아닌 fermat little thm이용해서 풀면 배열을 잡을 필요가 없어진다. 즉 메모리에 구애받지 않는 풀이가 된다. 시간복잡도는 O(N+logP).

https://www.acmicpc.net/problem/1153 다양한 풀이방법이 있겠지만, Goldbach's Conjecture라 불리는 가설?을 이용하여 풀었다. 항상 소수관련문제는 정수론과 뗄레야 뗄 수 없는것 같기도하고.. Goldbach's Conjecture는 아직 증명이 되지않은 정수론 미해결문제중 하나로 "2보다 큰 모든 짝수는 두개의 소수의 합으로 나타낼 수 있다"는 가설이다. 물론 아직 반례를 찾지못해 미해결문제로 남아있다. 즉, 앵간히 큰 짝수(우리가 문제에서 접할 수 있는 수)까지는 다 성립한다는 뜻. #include int num[1000001] = { 0 };int N;void prime() { for (int i = 2; i*i

https://www.acmicpc.net/problem/1750 naive하게 생각하면 포함-배제의 원리를 생각하기 쉬우나 조금 생각해보면 TLE가 떨어질거라는 확신이 드는 문제이다. DP를 이용해 N개의 원소중 1~i번째 숫자들을 후보로 하여 최대공약수가 j인 갯수를 d[i][j]라고 놓으면 생각보다 쉽게 점화식을 세울 수 있다. #include #define MAX 10000003#define LL long longint num[101];__inline int min(int a, int b) { return a > 1]; while ..