최근접쌍 문제 평면상에 N개의 점들이 주어질 때, 가장 가까운 두 점을 찾아라. Brute force 알고리즘 Euclidean distance 이용하여 모든 두 점 쌍들 사이의 거리 구해 최솟값 발견 Brute force 알고리즘 –> O(n*n) 분할 정복 알고리즘 분할 과정 N개의 점들을...

확률과 통계 무작위 알고리즘 난수를 발생시켜 진행과정을 결정하는 알고리즘 종류 라스베가스(Las Vegas) 알고리즘 옳은 답을 얻지만 수행시간이 오래 걸릴 확률이 약간 존재 몬테칼로(Monte Carlo) 알고리즘 수행시간이 빠르지만 옳지 않을 확률이 약간 존재

확률과 통계 카탈란 수 [n+2]각형을 n개의 삼각형으로 나눌 수 있는 경우의 수 카탈란 수의 점화식은 아래와 같다. 점확식의 의미: 한 가지 경우를 시행하면 그와 쌍이 되는 다른 경우를 반드시 시행해야 하는 모든 개수, 즉 쌍을 이루는 것들을 나열하는 모든 경우의 수를 카탈란 수라고 한다. ...

확률과 통계 Inversion a1,a2,…,an이 1,2,3,…,n의 순열이라고 할 때, i < j인데 ai > aj 라면 (ai, aj)를 Inversion이라 한다. 4,1,3,2,5: Inversion은 (a1, a2), (a1, a3), (a1, a4), (a3, a4) Inversion ...

문자열 용어 정의 T: 텍스트(text), P: 패턴(pattern) T[i]: T의 u번째 글자 부분문자열 T[i,j]: i번째 문자부터 j번째 문자로 이루어진 문자열, T[i]T[i+1]—T[j] 접두사(prefix): 주어진 문자열의 첫 문자부터 시작하는 부분문자열 접미사(suffix): 주어진 문자열의 마지막 문자에서 끝나는...

문자열 텍스트가 변하지 않을 때, 보다 빠르게 패턴을 찾고 싶을 때 데이터를 매번 검색시 다시 읽을 필요가 없이 색인을 생성하고 이 색인에서 검색하는 것이 타당한 접근 방법이다. ex) 전화번호부, 서적, 지도 등 텍스트의 전처리 기본 아이디어: 패턴 P가 텍스트 T에 나온다면, 이는 T의 어떤 접미사의 접두사이다. 따라서 접미사들을 사...

문자열 K개의 단어로 이루어진 사전에서 각 단어의 길이가 최대 m이라고 할 때, 주어진 문자열 T에서 이 사전에 나오는 단어가 나온 경우를 모두 찾으려면 어떻게 해야할까? Aho-Corasick 알고리즘 기본 아이디어: 주어진 단어들을 트라이 형태로 표현하고, Failure link를 정의하여 매치 실패시 다음으로 이동할 상태를 정의한다...

문자열 문자열 압축 기본 아이디어: 압축한 쪽과 압축을 푸는 쪽이 공통의 ‘사전’을 가지고 있다면, 텍스트에서 나오는 단어를 사전의 단어 인덱스로 바꾸면 압축할 수 있다. 양쪽이 어떻게 사전을 공유? (Lempel-Zive Data Compression) 별도로 사전을 공유하지 않는다. 압축하는 과정에서 사전을 ...