Basic ConceptIn the Sum-of-Subsets problem, there are n positive integers (weights) $w_i$ and a positive integer W. The goal is to find all subsets of the integers that sum to W. As mentioned earlier, we usually state our problems so as to find all solutions. 👉 부분집합의 합을 구하는 문제는 n개의 양의 정수(무게) $w_i$와 양의 정수 $W$가 주어졌을 때, 합이 $W$가 되는 정수의 부분집합을 모두 찾는 것이다. n-Queens 문제처럼 모든 해답을 찾도록 알고리즘을 구현할 것이다. Exampl..

Basic ConceptThe classic example of the use of backtracking is in the n-Queens problem. The goal in this problem is to position n queens on an n×n chessboard so that no two queens threaten each other; that is, no two queens may be in the same row, column, or diagonal. The n-Queens problem is a generalization of its instance when n = 8, which is the instance using a standard chessboard. For the s..

Basic ConceptIf you were trying to find your way through the well-known maze of hedges by Hampton Court Palace in England, you would have no choice but to follow a hopeless path until you reached a dead end. When that happened, you’d go back to a fork and pursue another path. Think how much easier it would be if there were a sign, positioned a short way down a path, that told you that the path l..

Basic Concept We developed a $\Theta(n^3)$ algorithm, which is Floyd Algorithm, for determining the shortest paths from each vertex to all other vertices in a weighted, directed graph. If we wanted to know only the shortest paths from one particular vertex to all the others, that algorithm would be overkill. Therefore, we will use the greedy approach to develop a $\Theta(n^2)$ algorithm for this..

Time Complexity ComparisonThe number of edges in a connected graph is $$ n-1 \leq m \leq \frac{n(n-1)}{2} \approx n^2 $$ 👉 어떤 그래프의 정점의 개수를 n이라고 할 때, 이음선 개수(m)의 범위는 n - 1개에서 부터 n(n - 1)/2이다. 여기서 n(n-1)/2은 1부터 n-1까지의 합이다. For a graph whose number of edges m is near the low end of these limits (the graph is very sparse), Kruskal’s algorithm is $\Theta(nlgn)$ which means that Kruskal's algorithm sh..

Basic ConceptWe will investigate two different greedy algorithms for minimum spanning trees, Prim’s algorithm and Kruskal’s algorithm. Each uses a different locally optimal property. 👉 앞서 살펴 본 프림 알고리즘 대신 크러스컬 알고리즘을 이용해도 최소신장트리를 구할 수 있다. Example etermine a minimum spanning tree. Step 1 가중치를 기준으로 전체 이음선들을 오름차순으로 정렬한다. Step 2 5개의 정점들이 있으므로 총 5개의 서로소 집합, 즉 {$v_1$}, {$v_2$}, {$v_3$}, {$v_4$}, {$v_5$..