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

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의 값을 가진다. - 경로비용 : 경로상의 모든 화살표들의 가중치들의 합 - 최단경로 : 경로비용이 가장 작은 경로 - 최단 경로 문제는 ..

* Guarded Commands ( Dijkstra 1975 ) - 목적 : 프로그램을 개발하면서 검증을 바로바로 하고 싶다. > 즉, 프로그램 개발이 끝난 동시에 검증이 끝나있음을 의미 한다. - 위의 목적을 이루기 위해서 selection과 loop를 새로 정의 하였다. * Selection of Guarded Command - []의 역할 > 일반 if-elseif문에서의 elseif와 같은 기능을한다. 그러나 여기엔 크나큰 차이가 있다. > 일반 if-elseif문과 다르게 모든 boolean expression에 대해서 T/F를 검사를 하여 True인 것 중에서 랜덤으로 하나의 stmt를 실행한다. > 조건이 모두 false이면 error를 출력해준다. - []의 기능으로 인한 이점 > 랜덤..

* 반복구문이란? - 반복이 일어나는 구문을 말한다. - 컴퓨터에서 반복이 일어나는 경우는 iteration(for, while)이나 recursion(재귀호출)이 있다. > 두 가지의 경우 중 이번 페이지는 iteration의 경우만 보도록 한다. * Iteration control statement(반복 조정 구문) - 반복 조정 구문(이하 반복문)의 설계 이슈 ⓐ 어떻게 반복문을 제어할 것인가? > 제어 방법에는 counter방법과 logic방법이 있다. counter방법은 단순한 숫자로 돌아가는 것으로 for문이 이에해당한다. logic은 조건의 T/F로 반복을 정하는 것으로 while문이 이에 해당한다. ⓑ 어디서 반복여부를 체크 할 것인가? > 제어를 체크하는 위치는 앞과 뒤의 경우에 따라서 ..

* if문에 의해서 2개를 선택하는 구조가 생성되었다. 더나아가 사람들은 다중선택 구조를 설계하였다. 대표적인 다중선택 구조는 switch-case문이라고 할 수 있다. 이번엔 이 다중선택 구조에 대해서 알아보자. * 설계 이슈 ⓐ 표현식의 구조와 선택구문의 타입은 어떤 것으로 할 것인가? > (in C) switch(선택구문){ ... } ⓑ 어떤 case를 선택하게 할 것인가? (single, compound, sequential) ⓒ 전체가 하나로 묶여 있는가? > 캡슐화가 되어 있는가? ⓓ 각 case에 해당하는 제어단위는 어떻게 할 것인가? > 해당 case만 실행할 것인가? case이하의 모든 구문(case문은 생략)을 실행할 것인가? ⓔ case로 제공되지 않은 표현에 대한 처리는 어떻게 해..

* Statement - Level Control Structure - 문장 수준에서 일어나는 제어 구조 - 제어란? 컴퓨터가 실행하는 순서와 다르게 실행 위치를 변경하는 행동 * 제어가 일어나는 단계 ⓐ 여러개의 수식이 있을 경우 - a + b + c + d * e : 컴퓨터의 실행 순서에 따르면 'a+b'부터 실행해야 하지만, 'd*e'부터 실행한다. > 이 경우는 연산자의 우선순위와 결합법칙에 의해 컴퓨터의 실행 순서와 다르게 제어가 일어난다. ⓑ 프로그램 단위당 - 함수나 Sub-Program > 함수 호출에 의해서 실행 위치가 변경된다. ⓒ 프로그램 안에서의 문장에 의해서 실행위치가 변경 ※ ⓐ는 이미 이전에 설명한 것이므로 Pass하고 이번엔 ⓒ를 중점적으로 살펴 보겠다. * 제어 구조의 탄생..

* Arithmetic Expression (수학적 표현식) - 수학적 표현식은 다음의 4가지로 구성이 된다. > Operator(연산자), Operands(피연산자), Parentheses(괄호), Function calls(함수 호출) - 수학적 표현식을 나타낼때는 다음의 설계 이슈를 가진다. > 연산자 우선순위는 어떻게 할 것인가? > 연산자 결합법칙은 어떻게 할 것인가? > 피연산자들의 평가 순서는 어떻게 할 것인가? > 부작용에 대한 대처는 어떻게 해줄 것인가? > 다양한 타입이 섞여있는 표현을 허락할 것인가? * 연산자 우선순위 - 연산자 종류는 연산자하나에 오는 피연산자들의 수에 따라서 달라진다. > A unary operator(단항연산자) : -a, -1, ++a > A binary op..

* Type Compatibility = Type Equivalence = 타입 호환성 - 같은 선언문에 있거나, 같은 타입이름을 갖는 것 ex) int a, b, c; // 같은 선언문에 있다. int a; int b; // 같은 타입이름을 갖는다. - Compatibility 방식에는 이름을 가지고 하는 것과 구조를 가지고 하는 것 두 가지로 나뉜다. * Name Type Compatibility - 반드시 정규 파라메터와 실제 파라메터의 타입 이름이 같아야 한다. (formal parameters = actual parameters) - 구현하기가 쉽다. - 매우 제한적이다. ex) type indextype = 1...100; //indextype을 새로 정의, 이것은 integer 1~100만을..

이번엔 합병정렬에서 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{// 배열 ..

이진 검색에서는 분할을 2부분으로 하여서 검색을 실시하였습니다. 이번엔 분할을 3부분으로 나누는 검색하는 알고리즘을 보여드리겠습니다. 자바로 작성하였습니다~ 별거는 없습니다. private int three_search(int low,int high){ int midLeft; int midRight; if ( low > high ) return -1; else{ midLeft = (int)((low*2+high)/3);// 1/3지점 선택 midRight = (int)((low+high*2)/3);// 2/3지점 선택 if ( key == value[midLeft] ){ // 키값 비교하여 같으면 인덱스 출력 return midLeft; } else if ( key == value[midRight]){ ..