Coursera 에서 제공하는 Princeton 대학교의 Algorithm 수업인 Algorithm Part 1 의 8 번째 수업입니다. Data Compression 주된 이유는 전송 시간과 저장 공간을 절약하기 위해서다. 무어의 법칙이 말해주듯이 제품의 성능은 점점 좋아지는데, 그럼에도 불구하고 사람들이 만들어 내는 데이터의 양은 더 급격히 증가한다. 그래서 압축이 필요하다. 이번시간에 배울 기법은 3 가지다. Run-length Huffman LZW data compression 응용은 … Continue reading Algorithm 8 – Data Compression, Huffman, LZW →

Coursera 에서 제공하는 Princeton 대학교의 Algorithm 수업인 Algorithm Part 1 의 7 번째 수업입니다. Min Cut edge weighted 그래프에서 st-cut 이란 vertices 를 두개의 disjont sets 으로 나누는 것이다. 이때 s, t 는 각각 다른 집합 A, B 에 속해있다. (http://en.wikipedia.org) capacity 란 컷으로 나뉘어진 두 집합 A, B 를 기준으로 A 에서 B 로 … Continue reading Algorithm 7 – Maximum Flow (Ford-Fulkerson) →

Coursera 에서 제공하는 Princeton 대학교의 Algorithm 수업인 Algorithm Part 1 의 6 번째 수업입니다. Intro to Substring Search N 길이의 텍스트에서 M 길이의 패턴을 찾는 문제다. 일반적으로 N >> M 이다. N 이 좀 많이 (무한히) 길기 때문에 지난시간까지 배운 알고리즘을 적용하기가 좀 힘들다. (1) suffix sort 를 쓰려고 보니 suffixes 를 만드는 것 자체가 … Continue reading Algorithm 6 – KMP, Boyer-Moore, Rabin-Karp →

Coursera 에서 제공하는 Princeton 대학교의 Algorithm 수업인 Algorithm Part 1 의 5 번째 수업입니다. String Symbol Table 지난 시간에 symbol-table 의 구현으로 red-black tree, hash table 의 성능을 살펴봤었다. red black tree 는 search, insertion, delete 에 compareTo 를 이용해 log N, hash table 은 equals, hashCode 를 이용해 1 (under uniform hashing assumption) 의 … Continue reading Algorithm 5 – R-way, Ternary Tries →

Coursera 에서 제공하는 Princeton 대학교의 Algorithm 수업인 Algorithm Part 1 의 4 번째 수업입니다. Strings in Java 문자열은 Character (문자) 의 나열이다. C 에서 하나의 캐릭터는 8-bit 인데, 자바의 경우에는 16-bit unsigned integer 로 표시한다. 스트링의 길이를 얻기 위해 length, 인덱싱 하기 위해 charAt, 서브스트링을 얻기 위해 substring 의 메소드를 지원한다. public final class String … Continue reading Algorithm 4 – Radix Sort, Suffix Sort →