greedyalgorithm2 0-1 knapsack problem 가방에 최대 무게가 있고 그 무게 안에 물건을 넣는데 물건의 가치가 최대로 넣는 경우를 구하는 문제. Brute force로 문제를 풀면 모든 가능한 부분집합의 경우를 비교해보면 되므로 2의 n번을 비교해보게 된다. 예를 들어 보석1, 2, 3, 4 가 있고 각각의 무게와 가치가 있을 때 0부터 최대 가방무게 n까지 열의 속성으로 두고 0부터 최대 보석 가지수를 4개까지 행이 속성으로 두어서 보석 가지 수⑊가방 무게 0 1 2 .. n 0 0 0 0 0 1 0 2 0 3 0 4 0 이런 식으로 테이블이 만들어진다 생각하고 이해해보면 쉽다. 처음에 이 문제를 이해하려고 했을 때 많이 애를 먹었던 부분이 왜 보석을 여러개를 안넣고 1개만 넣는거지??였다. 예를들어 보석1의 무게가 1이면 가방 무게가 2이므로.. 2021. 6. 9. 프림 알고리즘 Prim's Algorithm 일정 시간 복잡도 MST(minimum spanning tree)구하는 알고리즘 정점 선택 기반으로 가중치 제일 낮은 방향으로 이전 단계의 신장트리를 확장해나간다. 트리가 N-1개의 간선을 가질 때까지 반복한다. 의사 코드를 보면 다음과 같다. void prim(int n, const numberW[][], set_of_edges& F) //정점 개수, 간선 정보, 방문 간선 { index i, vnear; number min; edge e; index nearest[2..n]; //해당 인덱스의 정점에서 가장 가까운 정점 정보 number distance[2..n]; //현재 방문한 정점에서 해당 인덱스의 정점까지 거리(최단) F = ∅; for(i = 2; i 2021. 6. 8. 이전 1 다음