이번 글에서는, 알고리즘 설계 시 사용되는 접근법들 중 하나인 divide-and-conquer에 대해 살펴볼 것이다. Divide-and-Conquer Definition divide-and-conquer는 instance를 작은 instance(s)로 쪼개 푼 것을 기반으로, original instance를 푼다. Approach divide-and-conquer 알고리즘은 다음 3단계 절차를 기반으로 설계돼야 한다. (문제의) instance를 (같은 문제의) 작은 instance(s)로 쪼갠다.(즉, 정렬 instance를 작은 정렬 instance로 쪼갠다.) 작은 instance(s)를 푼다. (이때, 작은 instance를 더 쪼갤 수 있다면, 재귀를 통해 푼다.) 작은 instance(s..

이번 파트에서는 (문제 풀이) 기술들(=techniques)에 대해 살펴볼 것이다. (문제 풀이) 기술이란, 컴퓨터로 문제를 풀 때 사용되는 접근법(=approach) 혹은 방법론(=methodology)을 의미한다. (e.g., divide-and-conquer, dynamic programming, greedy approach) 용어 정리 specific task 혹은 question을 problem(=문제)라고 한다. (e.g., 정렬, 최단 경로) 문제 설명글에 값이 정해지지 않은 변수가 나올 수 있으며, 이를 parameters (to the question)라고 한다. 문제 parameters에 특정 값을 할당하여, 구체화된 문제를 instance (of the problem)라고 한다. in..

이번 글에서 reduction과 그로 인해 얻을 수 있는 3가지 요소에 대해 살펴볼 것이다. 1. Algorithm design Definition Problem $X$ reduces to problem $Y$, if you can use an algorithm that solves $Y$ to help solve $X$. Cost of solving $X$ = total cost of solving $Y$ + cost of reduction(=preprocessing and postprocessing) 정렬 알고리즘을 통해 중앙값 알고리즘을 얻을 수 있던 것처럼, reduction은 "기존 문제의 알고리즘으로 다른 문제의 알고리즘 설계에 도움을 주는 개념"이다. 때문에, 새로운 문제를 만났을 때, 새로..

데이터 압축은 파일의 크기를 줄임으로써, 저장 공간이 작아질 뿐만, 전송 시간이 빨라지는 효과를 줄 수 있다. 이번 글에서는, lossless compression(=무손실 압축)만 다룰 것이다. 즉, 데이터 손실 없이 데이터를 압축하는 방법에 대해서만 살펴볼 것이다. (데이터 압축 평가 시, 입축 비율(compression rate)일 사용할 것이다.) Universal data compression 모든 bitstring를 압축해주는 알고리즘은 존재하지 않는다. 더보기 Proof (by 귀류) 모든 1000-bitstring을 압축해주는 알고리즘이 있다고 가정하자. 그럼 $2^{1000}$개 bitstring을 최소 999 bits로 압축해야 한다. 하지만 999 bits는 $2^{999}$개만 존재..

이전 글에서는, "특정 문자열(one string)을 탐색하는 문제"에 대해 살펴봤다. (substring search) 본문에서는, "특정 문자열 집합(one of specified set of string)을 탐색하는 문제"에 대해 살펴볼 것이다. (pattern matching) 문자열 집합을 표현하는 대표적인 방법에는 정규표현식(=regular expression)이 있다. Regular expressions Definition Regular expressions is a notation to specify a set of strings. Operations operation order example RE matches concatenation 3 AABAAB AABAAB or 4 AA | BAA..

이번 글에서는, substring search에 대해 살펴볼 것이다. Substring search는 말뭉치(=corpus)에서 특정 문자열(=pattern)을 모두 찾는 문제다. (N >> M, N = length of corpus, M = length of pattern) 0. Burte-force algorithm corpus 맨 왼쪽 문자를 기준으로, pattern이 있는지 확인한다. 만약, pattern과 mismatch하면, 다음 문자(i=i+1)를 기준으로 pattern 여부를 확인한다. (by 재귀) 만약, pattern과 match하면, 문자 위치(i)를 반환한다. 위 알고리즘은 backup을 사용하기 때문에 매우 비효율적이다. (worst case $\sim MN$ char compar..