알고리즘14 nim game과 grundy number nim game과 grundy number를 익히기 전에 이와 같은 필승 전략 게임이론이 적용되기 위한 전제조건부터 알아보자. Impartial game 두 플레이어가 게임을 하는데 아래 조건을 만족해야 한다. 모든 정보가 공개된 게임 두 플레이어가 할 수 있는 행동이 같은 게임 첫 번째 조건으로 포커 같은 게임은 해당되지 않는다. 모든 정보가 공개되어있지 않고, 서로 상대의 패를 모르기 때문이다. 두 번째 조건으로 바둑, 체스 같은 게임도 해당되지 않는다. 각자 자신의 돌(흑/백), 말(킹, 퀸, 비숍...)만 움직일 수 있으니 할 수 있는 행동이 다르기 때문이다. 다시 조건을 해석해보면 선공/후공만 다를 뿐 이를 제외한 조건은 모두 같은 게임을 칭한다. 빡빡한 조건으로 이런저런 게임들이 다 해당되지 .. 2019. 10. 18. 중국인의 나머지 정리(Chinese remainder theorem) 중국인의 나머지 정리를 이해하기 위해 기초적인 문제를 차근차근 풀어보자. 아래 문제만 풀 수 있다면 한결 가까워질 것이다. 문제 [아이] 할아버지, 나이가 어떻게 되십니까? [할아버지] 내 나이는 3으로 나누었을 때 1이 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는단다. [아이] ;; 풀이과정 할아버지의 말씀 3가지를 수식으로 바꿔보면 다음과 같다. $ x \equiv 1\ (mod\ 3) $ $ x \equiv 3\ (mod\ 5) $ $x \equiv 2\ (mod\ 7)$ 위 세 개를 만족하는 $x$를 구해보자. 우선 첫 번째 수식 $x \equiv 1\ (mod\ 3)$만 놓고 보면 간단하다. $$x = 3n + 1$$ 두 번째 수식 $x \equiv 3\ (mod\ 5)$을.. 2019. 10. 18. 포함과 배제, 그리고 뫼비우스 함수 INTRO 적당히 꼼수를 써가면서 풀었는데 수학적으로 멋진 풀이를 가진 문제가 있어서 정리해본다. 제곱ㄴㄴ수 이 문제인데 풀 때는 몰랐지만 따로 공부한 후 다시 봤더니 포함과 배제, 더 나아가 뫼비우스 함수까지 개념을 접할 수 있는 아주 좋은 문제다. 이 문제를 풀어가는 과정에서 이 개념들을 접하면 더 이해하기도 쉬울 것 같다. 문제 해결 구간 내에서 square-free의 개수를 구하는 문제이다. square-free 수란 소인수 분해를 했을 때 제곱 인수가 없는 수를 뜻한다. f(n) = 1부터 n까지의 수 중에서 square free 한 수의 개수 위와 같이 f(n)을 정의하면 f(max) - f(min - 1) 을 출력하면 된다. 그럼 f(n)과 친해지기 위해 바로 식을 세우기 전에 손으로 직접 .. 2019. 10. 18. 투셋(2-sat) 2-SAT 문제를 해결하기 앞서 먼저 용어 정리부터 필요하다. CNF (Conjunctive Normal Form) $(x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_1 \vee x_3) \wedge (x_2 \vee \neg x_3 \vee x_4)$... $\vee$로 이루어진 절이 최대 k개이면 k-CNF 모든 k-CNF 는 3-CNF로 변형 가능 k-SAT(k-satisfiability problem) k-SAT 문제는 $\vee$(OR)로 이루어진 k개의 논리 변수가 $\wedge$(AND) 로 묶인 논리식을 만족(True)시키는 조합을 찾는 문제이다. k-SAT은 3-SAT으로 변형 가능하기 때문에 3-SAT과 2-SAT만 의미가 있음 3-SAT은 NP-compl.. 2019. 10. 18. Manacher's Algorithm Palindrome 문자열이 있을 때 뒤집어도 같은 문자열이라면 이 문자열을 회문(palindrome)이라고 부른다. 예를 들어, "mom", "tattarrattat", "IOI" 등이 있다. 문자열이 palindrome인지 확인하는 방법은 최소 한 번은 스캔해야 하기 때문에 $O(n)$의 시간 복잡도를 가진다. 부분 문자열의 palindrome 그러면 어떤 문자열이 있을 때 palindrome을 만족하는 부분 문자열도 있을 것이다. 한 글자만 놓고 보면 길이가 1인 palindrome을 만족할 테니, 의미 있게 임의의 위치를 중심으로 만들 수 있는 가장 긴 palindrome을 생각해보자. 처음 생각나는 방법은 무식하게 전부 해보는 방법이다. 길이가 1인 palindrome이 있는지 확인하고, 있다면.. 2019. 10. 17. 고속 푸리에 변환(FFT, Fast Fourier Transform) 이전 글(푸리에 변환)에서 이산 푸리에 변환(DFT)과 역변환(IDFT), 그리고 그 이점에 대해서 정리했었다. 다른 분야에서도 널리 쓰이겠지만 PS에서 그 용도만 다시 정리해보면 어떤 수열들에 대해 복잡한 연산(예를 들어 convolution)을 할 때, DFT로 변환 후 연산을 하고 IDFT로 역변환을 해서 결괏값을 얻을 때 사용한다. 한 번에 할 것을 세 번(DFT, 연산, IDFT)에 하기 때문에 비효율처럼 보이지만 복잡한 연산이 변환 후 수열에서는 간단한 연산으로 바꿀 수 있어서 훨씬 효율적이다. 어떻게 간단한 연산으로 대체되는지는 이전 글에서 확인 가능하고, 이번 글에서는 변환/역변환을 빠르게 하는 방법을 알아보자. Discrete Fourier Transform (DFT) $ a_{n} $의.. 2019. 10. 17. 이전 1 2 3 다음
