# Kruskal의 MST 알고리즘 Kruskal의 알고리즘은 탐욕적인 방법(greedy method)을 이용한다. 탐욕적인 방법은 알고리즘 설계에 있어 중요한 기법 중 하나다. 결정을 해야 할 때, 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택하는 방법을 말한다. 순간 순간의 최선을 선택해 최종적인 해답에 도달하는 과정인 것이다. 당시에 최적이라고 생각했던 선택들을 모은다고 해서 최종적인 결과가 최적의 해답이라는 보장은 없다. 따라서 탐욕적인 방법은 항상 검증이 필요하다. 다행히 Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다. Kruskal의 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건을 기초로 각 단계에서 사이클을 이..
# Prim의 MST 알고리즘 최소 비용 신장 트리(MST: minimum spanning tree)는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장트리를 말한다. 최소 비용 신장 트리를 이용하면, 도로 건설이나 전기 회로설계, 통신 인프라 구축 등의 문제를 가장 효율적으로 처리할 수 있게 된다. Prim의 알고리즘은 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법을 사용한다. 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함된다. Prim은 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다. 이 과정은 트리가 n - 1개의 간선을 가질 때까지 계속된다. // n개의 정점을 가지는 신장 트리의 간선은..
# 피보나치 수열 문제 Fibonacci 수열은 다음과 같이 정의된다.$f_0 = 0, f_1 = 1 그리고 f_i = f_{i - 1} + f_{i - 2}(i > 1 일 때)$ $f_i$를 계산하는 C함수로 순환 함수와 반복 함수를 모두 작성하라. # 구현 // 반복버전에서 반복계수가 2부터 시작해서 n까지 간다는 것만 주의하면 된다. 반복계수가 2인 까닭은 2개의 초기값을 설정해줬기 때문에 0과 1을 지나쳐 2부터 시작되는 것이다. /************************************************* **Fibonacci iterative & recursive ver *************************************************/ #include in..
# 팩토리얼 문제 문제) 팩토리얼 (=계승) 함수 n!은 $n\le1$일 때 n * (n - 1)! 의 값을 가진다. n!을 계산하는 C프로그램을 순환과 반복버전으로 구현하라. # 구현 // 순환함수는 다들 쉽게 작성하시리라 믿고, 반복버전 코드를 배워가시면 좋을 것 같습니다. /************************************************* ** Factorial recursive ver & iterative ver *************************************************/ #include int recur_fac(int n); int iter_fac(int n); void main() { int n; int output1, output2; wh..
# 비둘기집 원칙 문제 문제) 비둘기집 원칙이란 함수 f가 n개의 상이한 입력에 대해 n개보다 작은 상이한 출력이 나온다면 $a\neq$ $b$ 이고 $f(a) = f(b)$인 두 개의 입력 a, b가 존재한다는 것이다. 이와 같이 입력값이 상이하면서 함수값이 같은 a,b를 찾는 C프로그램을 작성하라. # 풀이 이 문제는 한 가지 함수를 미리 정해두고 프로그램을 작성한다. 그 후 함수 내에 같은 y값이 나오는 x값들이 있는지 확인하는 프로그램을 작성하면 된다. /************************************************* ** 비둘기집 원칙 프로그램 *************************************************/ #include #include //..
- Total
- Today
- Yesterday