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

public class Dijkstra { private int[][] w;// 가중치 행렬 private int length[];// 시작점에서 각 정점으로 가는 최소값을 저장하는 곳 private int touch[];// 출발점에서 목적지까지 가는데 걸리는 최소 가중치 private boolean isSelect[];// 정점이 선택되었는지를 판별하기 위한 것 private char vertex[];// 숫자로 한계산을 영어로 치환하기 위한 것 private int n;// 정점들의 수 // 정점의 개수를 받아서 그 만큼 할당을 해주면서 초기화하는게 옳은 것 // 다른 부분은 그렇게했지만 가중치 받는 것은 문제에서 가중치가 주어졌기때문에 // -> 고정되어서 입력없이 바로 입력되게하였다. Dijks..

public class Prim { private int[][] w;// 가중치 행렬 private boolean isblue[];// 정점 v가 이미 선택되었는가, 아닌가 private int near[];// 선택된 정점들중에서 가장 가벼운 가중치 private int n;// 정점들의 수 private char vertex[];// 숫자로 한계산을 영어로 치환하기 위한 것 // 정점의 개수를 받아서 그 만큼 할당을 해주면서 초기화하는게 옳은 것 // 다른 부분은 그렇게했지만 가중치 받는 것은 문제에서 가중치가 주어졌기때문에 // -> 고정되어서 입력없이 바로 입력되게하였다. Prim(int n){ this.n = n; w = new int[n][n]; isblue = new boolean[n]; n..

* 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("종점 " + ..