전체 글10 [알고리즘] 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. [알고리즘] Dynamic Programming(동적 계획법)-정의, 피보나치 수열 동적 프로그래밍이란 큰 문제를 작은 부분 문제로 분해하여 해결하는 방법이다. 이렇게 하면 각 부분 문제의 해답을 여러 번 반복하지 않아도 되므로 전체 문제를 훨씬 빠르게 해결할 수 있다. 이 방법은 문제가 두 가지 특성을 가질 때 잘 작동한다: 최적 부분 구조(Optimal structure) 최적 부분 구조는 전체 문제의 최적 해답이 그 부분 문제들의 최적 해답에서 구성될 수 있음을 의미한다. 중복되는 부분 문제(Overlapping Subproblems) 중복되는 부분 문제는 동일한 부분 문제가 여러 번 반복되는 경우를 의미한다. 피보나치 수열을 예로 들어보자. 수열의 n번째 항을 구할 때, 재귀는 아주 쉬운 방법이다. 아래는 재귀를 이용해 파이썬으로 구현한 피보나치 수열이다. 그런데 이 알고리즘은 .. 2023. 5. 25. 이전 1 2 3 다음
