이번 거 너무 대충 썼다.. 그냥 안 쓰려다가 이미 절반이나 써버려서 그냥 빠르게 머릿속 버퍼에 채우고 버릴 겸 포스팅  📕 목차1. Introduction2. Run-length 코딩3. Huffman 압축4. LZW 압축1. Introduction 📌 무손실 압축과 복원메시지: 압축하고자 하는 데이터 B압축: B를 압축한 결과 C(B)를 생성복원: D(C(B)) == B가 되도록 재구성압축률(compression ratio) = C(B)의 크기 / B의 크기텍스트 문서의 경우 50~75% 이상의 압축률 📌 압축의 예시 : 유전자 코드유전자 코드 {A, C, T, G} 4개의 알파벳으로 구성표현 방법ASCII 코드로 각 알파벳을 표현할 경우: 문자당 8-bit 소요Two-bit 인코딩: 문자당 2..

📕 목차1. Regular Expressions (RE)2. Nondeterministic Finite-state Automata (NFA)3. NFA를 이용하여 문자열 인식4. RE로부터 NFA 작성1. Regular Expressions (RE) 📌 패턴 매칭 (Pattern Matching)문자열 매칭: Text에서 하나의 pattern 문자열을 발견하는 것이 목적패턴 매칭: 특정 조건을 만족하는 문자열의 집합 중에 한 가지라도 Text에 나타나는가? 예를 들어, 유전 공학의 DNA 염기 서열을 생각해보자.사람의 유전자는 알파벳 A, C, T, G로 표현하며, GCG로 시작해서 CTG로 끝나며, 중간에 CGG나 AGG가 여러 번 나오는 패턴을 검색하려 한다.text로 "GCGGCGTGTGTGCG..

📕 목차1. Introduction2. Brute-force 알고리즘3. KMP(Knuth-Morris-Pratt) 알고리즘4. Boyer-Moore 알고리즘5. Rabin-Karp 알고리즘1. Introduction 📌 문자열 매칭 문제patternNEED    textINSTNEED길이가 n인 문자열(text)에서 길이가 M인 문자열(pattern)이 존재하는 지 검사하는 알고리즘보통 N >> M 인 경우가 많다. 2. Brute-force 알고리즘 📌 아이디어전탐색 알고리즘답게 패턴을 하나하나 대보고 비교하는 방법!매우 심플하지만, 딱 봐도 느려터졌다. 📌 구현public class BruteForce { public static int search(String txt, String p..

📕 목차1. String Simbol Table2. 트라이(Tries)3. 삼진 검색 트라이(Ternary Search Tries: TST)1. String Simbol Table • 심볼 테이블• String 심볼 테이블• 심볼 테이블 성능 📌 심볼 테이블(key, value) 쌍을 저장하는 데이터 구조특정 키와 해당 키에 해당되는 값의 쌍을 삽입key를 검색어로 제공하면, 이에 대응하는 value를 빠르게 찾아주는 구조고려 사항Generics을 지원해야 한다. (단, 키는 Comparable 인터페이스를 구현할 )중복 키는 허용하지 않는다.키와 값은 null이 될 수 없다.테이블에서 {k1, v1}을 제거하는 경우, k1을 검색해서 삭제하거나 {k1, null}을 고려해볼 수 있음 🟡 Simbo..