전체 글

1. 모듈로 연산이란?모듈로 연산이란 한 수를 다른 수로 나눈 나머지를 구하는 연산을 말한다.기호로는 $\bmod$를 써서 $A\bmod{B} = R$과 같이 나타낸다. 모듈로 연산은 덧셈, 뺄셈, 곱셈에 대해 분배 법칙이 적용된다.$$ (A \pm B) \bmod{C} = (A \bmod{C} \pm B \bmod{C}) \bmod{C} $$$$ (A \times B) \bmod{C} = (A \bmod{C} \times B \bmod{C}) \bmod{C} $$ 1-1. 모듈로 연산에서의 합동어떤 두 수 $A$와 $B$를 각각 $C$로 나눈 나머지가 같을 때, 이를 모듈로 합동이라고 한다.식으로 나타내면 $A = B + K * C\;(K \in \mathbb{Z})$이며, 간단하게 $A \equiv ..

외판원 순회 문제외판원 순회 문제란 도시들과 도시 간 이동 비용이 주어졌을 때, 외판원이 각 도시를 한 번씩 방문하고 출발한 도시로 돌아오는 최소 비용을 구하는 문제이다. 외판원 순회 문제는 아직 다항 시간 내에 해결할 수 있는 알고리즘이 발견되지 않았다.브루트포싱으로는 무려 $O(N!)$의 시간이 걸리며, 오늘 소개할 DP를 이용한 방법으로는 $O(N^22^N)$의 시간이 걸린다. 어떻게 해결할까?1. 완전 탐색 - $O(N!)$외판원이 도시를 방문하는 순서를 모두 구한 후, 최소 비용을 찾는 방법이다.이는 $N$개의 도시를 나열하는 모든 경우를 탐색하는 것으로 $O(N!)$의 시간이 걸린다. 2. 다이나믹 프로그래밍 - $O(N^22^N)$완전 탐색에서는 이미 계산한 경로의 최소 비용을 중복 계산하게..

LIS(최장 증가 부분 수열)이란?LIS란 말 그대로 어떤 수열의 부분 수열 중, 가장 긴 증가하는 부분 수열을 의미한다.예를 들어, {10, 20, 10, 30, 20, 50} 인 수열의 LIS는 {10, 20, 30, 50} 이고, 길이는 4이다. 어떻게 구할까?1. 완전 탐색 - $O(2^N)$모든 부분 수열을 구한 후, 증가하는 부분 수열 중 가장 긴 수열을 구하는 방법이다.말 그래도 모든 부분 수열을 구해야 하므로, $O(2^N)$의 시간이 걸린다. 2. 다이나믹 프로그래밍 - $O(N^2)$$A_i$을 마지막으로 가지는 가장 긴 증가하는 부분 수열의 길이를 $DP[i]$라고 해보자.각 원소별로, 해당 원소($i$)보다 앞선 원소들($j$)을 탐색한다.$A_i > A_j$인 원소들 중 $DP[j..

중간에서 만나기(Meet in the Middle)이란?중간에서 만나기란 완전 탐색에 시간이 오래 걸리는 경우 대상을 두 그룹으로 나누어 탐색하여 시간을 단축하는 방법이다. 예를 들어, 크기가 $N$인 집합의 모든 부분 집합을 구하기 위해서는 $O(2^N)$의 시간이 걸린다.하지만 모든 부분 집합 중 특정 조건을 만족하는 경우를 찾기만 하면 된다면, 집합을 반으로 쪼개 각각 탐색하여 $O(2\times2^{N/2})$만에 해결할 수 있다. MITM 적용해보기백준 1208번 부분수열의 합 2 문제를 직접 풀어보자.수열의 부분수열 중 합이 $S$가 되는 경우의 수를 구하는 문제이다. 완전 탐색을 위해서는 앞에서 말했듯이 $2^{40} = 1,099,511,627,776$회의 연산이 필요한데, 이는 제한 시..

포함-배제의 원리란?포함-배제의 원리(Inclusion-Exclusion Principle)란 여러 집합들의 합집합의 크기를 구하는 데 사용하는 공식이다.포함-배제의 원리는 교집합의 크기로 합집합의 크기를 구하거나, 혹은 그 반대의 경우에 적용할 수 있다. 살펴보기두 집합의 합집합의 크기는 아래와 같은 공식으로 쉽게 구할 수 있다.$$ | A \cup B | = | A | + | B | - | A \cap B | $$ 집합의 개수를 하나만 더 늘려보자. 세 집합의 합집합의 크기는 어떻게 구할까?그림에서 볼 수 있듯이, $ | A | + | B | + | C | $를 하면 교집합 부분이 중복으로 더해진다.따라서 $ - | A \cap B | - | B \cap C | - | A \cap C | $를 해주어..