남남서의 블로그

거듭제곱 a의 b승을 c로 나눈 나머지를 구해야 할 때가 있습니다. 참고로 거듭제곱을 영어로는 power라고 합니다. 일단 단순히 구현하면 이렇게 할 수 있습니다. // integer power function int ipow(int a, int b, int c){ int ans = 1; for(int i = 0; i < b; ++i) { ans *= a; ans %= c; } return ans; } 한 가지 조심해야 하는 점은, 값의 범위에 따라서는 중간에 ans * a의 값이 int 범위를 넘어갈 수 있습니다. 이 문제를 피하기 위해선 중간에 잠깐 long long으로 캐스팅하면 됩니다. ... ans = ((long long) ans * a) % c; /* alternatively: ans = (..

다항식 찾기 (n+1)개의 점, 즉 $(x_i, y_i)$의 순서쌍이 (n+1)개 주어지면, 이 n개의 점을 모두 지나는 다항식을 하나 찾을 수 있다. 즉 $P(x_i) = y_i$를 모두 만족하는 $P(x)$를 찾을 수 있다. (일단 각각의 $x_i$는 모두 다르다고 하자.) 예를 들어 (1, 1)과 (2, 3)을 지나는 다항식은 $f(x)=2x-1$도 있고, $g(x)=x^2-x+1$도 있다. 이런 다항식은 여러 가지가 있고, 무한히 많다. 그런데 사실은, 그중 차수가 가장 낮은 건 n차이고, 게다가 이때의 n차 다항식은 무려 유일하다. 다항식을 왜 찾을까? ― 다항식 곱셈 문제 잠깐 다른 얘기를 해본다. 두 다항식의 곱을 계산하는 문제를 생각하자. 예를 들면 $(x^2 + x + 3)$과 $(x -..

Tree와 Heap의 합성어인 Treap은 확률적인 BST이다. Red-Black Tree, AVL Tree 등은 모든 연산에서 O(log N)의 시간복잡도를 보인다. Splay Tree 등은 평균적으로, amortized O(log N)의 시간복잡도를 보인다. Treap은 평균적으로 O(log N)이나, 최악의 경우 O(N)의 시간복잡도를 가진다. 이는 Problem Solving에서 생각보다 유용한데, 대부분의 데이터는 랜덤하게 만들기 때문에 최악의 경우가 나오기 쉽지 않다. 또한 이러한 Treap이나, 문자열의 hashing같은 경우 푸는 사람들이 사용할 소수나 알고리즘을 예측할 수 없기 때문에 임의로 최악의 경우를 만들기도 힘들다. 이제 treap이 무엇인지 설명하겠다. Treap이란 Binary..

1. 이분 탐색 이분 탐색이란 탐색의 범위를 절반으로 줄여나가는 방법을 말한다. 결정 문제 답이 yes 혹은 no로 나오는 문제. 일반적으로 이분탐색으로 풀 수 있는 문제들은 우리가 정할 수 있는 어떤 값 x가 있다. 이 x에 따라, 어떤 결정 문제의 yes/no가 정해진다. 문제에서는 그 값이 yes가 나오는 최소/최대의 x를 요구한다. x에 의한 결과는 연속적으로 변한다. 즉, x의 값이 증가/감소하다보면, 어느 순간 yes가 no로 바뀐다. 즉, x일때 yes이면 x+1(혹은 x-1)일때 no이다. 이러한 성질들을 만족한다. 즉 O와 X의 경계를 찾는 것이 목적인 문제이다. l-4 l-3 l-2 l-1 l r r+1 r+2 r+3 O O O O O X X X X KOI 2012 중,고등부 1번 : ..

한 쌍의 정점을 잇는 간선은 최대 하나이고(no parallel edges),모든 정점을 포함하는 매칭이 존재하는 이분그래프 G=(L, R, E)가 있다고 하자."이 그래프의 최대 매칭이 유일하다면 degree가 1인 정점이 항상 존재한다."에 대해 참/거짓을 밝히고자 한다. 모든 정점을 포함하는 매칭이 존재하므로 모든 정점의 degree는 1 이상이다.G=(L,R,E)의 모든 정점이 degree가 2 이상이라고 하자.여기서 서로 다른 매칭이 두 개 이상 존재한다는 것을 보이자. alternating path와 비슷한, 'alternating cycle'을 생각하자.alternating cycle이란, 그 간선들이 '매칭된 간선'과 '매칭되지 않은 간선'을 번갈아가는 사이클이다.예)1-2 x 3-4이런 ..

N개의 숫자가 있다. 이를 연속된 구간으로 나눠서, 각 구간의 수의 합을 s라고 했을 때 as²+bs+c 의 값의 합(모든 구간에서 저 값을 구한 후 다 더함)을 최대화하는 문제이다. (a, b, c가 주어짐) => maximize( a(s12+ s22+…sk2)+b(Σ)+c×k ). 여기서 b항의 값은 항상 일정하기 때문에 a와 c값만 중요하다. => maximize( a(s12+ s22+…sk2)+c×k ). dp[i] : a[i]까지의 숫자만 있다고 할 때 저 값의 최댓값. i는 1-based. i를 j까지 묶는다고 하자.1≤j≤i 이다.dp[i] = maximize( dp[j-1] + a*(sum[i]-sum[j-1])^2 + c ) for j.=a*(sum[i]^2)+maximize(dp[j-1..