dp1 [알고리즘] Dynamic Programming(동적 계획법)-DAG(Directed Acyclic Graph) shortest path(최단 경로) 위의 그림은 DAG(Directed Acyclic Graph) 이다. DAG는 비순환 그래프를 의미하는데 단순히 말해서 cycle이 존재하지 않는다는 뜻이다. 다음에 그래프의 종류에 대해서는 따로 글을 써보도록 하겠다. 모모든 DAG 그래프는 아래와 같이 linearization 할 수 있다. dist(X)가 S로부터 어떤 점 X로 갈때의 최단 거리를 리턴하는 함수라고 생각해보자. dist(X)를 계산하기 위해서는 dist(C)+3과 dist(B)+1 만 비교하면 된다. 왜냐하면 B와 C만 D의 predecessor 이기 때문이다. Predecessor는 뭐냐면 Q->W 일때 Q를 predecessor, W를 successor 라고 한다. 즉 D 직전에 오는 것이 B와 C밖에 없다는 의미이다. 따라서 임.. 2023. 5. 26. 이전 1 다음
