In University ☆ In Bucket Place ☆ Hobby & Study Room ☆

* Kruskal 알고리즘은 다음의 순서대로 실행한다. 1. 연결선들을 가중치 순서대로 정렬하여 배열 EDGELIST[1...e]에 저장한다. 2. sizeT = 0 // 트리에 있는 정점들의 수 3. eCount = 0 // 트리에 있는 연결선들의 수 4. while ( sizeT < n-1 ) { eCount = eCount + 1; (v,w) = EDGELIST[ecount]; if ( not together (v,w) ){ // together(v,w)함수는 v와 w가 이미 합쳐져 있으면 true이다. "연결선 (v,w)를 트리에 추가한다." v와 w를 합친다. sizeT = sizeT + 1; } // 트리에 이미 추가된 노드들 끼리의 선이면 아무것도 실행하지 않고 다음 선으로 넘긴다. } - ..

* Prim의 알고리즘 작성 - 용어 : 처음에 선택된 정점 V0와 합쳐진 정점들은 "적색"정점들이라고 부른다. 그 외 다른 정점들은 "청색" 정점들이라고 부른다. - 알고리즘 : 각 단계에서 한 적색정점과 한 청색 정점을 연결하는 가장 가벼운 연결선을 선택한다. 그리고 청색 정점을 적색으로 바꾸고, 그 연결선을 트리에 추가한다. - 그래프의 표현 : 그래프는 비용행렬 W에 의해 나타내진다. - 슈도 코드 R: 적색 정점들의 집합 B: 청색 정점들의 집합 V: 주어진 그래프 내의 모든 정점들의 집합 T: 트리내에 포함되는 연결선들의 집합 ⓐ 임의의 노드 V0를 선택한다. ⓑ T = 공집합 ⓒ R = {V0} B = V - {V0} ⓓ for ( i = 1 ; i 위에서 중복된 계산 과정이 많이 존재한다는..

* 용어 설명 - 위의 그래프 G1은 무방향 가중치 연결 그래프를 나타내고 있다. - 순환경로(cycle) : 시작하는 정점과 끝나는 정점이 같은 것 ※ 여기서 경로란? 한 정점에서 다른 정점으로 가는 길을 말한다. - 부분그래프 : 그래프 중에서 일부분을 나타낸 것 - 트리 : 연결 되어 있고 순환 경로가 없는 그래프 - 신장트리 : 그래프의 부분 그래프 중에서 본래 그래프의 모든 정점을 가지고 있으며, 트리가 되는 것 - 최소비용 신장 트리: 신장트리들 중에서 가중치가 가장 적은 트리 * 무작정 알고리즘 - 모든 신장트리를 고려한 후, 그 중에서 비용이 가장 적게되는 것을 선택 - 분석 : 각 간선은 포함 될수도 있고 안될 수도 있다.(각간선마다 2가지 경우가 존재한다.) > 2 * 2 * 2 * ...

* 탐욕적 알고리즘 - 현재 상태에서 가장 최적인 상태를 선택하는데 사용하는 알고리즘 - 상태가 변할 때 마다 새로운 실행을 하여서 최적의 상태를 찾는다. ex) 문구점에 627원 짜리 물건을 사는데 1,000 원을 냈다. 가게 주인은 500, 100, 50, 10, 5, 1짜리 동전을 이용해서 최고 적은 수의 동전으로 거스려주로고 한다. 최소의 동전의 수는 몇개인가? > 거스름돈 : 373원 > 탐욕적 알고리즘은 가장 좋아 보이는 것부터 선택을 실시한다. ① 500원 짜리 동전을 선택한다. 373 500 원짜리를 내려 놓는다. ② 100원 짜리 동전을 선택한다. 373 > 100 -> 100원짜리 동전을 가진다. / 남은 금액 : 273원 ③ 100원 짜리 동전을 다시 선택한다. 273..

다음의 사실을 이용하여 연쇄행렬곱셈의 최적의 곱셈 순서를 구한다. 1. n*m 행렬과 m*l을 곱하기 위해서 필요한 곱셈들의 수는 n*m*l이다. 2. 행렬의 곱셈은 겹합적이다. (A*B)*C = A*(B*C) 위의 사실을 가지고 3개이상의 행렬 곱셈을 수행하는대 순서에 따라서 곱셈의 수가 큰차이가 있음을 발견했다. ex) A(100*1), B(1*100), C(100*5) 행렬이 있다. ⓐ (A * B) * C 의 곱셈의 수는 A*B를 구하는데 곱셈의 수 "100*1*100"에 A*B에 의해서 생성된 배열(100*100) 행렬에 C를 곱하여 해를 구하는데 필요한 곱셈의 수 "100*100*5"를 더한 수 "60,000"이다. ⓑ A * (B * C) 의 곱셈의 수는 B*C를 구하는데 곱셈의 수 "1*1..

public class bincoeff { // 두 개의 값중에서 작은 값을 판별하여서 반환해준다. private int min(int i, int j){ if ( i >= j ) return j; else return i; } // 이항 계수를 구하는 부분 public int coeff(int n, int k){ int i, j;// 루프문을 돌기 위해서 필요한 변수 int B[][] = new int[n+1][k+1];// 배열을 생성해준다. // 구하려는 값을 구하기 위해서는 1을 더해서 확장하여 생성해줘야한다. for ( i = 0 ; i

import java.util.*; public class floyd { private int D[][]; private int W[][]; private int P[][]; // 생성자 floyd(int n){ int i,j; Scanner scanner = new Scanner(System.in); // 받은 종점의 개수만큼 배열을 생성한다. D = new int[n][n]; // D는 최단거리를 저장하는 변수 W = new int[n][n]; // W는 가중치변수 P = new int[n][n]; // P는 이동간 거쳐가는 곳을 알려주기 위해 있는 변수 for ( i = 0 ; i < n ; i++ ) for ( j = 0 ; j < n ; j++ ){ System.out.print("종점 " + ..

* 최단경로찾기란? - 우리가 흔히 접하는 핸드폰의 지하철 안내도, 자동차의 네비게이션 등은 모두 최단거리 알고리즘을 사용하여서 작동을 한다. 내가 소개하려는 최단 경로도 있지만 요즘은 A*라는 최단 경로 알고리즘이 많이 쓰인다. - 지금 소개하려는 Floyd알고리즘을 이해하려면, 그래프에 대한 이해가 이미 충분히 되있어야 할 것이다. * 최단경로를 풀기위해 알아야하는 용어 - 가중치 행렬 W[i][j] > 정점 i에서 j로 이동하는 화살표가 존재한다면 화살표에 해당하는 가중치 > 정점 i에서 j로 이동하는 화살표가 없다면 무한대 > 정점 i와 j 의 값이 같다며느 0의 값을 가진다. - 경로비용 : 경로상의 모든 화살표들의 가중치들의 합 - 최단경로 : 경로비용이 가장 작은 경로 - 최단 경로 문제는 ..

이번엔 합병정렬에서 3부분으로 나눠서 합병하는 소스를 보도록 합시다. 앞과 마찬가지로 자바로 작성했습니다. private void MergeSort(int i, int j){ int midLeft;// 배열의 1/3지점을 가르킴 int midRight;// 배열의 2/3지점을 가르킴 if ( j - i >= 2 ){// 배열울 분할시 3개보다 적으면 분할하면안됨 midLeft = (int)(i*2+j)/3;// 지점 계산 midRight = (int)(i+j*2)/3; MergeSort(i,midLeft);// 재귀적 순회 MergeSort(midLeft+1,midRight); MergeSort(midRight+1,j); Merge(i,midLeft,midRight,j);// 합병 }else{// 배열 ..