프로그래밍/알고리즘

외판원 순회 문제외판원 순회 문제란 도시들과 도시 간 이동 비용이 주어졌을 때, 외판원이 각 도시를 한 번씩 방문하고 출발한 도시로 돌아오는 최소 비용을 구하는 문제이다. 외판원 순회 문제는 아직 다항 시간 내에 해결할 수 있는 알고리즘이 발견되지 않았다.브루트포싱으로는 무려 $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 |$를 해주어..

트라이란?트라이(Trie)란 주로 문자열을 효율적으로 저장, 탐색하기 위한 트리 형태의 자료 구조를 의미한다.트라이는 문자열의 맨 앞 문자부터 계층적으로 저장하고 있다.위 그림에서 'tea'를 찾으려면 순서대로 't', 'te', 'tea'로 찾아 내려오면 된다.이처럼 트라이에서 찾으려는 문자열의 길이가 $m$일 때, $O(m)$의 시간 만에 원하는 문자열을 찾을 수 있다. 구현해보기삽입'tax'라는 문자열을 삽입해보자.root의 자식 중 't'가 있으므로 해당 노드로 이동한다.'t'의 자식 중 'a'('ta')가 없으므로 해당 노드를 생성 후 이동한다.'a'의 자식 중 'x'('tax')가 없으므로 해당 노드를 생성 후 이동한다.해당 구조를 코드로 작성하면 아래와 같다.class Node: def..