본문 바로가기

Bioinformatics/Algorithms34

2차원 MXN 격자에 있는경로의 개수 계산하기 가령 M개의 행과 N개의 열을 가진 격자(grid)를 생각해 보자.이것은 조합을 계산하면 된다.(M+N)C(M) 또는 (M+N)C(N)이 동일한 값을 결과로 도출하게 된다. 이것은 먼저 A가 시작점(왼쪽 상단), B(가 오른쪽 하단)이라고 가정했을 때, A에서 B로 가는 경로는 오른쪽 방향으로 가는 경로는 N만큼 있고, 아래쪽으로 가는 방향으로 가는 경로는 M만큼 있기 때문에 총 경로 개수는 M+N이 있고, 이중에서 중복을 허용하지 않고, 순서는 중요하지 않은 조합을 계산하면 되는 것이다. 조합은 다음과 같이 계산한다. 여기에서 n은 조합을 계산할 대상이 되는 개체의 수를 나타내고, r은 몇 개의 객체를 선택할지를 나타낸다. 가령 16X12의 조합을 계산할 때는, 28C12가 되고 이것을 계산하면, 30.. 2013. 12. 19.
커널 함수와 지지 벡터 머신(SVM) 본 내용은 http://www.quora.com/Machine-Learning/What-are-Kernels-in-Machine-Learning-and-SVM의 답변 중 가장 좋다고 생각한 몇 가지의 답변을 선택하여 번역했다. 니킬 가그(Nikil Garg)의 답변 이것은 단순하고, 이해하기 쉬운, 수학으로 설명된 내용이 적은 지지 벡터 머신(SVM, supporting vector machine)과 커널 함수에 대한 설명이다. 자, 지지 벡터 머신이란 무엇인가? 지지 벡터 머신은 분류(classification) 문제를 해결하는데 도움을 주는 기술이다. 지지 벡터 머신을 이해하기 위해서, 먼저 우리는 실제로 분류 문제가 무엇인지 알 필요가 있다. 분류 문제: 일반적인 분류 문제의 상황에서, 우리는 어떤.. 2013. 5. 8.
해시 테이블, 열린 주소 방식 본 내용은 http://www.algolist.net/Data_structures/Hash_table의 내용을 편역한 것이다. 해시 테이블 해시 테이블(혹은 해시 맵)은 사전 ADT(추상 자료 구조)의 가능한 구현 중 하나이다. 그렇기 때문에, 기본적으로 그것은 유일한 키를 연관된 값에 사상한다. 구현 관점에서, 해시 테이블은 배열 기반의 자료 구조이고, 해시 함수를 이용해서 키를 연관된 값이 검색되어지는 배열 요소의 색인 값으로 변경하는데 해시 함수를 이용한다. 해시 함수 해시 함수는 해시 테이블 설계의 매우 중요한 함수이다. 해시 함수는 해시 값들이 균등하게 분포될 때 좋다고 여겨진다. 해싱의 품질을 위해 요구되는 다른 해시 함수의 특성은 차후에 살펴보겠다. 우리가 해시 함수에 주요한 관심을 가지는 .. 2013. 5. 3.
[간략]은닉 마르코프 모델(Hidden Markov Model)과 비터비(Viterbi) 알고리즘의 생물학 이용 최근에 여러 가지 자료 구조와 알고리즘을 보다가 은닉 마르코프 모델과 비터비 알고리즘을 보게 되었다. 이런 알고리즘을 왜 사용하는 걸까? 라는 고민에 이것 저것 찾아 보다가 정리를 할 수 있게 되어 간략하게 적게 되었다. 가령 생물 정보학에서 자주 다루게 되는 DNA 염기서열이 다음과 생성(output)이 되었다고 하자. s = "ATCGATCGTTTCATTAGTATTCATGCT" 이 서열에는 총 4가지 문자가 사용되었다. 그렇다면, 이런 서열을 생성하는 동안 각 순간에 염기 변이 확률 같은 것이 있지 않을까? 확률로써 염기의 전이들을 표현하고 싶다면, 그에 합당한 모델이 있어야 한다. 이 때 우리는 은닉 마르코프 모델(HMM)을 사용할 수 있다. 예를 들어, 우리는 다음과 같이 은닉 마르코프 모델을 정.. 2013. 4. 3.