오늘의 포스팅 내용은 깊이우선탐색(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에서 설명해주고 이것..
오늘도 저번에 이어서 Effective Java 2/E 의 내용중 일부를 포스팅 한다. 역시나 책에 나온 내용을 바탕으로 내가 이해한 대로 다시 포스팅 하는거라서 저자가 의도한 것과는 다른내용이 있을수도 있다a 책의 내용이 궁금한 사람들은 직접 구입해서 읽어보면 좋을꺼 같다.ㅎ 오늘의 포스팅 내용은 "불필요한 객체는 만들지 말라." 이다. 처음에 이 제목을 보고 '당연한 소리를 하고있어..' 라고 생각했다. 그런데 책에는 크게 신경쓰지않고 제작한 코드에서 불필요한 객체가 생기고 그것이 프로그램의 속도에 영향을 준다는것을 강조하고 있었다. 그러한 실수의 예를 보면 다음과 같다. 다음과 같은 코드에서 isBabyBoomer() 함수가 문제이다. 사용자의 생일 정보와 BabyBoomer 에 태어난 사람인지 아..
요즘 Effective Java 2/E 라는 책을 구입하고 읽고있다. 읽어보면서 다른사람들과 공유하면 좋겠다라는 내용들이 있어서 생각날때마다 하나씩 포스팅 하려고 한다. 책에 나온 내용을 바탕으로 내가 이해한 대로 다시 포스팅 하는거라서 저자가 의도한 것과는 다른내용이 있을수도 있다a 책의 내용이 궁금한 사람들은 직접 구입해서 읽어보면 좋을꺼 같다.ㅎ 오늘의 포스팅 내용은 Builder 패턴이라는 것이다. Builder 패턴은 다음과 같은 모양의 패턴이다. 그렇다면 이러한 Builder 패턴은 어떠한 상황에서 쓰면 좋을까?? 책에서는 Builder 패턴을 다음과 같은 상황에서 쓰라고 추천한다. 상황. 만약 당신이 만드는 클래스 중에 생성자 인자가 많은 클래스가 있다면 생성자대신에 Builder 패턴을 사..
책을보다보니 자바의 리플렉션이라는 주제에 대해서 나왔다. 리플렉션이 뭔가 했더니 JVM에 인스턴스된 객체를 통해서 객체의 원래 클래스가 무엇인지, 어떤 메소드와 변수들을 제공하는지 등 클래스의 정보를 확인할수 있는 방법입니다. 우리가 애용하는 자동완성 기능이 이 방법을 이용해서 제공되는거라고 하더군요...! 또 한 알아낸 메소드나 클래스 변수를 이용하여 실행 또는 수정까지 할 수 있습니다. 책에서는 리플렉션을 통해서 얻을수 있는 정보는 다음과 같다고 설명해줍니다.1.클래스 이름2.클래스의 제어자3.패키지의 정보4.클래스의 부모 클래스5.클래스의 생성자6.클래스의 메소드7. 클래스의 변수8. 클래스의 Annotation 이중에서 우리는 생성자,메소드,변수만을 다뤄볼것입니다. 우선 다음과 같은 클래스가 있다..
이번에는 자바 멀티스레드 환경에서 동기화하는 법에 대해서 알아보겠다. 예전에 C++ 환경에서 멀티스레드 동기화 자료가 있으니 필요하신분들은 그쪽을 확인하시면 되겠다. 우선 동기화가 필요한 이유는 N개의 스레드가 공통자원을 사용할때 문제가 생기기 때문이다. 다음과 같은 코드가 있다고 할때 양쪽 스레드에서 res를 10000번 ++ 증가 시키기 때문에 2개의 쓰레드의 합으로 결과가 20000이 나올것이라 예상했다. 하지만 결과를 보면 우리의 예상과는 다르다. 이러한 값이 나오는 이유는 예를들어 th1이 res가 100인 값을 증가하려고 할 때 동시에 th2도 res 변수를 증가시키려고 할때가 있다. 그러면 사실 두 개의 스레드가 증가시켰으니 102가 되어야 하지만 th1과 th2가 동시에 res변수에 접근했..
앞에 포스팅에서 봤겠지만 MainThread가 종료됬다고해서 그 안에서 동작하던 Thread들은 종료되지 않는다.(http://idea-sketch.tistory.com/admin/entry/post/?id=17) 그래서 이번에는 MainThread가 종료될때 같이 종료되는 Thread를 만들어보자. 방법은 아주아주 * 100 간단하다!! 바로 setDaemon() 을 true로 설정하면 끝! 다음은 예제 코드이다. 실행결과이다. MainThread가 종료되고 난후 더이성 is Running...이 뜨지 않는다. 즉 그 안에서 동작중이던 Thread도 같이 종료되었다~ 누군가에게는 작은도움이 되었기를 바라면서 오늘의 포스팅 끝~
- Total
- Today
- Yesterday
- next key lock
- MySQL 인덱스
- lock
- Elasticsearch Cluster
- innoDB lock
- 페어 프로그래밍
- 엘라스틱서치 기초
- MySQL
- ruby meta programming
- Pair-programming
- 루비 메타프로그래밍
- metaprogramming
- gap lock
- 페어프로그래밍
- mysql lock
- MySQL 족보
- ruby
- 넥스트 키 락
- 되추적
- 루비 상수
- Autoloading
- InnoDB
- 메타프로그래밍
- dead lock
- autoload_paths
- 갭 락
- db
- 트랜잭션
- 루비
- 인덱스
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |