오늘의 포스팅은 특정문자열에서 반복적으로 나타나는 부분문자열을 찾는 방법입니다. 우선 여기서 말하는 반복부분문자열이란 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분문자열을 '반복 부분문자열'이라고 부르겠습니다. 예를들어 banana가 있을경우 반복부분 문자열은 an, na, ana 입니다. 머리로는 알겠지만 알고리즘으로는 이를 어떻게 알수 있을까요? 방법은 접미사배열(Suffix Array)을 사용하는겁니다. 우선 접미사배열이란 전산학에서 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다.(위키백과) 예를들어 banana가 있을경우 접미사배열은 다음과 같습니다. 다음과 같이 앞에서부터 한칸씩 나가면서 문자열을 잘라냅니다. 그리고 ..
오늘의 포스팅은 문자열검색 알고리즘인 라빈-카프 알고리즘입니다. 장문의 문자열 A가 있을때 문자열A 안에 특정 문자열B가 있는지 알수 있는 방법은 뭐가 있을까? 고민했을때 제일 간단한 방법은 찾고자 하는 문자열B의 첫글자가 있는곳을 문자열A에서 순차적으로 탐색해서 발견했을때 본격적으로 비교를 시작하는것입니다. 그러나 이방법은 제일 간단하고 무식한(?) 방법이지만 무식한(?)만큼 탐색하는데 비용이 많이듭니다. 그래서 이렇게 무식한(?) 방법 보다는 비용이 덜 들면서 빠르게 찾을수 있는 알고리즘인 카프-라빈 알고리즘을 설명하려고 합니다. 라빈-카프 알고리즘을 간단히 설명하자면 문자열을 수치로 변환시켜 탐색하는 알고리즘입니다. 알고리즘 공식은 다음과 같습니다. 장문의 문자열 A가 있을때 A[n]은 A문자열의 ..
오늘의 포스팅 내용은 유한상태기계(finite-state machine,FSM) 이다. 내가 FSM이라는 개념을 알게된 이유는 개발하는 게임의 AI 처리를 위해서였다. "어떻게하면 한 클래스가 상황에 따라 다른동작을하게 하고 쉽게 관리할수 있을까?"를 고민하다 GPG에서 발견한개념이 FSM이다. FSM에 대해 간단히 설명하자면 "FSM 이란 용어 그대로 유한한 상태들로 구성된 기계라고 보면 된다. 여기에서 상태란 하나의 조건이라고 생각하면 된다. 상태의 예를 들자면 문이 열림, 닫힘, 잠김 등이된다. FSM은 어떤 입력에 의해서 하나의 상태에서 다른 상태로 전이되는 식으로 동작한다. 그래서 FSM은 상태를 전이시키기위해 어떤상태로 바꿀지에대한 간단한 전이함수를 가진다." 라고 GPG에서 설명해주고 이것..
- Total
- Today
- Yesterday
- 루비 메타프로그래밍
- 넥스트 키 락
- Pair-programming
- innoDB lock
- gap lock
- mysql lock
- 되추적
- MySQL 족보
- 루비
- autoload_paths
- 페어프로그래밍
- MySQL
- metaprogramming
- MySQL 인덱스
- db
- dead lock
- Autoloading
- 루비 상수
- 메타프로그래밍
- 인덱스
- next key lock
- ruby
- ruby meta programming
- Elasticsearch Cluster
- 엘라스틱서치 기초
- lock
- 트랜잭션
- 갭 락
- 페어 프로그래밍
- InnoDB
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |