P문제란? 다항시간 내(reasonable time)에 답을 구할 수 있다. 다루기 쉬운 문제 결정론적 다항시간 문제 NP문제란? Nondeterministic Plynomial time 다항시간 내 풀 수 없는 문제 다항시간내에 풀 수 있는지 없는지 모른다. 다루기 어려운 문제 비결정론적 다항시간 문제 -> 적어도 검산은 쉽게 할 수 있는 문제. 하지만 답을 찾기는 어려운 문제 Unsolvable problems 어떤 알고리즘으로도 풀 수 없는문제 Optimization/Decision problems Hamiltonian paths and cycles Traveling salesman problem Is P=NP? P⊆NP P=NP라면? 복잡하고 어려운 문제들을 다항시간 내에 반드시 풀 수 있다. 하..
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...
