이번 글에서는, divide-and-conquer 기법을 활용한 유명 알고리즘에 대해 살펴볼 것이다. 1. Quicksort Problem 정렬 문제다. 즉, 크기가 n인 배열(=S)을 정렬하는 문제다. Algorithm pivot item(=S[0])으로 배열 S를 partition(=분할)한다. pivot item보다 작으면 pivot 왼쪽으로 이동 pivot item보다 크면 pivot 오른쪽으로 이동 분할된 2개 부분 배열을 각각 정렬한다. (만약, 부분 배열을 더 분할할 수 있다면, 재귀를 통해 정렬한다.) 정렬된 부분 배열 2개와 pivot item을 연결시켜, original 배열을 정렬한다. Analysis base operation: pivot item과 S[i]간의 비교 연산 input..

이번 글에서는, 알고리즘 설계 시 사용되는 접근법들 중 하나인 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..