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

* 최단경로찾기란? - 우리가 흔히 접하는 핸드폰의 지하철 안내도, 자동차의 네비게이션 등은 모두 최단거리 알고리즘을 사용하여서 작동을 한다. 내가 소개하려는 최단 경로도 있지만 요즘은 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{// 배열 ..

이진 검색에서는 분할을 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]){ ..

1. 문제 : 이항 계수(Binomial Coefficient) 문제를 해결하라. (for 0 0 정수이고, k는 0보다크거나 같고 n보다 작거나 같은 정수이다. if ( k == 0 || k == n ) return 1; else return bincoeff(n-1,k-1) + bincoeff(n-1,k); } - 분석 : 매우 비효율적이다. > Why? 문제가 2개의 더 작은 하위 문제들로 나뉘어지나, 하위 문제들이 원래의 문제 만큼 크다. 즉, 하위 문제가 상위 문제와 겹치는 경우가 발생한다. 균형취하기가 사용이 안됨(?) 4. 동적프로그래밍 해법 - 설계 아이디어 ⓐ 다음의 사실을 사용하라. A[n][k] -> A[n-1][k-1] + A[n-1][k] (단,n > 0 정수이고, k는 0보다크거나..

* 동적프로그래밍(Dynamic Programming)이란? // 분할정복알고리즘과의 비교 - 분할정복식 알고리즘 설계법은 하향식 해결법으로 나누어진 문제가 독립적인 문제를 해결하는데 적합하다. > 피보나치의 알고리즘을 분할정복식으로 구현하면, 알고리즘을 실행하면서 같은 계산을 한 번 이상하는 결과를 유발한다. 따라서 분할정복 알고리즘에 적용하기 부적합하다. - 동적 프로그래밍은 상향식 해결법으로 분할정복식과 같이 문제를 나눈 후에 나누어진 하위 문제들을 해결한다. > 문제를 해결할시 하위에서 풀은 값이 상위의 문제를 해결하는데 필요하면, 반복계산없이 하위 결과를 가져와 사용한다. * 동적프로그래밍 설계 전략 - 문제의 한 부분을 더 작은 하위 문제들의 부분으로 분할한다. - 작은 하위 문제들의 실례를 ..

- 균형 취하기를 적용한 분할 정복은 분할한 하위 문제들이 독립적이라면(같은 하위 문제가 없다면) 유용한 기법 > 피보나치 문제는 하위 문제들이 독립적이지 않은 예제로, 분할정복으로 해결하기에 효율이 낮은 문제이다. - 분할과 합병단계는 효율적으로 구성되어야한다. > 대부분의 경우에는 분할 또는 합병 단계 중 하나는 쉽다. > 문제는 보통 2개의 하위 문제들로 나뉘어지나 항상 그렇지는 않다.

. N개의 숫자들을 정렬하는 방법 ⓐ 알고리즘(명백한 방법) - 최대값을 찾는다. - 남아 있는 숫자들을 회귀적으로 정렬한다. ⓑ 분석 - 요구되는 비교 횟수 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = ⊝(n^2) > 명백히 이 방법은 "균형취하기"발견법(Heuristic)을 이용하지 않는다. ⓓ 새로운 알고리즘 전략 : 합병정렬 - 배열을 반(Half)로 나눈다. - 두개의 부분들을 각각 정렬한다. - 정렬한 두 개의 부분들을 병합한다. ex) 27 10 12 20 25 13 15 22를 정렬하라. ⓔ 새로운 알고리즘 구현 //배열 a[i...j]를 정렬한다. void Mergesort(int i, int j){ int mid; if ( i > j ) { mid = flo..

1. 이진 검색(Binary Search) - 문제 : 크기가 n인 정렬된 배열 S에 키(key) x가 있는지를 탐색 ⓐ 명확한 방법 - 알고리즘 ① 키 x를 찾을 때까지 배열의 첫번째 요소부터 시작하여 x를 배열의 각 요소와 순서대로 비교한다. - 복잡도 분석 > 최악의 경우 n번을 비교해야 한다. - 관찰 > 이 방법은 "배열이 정렬되어 있다는 사실"을 이용하지 않고, "균형취하기"라는 발견법을 이용하지 않았다. ⓑ 효율적인 방법 - 알고리즘 ① 키 x를 배열의 중간요소와 비교한다. 같으면 찾았으니 끝낸다. 캍지 않으면, 배열을 중간요소를 기준으로 반을 나눈다. ② 키 x가 중간요소보다 작으면 왼쪽에 위치한 배열반쪽을 선택한다. 키 x가 중간요소보다 크다면 오른쪽에 위치한 배열의 반쪽을 선택한다. ③..

1. 설계전략 ⓐ 분할(Divide) - 문제를 풀기 쉽도록 여러개의 작은 하위 문제들(Sub Problems)로 나눈다. ⓑ 정복(Conquer) - 더 작은 하위 문제들을 회귀적으로 푼다. ⓒ 통합(Merge) - 본 문제에 대한 답을 구하기 위해 하위 문제들의 답을 합친다. 2. 문제 : 배열의 최대 값과 최소 값 찾기 - 일반 해결법 ⓐ 배열의 값을 일일이 비교하며 최대값을 구한다. ⓑ 최대값을 제외한 모든 값을 비교하며 최소값을 구한다. > 효율 - 배열의 크기 : n - 비교 횟수 : n - 1 - 총 비교 횟수 : n-1(최대값 비교횟수) + n-2(최소값 비교횟수) = 2n - 3 - 분할 정복을 이용한 해결법 ⓐ 배열을 반으로 나눈다. ⓑ 양쪽 절반들의 최대값과 최소값을 구한다. ⓒ 배열..

1. 차수(Order) - 어떤 1차 시간(linear-time) 알고리즘이 어떤 2차 시간(quadratic-time) 알고리즘 보다 더 효율적이다. - 일반적으로 고차항이 시간 복잡도를 지배한다. ex) 주1 : 0.01n^2 >= 100n ( n >= 10,000) 주2 : n = 1,000,000 일때 0.01n^2과 0.01n^2+100n+10,000의 값은 거의 같다고 볼 수 있다. > 0.01n^2+100n+10,000에서 n^2의 항이 식을 지배함. 2. 큰(Big) O 표기법 - 정의 주어진 복잡도 함수 f(n)에 대해서 O(f(n))은 n>=N인 모든 정수 n에 대해서 g(n) 0)와 음이 아닌 정수 N이 존재하는 g(n)함수들의 집합이다. - g(n) ∈ O(f(n))이라면 우리는 g..