전체 글146 Greedy 수업 필기 26.그래프 용어 (참고: https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html)비방향성 그래프->양방향 통행 도로를 생각->엣지를 통해서 양 방향으로 갈 수 있다. ->ex) 정점 a와 정점 b를 연결하는 엣지는 (a,b)와 같이 정점의 쌍으로 표현한다. (a,b)와 (b,a)는 동일 방향 그래프->일방 통행 도로를 생각->엣지에 방향성이 존재하는 그래프 27.신장트리란?->'부분'그래프->&G안에 모든 정점을 포함하며&트리가 되는(임의의 노드에서 다른 노드로 가는 경로가 유일, 회로가 존재하지 않는다, 모든 노드는 서로 연결, 엣지를 하나 자르면 트리가 두 개로 분리, 엣지의 수는 노드의 수에서 1을 뺀 것과 같다)(connected a.. 2018. 12. 17. Dynamic Programming 수업 필기 2.Divide and Conquer-> top down 해결법, 나누어진 부분들 사이에 상관관계가 없는 문제를 해결하는데 적합. ex) 피보나치 알고리즘에 d&c 방법을 사용하면 호율적 x. 왜냐? 피보나치의 경우 나누어진 부분들이 서로 연관되어 있기 때문 3.재귀적 해법. divide and conquer로 푸는 방법 중 가장 안좋은 예 4.피보나치를 d&c로 풀면 심각하게 비효율적&엄청난 중복 호출. 5,6.동적 프로그램이 solution. ex) 피보나치 수를 구하는 동적 프로그래밍 알고리즘fibonacci(n){f[0] = 0; f[1] = 1;for (i =2; iprincipal of optimality가 성립함. 2. Principle of Optimality가 성립하지 않는 예)* Lon.. 2018. 12. 17. Prev. 1 ··· 6 7 8 9 Next.