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. 최단경로 문제) 모든 하위 문제를 풀고 그 결과를 저장해두어 그 결과를 ..
