Coding Test

📕 목차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..

📕 목차1. 자바의 String 사전 지식2. LSD(Least Significant Digit)3. MSD(Most Significant Digit)4. Three-way String Quicksort1. 자바의 String 사전 지식 • char 데이터 타입 (feat. Character)• String 데이터 타입• StringBuilder• 두 개의 문자열 비교• Alphabet• 문자열 정렬 알고리즘 필요성 📌 char 데이터 타입 (feat. Character)C언어를 공부할 때는 char 타입이 8-bit(1byte)였는데, 자바에서는 16-bit(2byte)의 크기를 갖는다.이는 제공하는 문자 체계가 다르기 때문이다.C: 7-bit의 ASCII 코드 지원Java: 16-bit의 Unic..