구사과

계산 이론은 전산학의 근간을 이루며, 컴퓨터를 사용하는 모든 학문의 수학적 분석에 있어서 중요한 역할을 한다. 계산 이론 분야의 $P = NP$ 난제는 컴퓨터 과학의 거의 모든 분야를 관통하는 중요한 문제이고. $P = NP$ 난제의 여러 중요한 실용적 의미와 그 악명높음은 이미 대중적으로도 잘 알려져 있다. 계산 이론의 내용은 전산학의 어떠한 부분을 다루더라도 만나게 되는 경우가 많지만, 대부분의 내용은 튜링 머신과 같은 복잡한 개념을 바탕으로 정의된다. 이러한 특징 때문에, 계산 이론의 많은 내용은 잘 알려져 있으면서도 제대로 알고 있는 사람은 그렇게 많지 않은 경우가 많다. NP 시간 복잡도가 Non-Polynomial의 줄임말이라는 유명한 오해가 대표적인 사례이다. 튜링 머신과 같은 개념은 매우 ..

A. Strange Device Subtask 1 (10점) 문제에 적힌 대로 모든 순서쌍을 나열한 후, 정렬하여 서로 다른 순서쌍의 개수를 세자. Subtask 4/5 (20점) 고정된 $0 \le y < B$ 에 대해서 쌍이 겹칠 수 없으니, 각각 따로 문제를 해결한 후 합쳐주자. $t = qB + y$라고 하면, $x = qB + y + q$ 로 표현 가능하다. 이때, $y$ 는 상수이고, $q(B+1) + y \mod A$라는 식은 $q$가 $T = A / gcd(A, B + 1)$ 주기로 반복됨을 알 수 있다. 각각의 구간 $[L_i, R_i]$ 에 대해서, 가능한 $q$ 의 구간을 계산할 수 있다. 가능한 $q$ 의 구간을 계산했다면, 가능한 $q \mod T$ 의 구간 역시 알 수 있다. (..

Berlekamp-Massey 알고리즘은 특정한 DP의 점화식을 찾아주는 알고리즘이다. $10^{18}$ 번째 피보나치 수를 찾기 위해서 행렬 곱셈을 짜고, 타일 채우기 문제를 풀기 위해서 수많은 점화식과 씨름하던 옛 시간은 이젠 안녕. 이제는 백트래킹 짜고 하드 코딩해서 넣으면 끝난다. 이 글은 알고리즘의 구현법, 동작 원리나 증명에 대해서 거의 설명하지 않는다. 그 이유는 내가 구현법과 동작 원리, 증명을 모르기 때문이다. 알고리즘 구현은 여기에서 복붙해서 사용하면 된다. 이론적 배경지식이 상당히 깊지만, 그 활용도가 매우 높기 때문에, 일단 이해하지 말고 작동법부터 제대로 깨우친 후, 나중에 다시 돌아와서 방법을 이해하는 것을 추천한다. 1967년 이 알고리즘을 개발한 수학자 Elwyn Berlek..