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

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

문제 한 쌍의 토끼들은 한 달이 될 때에 한 쌍의 토끼를 낳고 두달이 될 때에 또 다른 한 쌍의 토끼를 낳는다. 내가 방금 한 쌍의 새로 태어난 토기들을 샀다면 지금부터 n번째 달에 몇 쌍의 토끼들이 태어날까? 주 : n이 주어지면 토끼 쌍들의 수를 구해야 한다. n은 매개 변수이다. f(n)을 지금부터 i 번째달에 태어난 토끼 쌍들의 수라고 하자. n 0 1 2 3 4 5 6 ... f(n) 1 1 2 3 5 8 13 ... > f(n) = f(n-1) + f(n-2) / f(0) = f(1) = 1 / n >= 2 (수학적 풀이) 점화식을 풀어서 "수학적"으로 해결 (알고리즘) f(n)을 구하는 알고리즘 설계 : 매개 변수 : n // 출력값 : f(n) ⓐ n이 0이면, f(n) = 1 ⓑ n이 1..

1. 문제(Problem) - 우리가 해답을 찾으려고 묻는 질문 ex) n개의 숫자들의 목록 S를 비내림차순(non-decreasing/오름차순)으로 정렬하자. 2. 매개변수(Parameter) - 문제에 특정한 값이 지정되어 있지 않은 변수. 위의 예에서 S와 n이 매개 변수역할을 한다. 3. 문제의 사례(Instance) - 문제의 매개 변수들에 각각 특정한 값을 지정한 것 ex) 위문제들중 문제의 한 사례는 / S = [10, 7, 11, 5, 13, 8], n = 6 4. 문제의 한 사례에 대한 해답 - 문제의 한 사례에서 문제가 제기하는 질문에 대한 해답 ex) 위의 사례에 대한 해답은 [5, 7, 8, 10, 11, 13]이다. 5. 알고리즘 - 문제의 각 사례에 대한 해답을 얻기 위한 단계별..