꿈꾸는 개발자 꿈꾸는 개발자

http://www.fas.harvard.edu/~cscie119/lectures/recursion.pdf

MST(Minimum Spanning Tree) 를 찾는 방법은 프림스 알고리즘(Prim's Algoryth)을 이용한다. Prim's Algorythm은 방향은 없지만 가중치는 있는 tree에서 모든 정점을 포함하는 Spanning Tree를 찾는다. 이는 모든 정점을 포함하는 Edge들은 가장 작은 total weight를 갖는 부분집합을 찾는 과정이다. 1. 수도코드 ReachSet = {0}; // You can use any node... UnReachSet = {1, 2, ..., N-1}; SpanningTree = {}; while ( UnReachSet ≠ empty ) { Find edge e = (x, y) such that: 1. x ∈ ReachSet 2. y ∈ UnReachSe..

99개의 값을 저장할 수 있는 배열 item[0], item[1], …, item[98]이 있다. 1부터 100까지의 값이 들어 있는 집합 {1,2,3, …, 100}에서 무작위로 수를 꺼내서 배열에 저장했다. 집합에 들어 있는 원소의 수는 100개인데 반해서 배열은 값을 99개까지만 저장할 수 있으므로 집합 안에 하나의 숫자가 남았다. 남은 것이 어느 수인지 확인할 수 있는 프로그램을 작성하라. int gaussTotal = 5050; for (i=0; i

01. 최초의 알고리즘 가장 오래된 알고리즘은 기원전 300년경에 만들어진 유클리드의 최대공약수를 찾는 알고리즘이다. 최대공약수는 2개 이상의 자연수의 공약수들 중에서 가장 큰 수이다. * 핵심 유클리드는 2개의 자연수의 최대공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수와 같다는 성질을 이용하여 최대공약수를 찾았다. 예를 들면, 24와 14의 최대공약수는 24-14=10과 작은 수 14와의 최대공약수와 동일하다. 유클리드는 이 과정을 반복하여 최대공약수를 다음과 같이 계산하였다. 단, 최대공약수 (a,0)=a 이다. 최대공약수(24, 14) = 최대공약수(24-10, 14) = 최대공약수(10,14) = 최대공약수(14-10, 10) = 최대공약수(4, 10) = 최대공약수(10-4, 4..

버블정렬은 이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복하여 정렬한 알고리즘이다. 배열을 좌우가 아니라 상하로 그려보면 정렬하는 과정에서 작은 수가 마치 '거품'처럼 위로 올라가는 것을 연상케 한다. 예제를 통해 버블 정렬의 수행 과정을 살펴보자. [그림1-1] 에서 가장 먼저 첫 번째 숫자인 50과 40을 비교하고 40이 작으므로 40과 50을 바꾼다. 다음에는 두 번째 숫자인 50과 이웃하는 90과 비교하고, 90이 크므로 자리를 바꾸지 않는다. 마지막으로 세번째 숫자인 90과 이웃하는 10을 비교하고, 10이 작으므로 90과 자리를 바꾼다. 이렇게 입력을 전체적으로 처리하는 것을 패스(pass)라고 한다. 즉, 1번의 패스 후에 그 결과를 살펴보면, 작은 수는 버블처럼 위로 1..