Coding Test

[Programmers] 퍼즐 조각 채우기 (Level 3)

1. 문제 설명  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr코테의 근본은 C++하지만 최근 기업 코테에서 C++을 받아주질 않는 추세다.이유가 뭔고 하니 C++로 해킹을 하는 사람들이 있다고......:(그것도 있고 기업 코테의 목적이 알고리즘 그 자체보단, 언어의 이해도를 측정하는 구현 능력에 초점을 맞추면서 겸사겸사 제한하는 것 같다. 덕분에 코테도 자바로 하는데, 손에 안 익어서 죽을 맛이다. 2. 아이디어 생각 이상으로 시간을 너무 잡아먹었다.3월 이후로 개발에 몰두한다고 코테 손 좀 놨더니 바로 폼 떨어져버림. 1️⃣ 블록 탐색일단 처음 보자마자..

[Algorithm] 데이터 압축(Data Compression)

이번 거 너무 대충 썼다.. 그냥 안 쓰려다가 이미 절반이나 써버려서 그냥 빠르게 머릿속 버퍼에 채우고 버릴 겸 포스팅  📕 목차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..

[Algorithm] 정규식(Regular Expressions)

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

[Algorithm] 문자열 매칭(Substring Search)

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