Shortest Path Problem(최단 경로 문제) 정점 u 에서 v까지의 최단 경로 : 정점 u에서 정점 v까지의 경로 중에 경로의 값이 가장 작은 경로 정점 u를 시작점(source), 정점 v를 도착점(destination) 이라고 한다. δ(u,v) : u에서 v까지의 최단 경로 값 negative-weight cycles이 있으면 최단경로 문제는 정의되지 않는다. δ(u,v)=-∞가 나올 수 있음 positive-weight cycles, zero-weight cycles 는 구할 수 있다. (사이클 무시하면 됨) optimal substructure theorem(최적부분 구조 : 분할된 문제의 결과가 매번 같다)으로 greedy sub를 만족한다. δ(s,v) ≤δ(s,u)+δ(u,v)..
Graph(그래프)와 Tree(트리) 그래프 : 정점(vertex)과 그 vertex를 연결하는 간선(edge)을 하나로 모아둔 자료구조 트리 : 그래프의 한 종류 ,Cycle이 불가능, undirected, connected,노드가 N개인 트리는 항상 N-1개의 간선을 가진다. Weight Undirected Graph(가중 무방향성 그래프) 그래프(vertex,edge 로 이루어진 집합) + undirected (방향성을 가지지 않음) + 각 간선이 값을 가짐 G=(V,E) 간선 집합에 속하는 각 간선 (u,v)는 w(u,v)를 가진다. Spanning Tree(신장 트리), Spanning Forest Spanning Tree : 그래프에 있는 모든 vertex를 연결한 트리, 트리의 각각의 값을 ..
Greedy Algorithm optimization problem을 풀 때 사용 dynamic programming이 너무 과도할 때(복잡할 때) greedy로 더 쉽게 풀 수 있다. 현재 상황에서 최선의 답을 선택. 현재 상황의 최선이 전체의 최선이길 바라면서 푼다. Greedy choice property(앞의 선택이 이후의 선택에 영향을 주지 않는 조건)를 만족할 때 사용한다. 현재 상황에서는 최선이지만 전체에서 최선이라는 보장은 없다. greedy로 풀 수 있는 문제는 모두 dynamic programming으로 풀 수 있다. top-down 구조 (dynamic은 bottom up) ex) 가방채우기 문제, 허프만 코드, 크루스컬 MST, 프림 MST, SSSP Counting money 6...
문제 해결 방법의 종류 brute-force approach : 모든 경우에 대해서 다 계산하고 가장 좋은것을 택하는 방법. n이 커지면 너무 오래걸려 실행 불가능하다. divide and conquer approach dynamic programming approach greedy approach Dynamic Programming(DP) 주어진 문제를 하위문제로 나누어서 해결한다. 하위 문제가 서로 연관이 있을 때 사용 (divide and conquer은 서로 연관이 없을 때 사용) optimization problem(최적해를 구할 때) 를 풀 때 사용 (최적화문제 : 답이 여러개인 문제에서 가장 좋은 답을 찾는 문제 ex. 최단경로 문제) 모든 하위 문제를 풀고 그 결과를 저장해두어 그 결과를 ..
Binary Search Tree 이진탐색과 연결리스트를 결합한 자료구조이다. 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값만 있어야한다. 각 노드의 오른쪽 서브트리에는 해당 노드보다 큰 값만 있어야한다. operation : SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE average case : O(log n) (평균 높이 : log n) worst case : O(n) Search 루트에서 시작. k를 찾을 때 key[x]>k 이면 x의 왼쪽 subtree에서 search key[x] 그냥 삭제 Case2: 삭제할 노드에 자식노드가 1개 있을 때 -> 해당 노드를 지우고 해당 노드의 자식과 부모를 연결 Case3: 자식노드가..
hashing dictionary (key, value)를 implementing insert, search, delete 연산의 average-case : O(1) find minimum과 같은 sort연산은 비효율적이다. dictionary dynamic-set data structure. 동적으로 크기가 변한다. operation : insert, search, delete hash table key : hash function의 input. U : universe of keys. 모든 가능한 키의 집합 K : actual keys. 딕셔너리에 매칭된 실제 키 Hash Table을 만들 때 U를 저장할 필요 없다. |k|=n의 사이즈를 테이블로 만든다. 하지만 좁은 장소에 여러개를 저장해야하므로 h..
NER? NE(개체명) 을 R(인식) 하는 작업. 문자열 안에서 NE의 위치를 알아내고 사전정의한 카테고리에 따라 알맞게 분류하는 작업 즉, NE를 인물, 장소, 시간 이라 하면 문장 안에서 인물, 장소, 시간을 나타내는 명사를 찾아내는 것이다. input : 문자열, output : 단어별로 해당되는 태그 -> multi class 분류 작업 NE 태깅 시스템 1. BIESO 개체명이 시작할 때 : B 토큰이 개체명 중간에 있을 때 : I 토큰이 개체명의 마지막에 있을 때 : E 하나의 토큰이 하나의 개체명 : S 토큰이 개체명이 아님 : O 2. BIO 1번에서 E와I 통합, S와 B통합 NER 접근법 1. 규칙 기반 접근 2. 사전 기반 접근 3. 기계학습 접근 More Info https://gi..
Markov Property → A → B → C → 연쇄해서 사건이 일어나므로 특정 상태의 발생 확률은 그 전 상태의 확률값으로 구할 수 있다. 단어 등장확률 계산하면 P(나는 오늘 커피를 마셨다) = P(나는) X p(오늘 | 나는 ) X P(커피를 | 나는, 오늘 ) X P(마셨다 | 나는, 오늘, 커피를) 뒤로 갈 수록 확률을 계산하기 어려워짐 → 마르코프 특성 적용 P(나는 오늘 커피를 마셨다) = P(나는) X p(오늘 | 나는 ) X P(커피를 | 오늘) X P(마셨다 | 커피를) → P(현재|이전) : bigram but, 특정 상태의 확률값을 구하기 쉽지 않음 이전의 모든 확률을 구하는것은 불가능. → 미래의 상태는 오직 현재 상태의 영향만 받는다 라고 가정 Markov Chain Mar..
