전체 글110 투셋(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 ··· 29 30 31 32 33 34 35 ··· 37 다음
