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/7975 (AMPPZ 2012 B번) 어찌보면 흔한 BFS문제처럼 보일 수 있지만 "두 관광 명소 사이를 이동하는 와중에도 매력도가 100m마다 1씩 증가한다." 라는 조건때문에도착점이 동일하더라도 시작하는 위치에 따라 cost가 바뀐다는 점을 해결하는 것이 이문제의 키포인트로 보인다. 결국 이 문제는 변수가 아래 두가지인 셈이다.1. 현재위치와 다음위치 사이의 거리2. 다음위치의 매력도 이 문제를 해결하기위해 생각해 본 것이 한가지 변수를 고정시키면 어떻게 풀 수 있는가 였다.즉 2번 변수를 고정시켜 '만약 도시의 매력도가 모두 동일하다면 어떤점을 선택하는것이 유리할까' 라는 문제로 접근을 해보면, 간단하게도 현재위치에서 갈수있는 다음위치들중 가..

https://www.acmicpc.net/problem/9521 이 문제는 i에서 출발하여 f[i]로 향하는 간선을 직접 그려보면 몇가지 특징을 확인 할 수 있다. 1. 각 지점마다 하나의 간선을 출발시킨다는 점2. 상호간에 간선관계가 직/간접적으로 전혀 없는 덩어리?그래프?들로 이루어져 있다는 점3. 이 덩어리들안에는 무조건 단 하나의 루프가 있다는 점(자기자신으로 향하는 간선을 가진점도 루프로 간주) 결국 이 문제는 N개의 점이 몇개의 덩어리들로 나누어 져 있으며, 그 덩어리들은 각각 하나씩 루프를 가지고있다.루프에 포함되지 않는 점들은 K-1개의 경우를 가지게되고, 결국 루프를 구성하는 점들의 경우의 수를 구할 수 있어야 한다. 1번부터 M번까지, M개의 점으로 이루어진 루프가 있다면 1번 = K..

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 ..