[CF 1512E] Permutation by Sum - 1600 문제 요약 : 1~n수 중에서 (r-l+1)개 중복없이 뽑아서 s만들 수 있는지를 묻고 있다. 문제 풀이 : n부터 1씩 줄여나가면서 누적합을 쌓아가면서 s를 만든다. 이때 만들어진 수의 집합은 최소의 개수이므로 (r-l+1)개보다 적거나 같을 것이다. 만약 크다면 s를 만들 수 없다는 뜻이다. 개수를 늘리기 위해서는 작은 값부터 2개로 쪼개면 된다. 예를 들어 x라는 값을 쪼갠다면 (1,x-1) 또는 (2,x-2) 또는 (3,x-3)...이런 식이다. 이때 쪼개진 결과로 나오는 두 개의 값은 초기 집합과 겹치면 안된다. 겹치지 않는 것이 확인이 된다면 set에서 두 값을 insert 해주고 원래 x값은 삭제해준다. 가장 작은 값부터 쪼개..
[CF 1333C] Eugene and an array - 1700 문제 설명 : 배열 a의 subarray 중에서, 모든 원소의 합이 0이 아닌 경우의 개수를 구하여라. 풀이 : subarray의 합이 0이 된다는 말은 바꿔 얘기하면, prefix sum배열을 만들었을 때 값이 같은 원소가 두개 이상 존재한다는 뜻이다(그 두 지점을 각각 a,b라고 했을 때 pref[b] - pref[a-1] == 0이 될 것이므로). 따라서 왼쪽->오른쪽으로 pref배열을 돌면서 나오는 값을 map에다 집어 넣는다. key값은 누적합 값 자체를 넣을 것이고 value에는 그 값이 가장 최근에 몇 번째 인덱스에 등장했느냐를 저장한다(정확히는 등장한 인덱스 +1의 위치). 그러면 현재 prefix sum과 일치한 값이 나..
위계가 존재하는 트리에서 두 노드 a와 b가 있을 때, a가 b의 ancestor(조상)인지 확인해야 할 때 사용하는 방법이다. 트리의 루트노드에서부터 dfs순회를 시작해서 preorder로 한 번, postorder로 한 번 각각 돌아준다. 그러면 각 순회 별로 노드의 방문 순서를 기록을 해둘텐데, 당연히 preorder의 순서와 postorder의 순서는 다를 것이다. 여기서 생기는 특징은 preorder는 루트노드에서 가까울수록 순회 순서가 빠를 것이고, postorder는 루트노드에서 가까울수록 순회 순서가 느리다. 이를 이용해서 ancestor를 판별할 수 있다. 바로 a가 b의 ancestor라면 preorder로 돌았을 때는 a가 b보다 먼저 등장할 것이고, postorder로 돌았을 때는 ..
[CF 1092F] Tree with Maximum Cost - 2100 문제 설명 : 각 노드별로 가중치가 정해져있는 트리가 주어진다. 이 트리에서의 최대 cost를 구해야 하는데 cost는 (기준노드~다른노드까지의 거리) * (다른 노드의 가중치) 의 총합으로 정의된다. 여기서 거리는 기준노드~다른노드까지 거쳐야 하는 간선의 개수이다. 풀이 : 어떤 임의의 노드 i를 기준으로 cost를 구한다고 하자. 그리고 i에서 j로 기준노드를 변경할 때 어떠한 연관성이 있는지 살펴볼 것이다. $cost_i= 1*(a1+a2+...a_p) + 2*(a_(p+1)+...a_q) + 3*(...) + 1*(b1+b2+..b_s)+2*(...)$이다. 이 식에서 a1,a2...a_p는 노드 i에서 거리가 1만큼 떨어진..
[CF 1082E] Increasing Frequency - 2000 문제 설명 : 배열 내의 임의의 구간에 대해서 임의의 수를 더하거나 빼는 연산을 할 수 있다. 이 연산을 수행한 뒤 c가 가장 많이 등장할 수 있는 빈도수를 구하는 문제이다. 풀이 : 두 가지 풀이가 있다. 하나는 dp를 이용한 풀이이고 다른 하나는 그리디를 이용한 풀이인데, 그리디를 이용한 풀이가 짧고 간결하지만 아이디어적이라서 떠올리기가 쉽지는 않다. 그래서 dp를 이용한 풀이를 먼저 설명하겠다.cnt(l,r,x)를 구간 [l,r]에서 x의 등장 빈도수라고 정의하자. 그러면 이 문제는 연산을 수행한 뒤에 cnt(l,r,c)의 최대를 구하는 문제가 된다. 여기서 나는 연산을 수행할 것이기에 c가 아닌 수 d에 특정 수를 더함으로써 c..
포함배제의 원리는 여러개의 집합이 있고, 각 집합간의 교집합에 속하는 원소의 개수를 알 때, 총 합집합의 원소의 개수를 구하는 방법이다. 집합이 두개나 세개일 때 구하는 방법은 중학교 수학시간에 배웠다. 집합이 두개(A,B) 일 때는 |A합B| = |A|+|B|-|A교B|이고, 세개(A,B,C)일 때는 |A합B합C| = |A|+|B|+|C|-|A교B|-|B교C|-|A교C|+|A교B교C| 로 구할 수 있다. 그렇다면 집합의 개수가 이보다 더 많아질 때는 어떻게 계산할까? 집합의 개수가 n개일 때 합집합을 구하는 공식은 3개일 때의 공식에서 보면 살짝 유추할 수 있는데, 바로 집합의 교집합이 홀수개일 때는 더하고, 짝수개일 때는 빼는 것이다. A,B,C와 A교B교C교는 홀수개였으므로 더했고 A교B, B교C,..
확장 유클리드 정리는 $ax+by=c$ ($a,b,c$는 상수 $ x,y$는 정수인 미지수)를 만족시키는 $x,y$를 찾는 알고리즘이다. 예를 들어서 $a=3,b=4,c=10$이라면 $x=2,y=1$을 찾을 수 있게 해주는 것이다. 여기서 반드시 충족되야할 조건은, $a$와 $b$의 최대공약수가 $c$의 약수여야 한다는 것이다. 수식으로 표현하자면 $gcd(a,b)=d$일 때, $d | c$를 만족해야 한다는 것이다. 위 식에선 d=1이고 c=10이므로 충족한다. 이를 충족시키지 못하면 $x,y$는 존재하지 않는다. 그러면 본격적으로 $ax+by=c$를 만족하는 $x,y$는 어떻게 구할까? 바로 기존의 유클리드 알고리즘을 거꾸로 거슬러 올라가기만 하면 된다. 유클리드 알고리즘은 $gcd(a,b)=gcd(..
[CF 1208B] Uniqueness - 1500 문제 설명 : 배열 a가 주어지고 나는 최대 1번의 연산을 통해 구간 [l,r]에 해당하는 범위의 원소를 제거할 수 있다. 이 결과로 남아있는 배열 a에 존재하는 모든 원소는 고유하게 만들어야 한다. 내가 제거할 구간의 길이가 최소가 되도록 하여라. 풀이 : 두 가지 방법으로 풀 수 있다. 하나는 좌표압축과 이분탐색을 이용해서 모든 구간의 경우의 수(N^2)을 다 돌면서 구간의 lower bound를 찾는 방법이 있다. 좌표압축을 통해 수의 범위가 매우 커서 배열의 인덱스로 활용할 수가 없더라도 O(1)만에 바로 접근할 수 있는 방법이다. 자세한 설명은 아래에 한다. 다른 한 방법은 투포인터를 이용한 방법이다. 배열에서 어느 구간을 삭제한다는 의미는 곧..