오늘의 주제는 되추적(Backtracking) 이다. 저번 포스팅인 깊이우선탐색(Depth-First Search)과 넓이우선탐색(Breath-First Search)의 몸풀기를 거치고최단경로(Shortest Path) 알고리즘에 들어가는 첫 걸음이라고 생각하고 가벼운 마음으로 읽어보면 되겠다. 우선 되추적(Backtracking)이 뭔지부터 알아보자.『 퇴각검색(영어: backtracking, 한글: 백트래킹)은 한정 조건을 가진 문제를 풀려는 전략이다. "퇴각검색(backtrack)"이란 용어는 1950년대의 미국 수학자 D. H. 레머가 지었다. 문제가 한정 조건을 가진 경우 원소의 순서는 해결 방법과 무관하다. 이런 문제는 변수 집합으로 이뤄지는데, 한정 조건을 구성하려면 각각의 변수들은 값이 있..
오늘의 포스팅 내용은 저번의 깊이우선탐색(Depth-First Search)에 이어서 너비우선탐색(Breadth-First Search)이다. 깊이우선탐색(DFS)와는 다르게 너비우선탐색(BFS)은 큐를 사용한다. 이번에도 역시 다음과 같은 상황이 있다고 해보자. 이 상황에서 L을 찾아줘! 라는 요구사항이 있다면 답을 찾기위해 BFS는 어떻게 동작할까? 너비우선탐색의 정의는 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 라고 위키백과에 써있다. 너비우선탐색은 노드를 선택하고 추가하는 과정에서 큐을 사용한다. 그리고 너비우선탐색 이라는 말..
오늘의 포스팅 내용은 깊이우선탐색(Depth-First Search)과 너비우선탐색(Breadth-First Search)이다. 최단경로(Shortest Path) 알고리즘에 들어가기전에 몸풀기라고 생각하시고 가벼운 마음으로 읽어보면 될꺼 같다. 우선 깊이우선탐색(DFS)의 경우 스택을 너비우선탐색(BFS)은 큐를 사용한다. 우선 이런 탐색방법을 왜 하는지부터 알아보자. 다음과 같은 상황이 있다고 해보자. 이 상황에서 L을 찾아줘! 와 같이 정렬이 되지 않은 트리 혹은 그래프와 같은 자료구조에서 어떠한 특정 조건을 만족하는 상황을 찾는데 사용된다. 그렇다면 이러한 상황에서 길을 찾기위해 DFS와 BFS는 어떻게 동작할까? 우선 깊이우선탐색부터 알아보자. 깊이 우선탐색의 정의는 맹목적 탐색방법의 하나로 탐..
오늘의 포스팅 내용은 이진탐색트리(BST) 입니다! 우선 이진탐색트리에 대한 설명에 앞서 트리에 대해서 짧게 설명하고 지나가겠습니다. " 트리 구조란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. 트리에서 최상위 노드를 루트 노드(root node 뿌리 노드)라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드)라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다. " 고 위키피디아에 나와있습니다.ㅎ 그리..
오늘의 포스팅은 특정문자열에서 반복적으로 나타나는 부분문자열을 찾는 방법입니다. 우선 여기서 말하는 반복부분문자열이란 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분문자열을 '반복 부분문자열'이라고 부르겠습니다. 예를들어 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
- ruby
- Elasticsearch Cluster
- metaprogramming
- 되추적
- 페어 프로그래밍
- innoDB lock
- 갭 락
- MySQL 족보
- 루비
- 루비 메타프로그래밍
- Autoloading
- db
- 인덱스
- mysql lock
- 넥스트 키 락
- 루비 상수
- Pair-programming
- dead lock
- ruby meta programming
- gap lock
- 트랜잭션
- lock
- next key lock
- autoload_paths
- 메타프로그래밍
- MySQL 인덱스
- 페어프로그래밍
- InnoDB
- MySQL
- 엘라스틱서치 기초
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |