Study
-
[Data Structure] 자료구조 - ArrayStudy/Data Structure 2020. 9. 21. 23:47
1. Introduction to Arrays Array는 item들의 collection이 메모리에 연이은 위치에저장된다. 여러 같은 type의 여러 item을 같이 저장하는 것이다. 기본 값에 offset을 추가하여 각 요소의 위치를 쉽게 계산할 수 있다. 더보기 offset: 기준이 되는 주소에 더해지는 값 각 element는 array의 index로 식별할 수 있다. Array의 장점 1. Array에서는 element의 random access가 된다. 이 말은 위치로 element에 접근하는 것이 빠르다는 것이다. 2. Array는 성능에 큰 차이를 만들 수 있는 더 나은 캐시 locality를 가지고 있다. 더보기 locality: 기억 장치 내의 정보를 균일하게 접근하는 것이 아닌 어느 한..
-
[Algorithm] 알고리즘 - 문자열 매칭(Pattern Matching)Study/Algorithm 2020. 8. 27. 19:00
문자열 매칭 또는 패턴 매칭은 컴퓨터 과학에서 중요한 문제이다. 노트패드나 워드파일 또는 웹 브라우저 데이터베이스에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다. 문자열 매칭 방법의 종류는 아래와 같다. 1. Naive Matching (원시적인 매칭) - $O(mn)$ 2. Automata Algorithm (오토마타를 이용한 매칭) - $\Theta(n + |\sum| m)$ 3. Rabin-Karp Algorithm (라빈-카프 알고리즘) - $\Theta(n)$ 4. Knuth-Morris-Pratt(KMP) Algorithm (KMP알고리즘) - $\Theta(n)$ 5. Boyer-Moore Algorithm (보이어-무어 알고리즘) - $\Theta(n)$ Wor..
-
구현을 통한 Bloom Filter 알아보기 with Python3Study/Data Structure 2020. 6. 11. 22:39
Bloom Filter를 구현하기에 앞서 Bloom Filter의 정의를 보겠습니다. 위키피디아에 따르면 "Bloom Filter는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료구조이다. Bloom Filter의 핵심은 바로 '확률적 자료구조'라는데 있습니다. '블룸 필터에 의해 어떤 원소가 집합에 속한다고 판단된 경우 실제로는 원소가 집합에 속하지 않는 긍정 오류가 발생하는 것이 가능하지만, 반대로 원소가 집합에 속하지 않는 것으로 판단되었는데 실제로는 원소가 집합에 속하는 부정 오류는 절대로 발생하지 않는다는 특성이 있다'라고 합니다. 예를 들어 원소 'dog'이 집합에 속한다고 알려주지만 실제로는 'dog'이 집합의 원소가 아닐 수 있다는 것 입니다. 그리고 'cat'이라는 원소가 ..
-
Trie 자료구조Study/Data Structure 2020. 6. 11. 19:21
https://en.wikipedia.org/wiki/Trie를 참고하면 digital tree 또는 prefix tree라고 하는 trie는 일종의 검색 트리입니다. 동적인 set을 저장하거나 연관있는 배열을 저장할 때 쓰입니다. key는 일반적으로 문자열을 저장합니다. binary search tree와는 다르게 노드는 관련된 키를 저장하지 않습니다. 대신 트리의 위치가 키를 정의하는 방식입니다. 그래서 키는 트리 구조 전체에 분산되어 있습니다. 노드의 모든 하위 항목에는 해당 노드와 연관된 문자열의 공통 접두사가 있습니다. 루트는 빈문자열과 연관되어 있습니다. 위 그림과 같이 "te"의 하위 항목인 "tea", "ted", "ten"은 "te"라는 공통 접두사가 있다고 보시면 됩니다. 아래는 위키피..
-
머신러닝을 위한 Probability and Distribution 알아보기Study/통계 2020. 5. 29. 19:56
Probability 확률이라는 하는 것이 결국 MAP, MLE를 통해 알아본 근간이기 때문에 확률에 대해서 알아 볼 필요가 있습니다. $\Omega$라는 세상의 모든 사건들 중에 $E_1$이라는 사건과 $E_2$라는 사건이 발생한다고 가정을 한다면 이렇게 $E_1$과 $E_2$가 발생할 수 있는 확률이라는 것이 무엇인지 정의 해보는 것 입니다. 그것을 다음과 같이 정의해보겠습니다. $P(E) \in R $ 함수 모양을 하고 있는데 함수의 인자로 E(Event)가 들어가는 것 입니다. 함수에 E를 넣었더니 그 결과값은 R이라고 하는 continuous value가 나오고 그 값은 $P(E) \geq 0 $ 이라는 것 입니다. 그리고 또 다른 제약 조건이 있는데 $\Omega$라는 이 세상의 삼라만상 모든..
-
MLE(Maxinum Likelihood Estimation)에 대한 이해Study/통계 2020. 5. 28. 19:09
위키피디아에 MLE의 정의를 보면 '어떤 확률변수에서표집한 값들을 토대로 그 확률변수의모수를 구하는 방법, 어떤 모수가 주어졌을 때, 원하는 값들이 나올가능도를 최대로 만드는 모수를 선택하는 방법'이라 합니다. 어느정도 이해한 지금의 상황에선 위의 뜻이 좋은 설명이라고 생각하지만 처음 MLE를 접했을 때 잘 이해되지 않는 부분이 있었습니다. 이해를 위해 나름대로 기록한 내용을 적어 보려고 합니다. Thumbtack Question 압정은 동전과를 모양이 다르기 때문에 쉽게 50:50 확률이라고 보기 힘듭니다. 실제로 압정을 던져서 앞이 3번 뒤가 2번 나왔으니 3/5, 2/5의 확률이라고 대답하기엔 부족한 점이 있습니다. Binomial Distribution Binomial Distribution은 이..
-
MAP - Maximum a Posteriori 최대 사후 확률Study/통계 2020. 5. 7. 12:06
MLE(Maximum Likelihood Estimation)는 주어진 관측결과의 발생 가능성을 가장 높게 만들어 주는 모수를 찾아냈습니다. MAP는 MLE와 전혀 다른 개념을 가지고 있는데 MAP는 주어진 관측결과와 '사전지식(사전확률)'을 결합해서 최적의 모수를 찾아내는 방법입니다. 어떤 모수 $\theta$의 사전 확률 분포가 $p(\theta)$로 주어져 있고, 그 모수에 기반한 조건부 확률분포 $f(x|\theta)$와 그 분포에서 수집된 값 $x$가 주어져 있습니다. 이떄 모수의 사후 확률분포는 베이즈 정리에 의해 다음과 같이 계산할 수 있습니다. 여기서 x가 주어져 있기 때문에 분모는 $\theta$에 대해 상수가 됩니다. 여기에서 최대 사후 확률 모수는 다음과 같이 정의됩니다. 최대 사후 ..