Algorithm(28)
-
[Algorithm Part 3] 1. Introduction
이번 파트에서는 (문제 풀이) 기술들(=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..
2023.07.06 -
[Algorithm Part 2] 11. Reduction
이번 글에서 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은 "기존 문제의 알고리즘으로 다른 문제의 알고리즘 설계에 도움을 주는 개념"이다. 때문에, 새로운 문제를 만났을 때, 새로..
2023.06.29 -
[Algorithm Part 2] 10. Data Compression
데이터 압축은 파일의 크기를 줄임으로써, 저장 공간이 작아질 뿐만, 전송 시간이 빨라지는 효과를 줄 수 있다. 이번 글에서는, lossless compression(=무손실 압축)만 다룰 것이다. 즉, 데이터 손실 없이 데이터를 압축하는 방법에 대해서만 살펴볼 것이다. (데이터 압축 평가 시, 입축 비율(compression rate)일 사용할 것이다.) Universal data compression 모든 bitstring를 압축해주는 알고리즘은 존재하지 않는다. 더보기 Proof (by 귀류) 모든 1000-bitstring을 압축해주는 알고리즘이 있다고 가정하자. 그럼 $2^{1000}$개 bitstring을 최소 999 bits로 압축해야 한다. 하지만 999 bits는 $2^{999}$개만 존재..
2023.06.27 -
[Algorithm Part 2] 9. Pattern Matching
이전 글에서는, "특정 문자열(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..
2023.06.22 -
[Algorithm Part 2] 8. Substring Search
이번 글에서는, 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..
2023.06.19 -
[Algorithm Part 2] 7. Tries
이번 글에서는, Tries에 대해 살펴볼 것이다. Tries는 문자열(=string) key에 특화된 symbol table이다. 문자열을 key로 둘 때, Tries는 기존 Balanced Search Tree 혹은 Hash Table보다 (문자열의 모든 문자 조사를 피함으로써,) 더 좋은 성능을 보인다. 1. R-way tries Representation 다음 조건을 만족하는 트리로 표현할 수 있다. 모든 노드는 value와 R개의 자식 노드를 가지고 있다. key(=문자열)는 root노드에서 해당 노드까지의 경로로 알 수 있다. 예를 들어, 경로가 115(ascii s) → 97(ascii e) → 101(ascii a)인 경우, 노드의 key는 "sea"다. 따라서, 따로 노드에 key를 저장할..
2023.06.17