5. 확률적 분석과 랜덤화된 알고리즘 통계에 관한 기초 용어 설명 확률함수 어떤 사건 X가 일어날 확률을 Pr(X)라고 표현한다. 주사위를 던져서 1이 나오는 사건을 A, 짝수가 나오는 사건을 B라 하면 $$ Pr(A) = \frac16 , \ \ Pr(B) = \frac12 $$ 라고 표현할 수 있다. 기댓값 각 사건이 벌어졌을 때의 이득과 그 사건이 벌어질 확률을 곱한 것을 전체 사건에 대해 합한 값이다. 예를 들어 500원 동전을 던져서 앞면이 나오면 500원을 얻는다고 해보자. 앞면이 나올 확률 X는 2분의 1, 즉 50%이다. 따라서 ...
5. 확률적 분석과 랜덤화된 알고리즘 5.1 고용 문제 직업 소개소에서 면접자를 추천 받으려면 적은 소개료를 지불해야 한다. 소개받아 면담한 후 일을 잘할 수 있는 사람이면 해고하고 새로운 지원자를 고용하면 된다. 고용하면 많은 소개료를 지불해야 한다. 이 떄 비용을 알고자 한다. Hire-ASSISTANT(n) 1 2 3 4 5 6 best = 0 // 0번은 가장 낮은 점수를 갖는 가상의 지원자 for i = 1 to n 지원자 i를 면접한다. if 지원자 i가 지원자 best보다 나은가? best = i 지원자 i를 고용한다. 위 의사코드가 비용을 의미한다. ...
4.분할정복 4.5 점화식을 풀기 위한 마스터 방법 T(n) = aT(n/b) + f(n) 마스터 방법은 위와 같은 점화식을 푸는 기본 지침을 제공한다. 여기서 a≥1, b>1 인 상수이고 f(n)은 점근적으로 양인 함수다. 마스터 정리 정리 4.1 (마스터 정리) a≥1, b>1 인 상수이고 f(n)이 양의 함수라 하고, 음이 아닌 정수에 대해 T(n)이 다음 점화식에 의해 정의된다고 하자. T(n) = aT(n/b) + f(n) 여기서 n/b는 ⌈n/b⌉ 또는 ⌊n/b⌋을 뜻하는 것으로 이해한다. 그러면 T(n)의 점근적 한계는 다음과 같다. ...
4.분할정복 4.4 점화식을 풀기 위한 재귀 트리 방법 **재귀 트리(recursion tree)**에서는 각 노드가 재귀 호출되는 하위 문제 하나의 비용을 나타낸다. 트리의 각 레벨마다 그 비용을 합한 후 모든 레벨당 비용을 합한다. 예시: T(n) = 3T(n/4)+cn^2 T(n) 은 cn^2 + T(n/4) 3개로 이루어진다. 각 T(n/4)는 c(n/4)^2 + T(n/16) 3개로 이루어 진다. 즉 맨 위부터 각 레벨은 cn^2 1개, c(n/4)^2 3개, c(n/16)^2 9개 .. 로 반복됨을 알 수 있다. 이것이 어느정도 깊이까지 반복될까? 크기를 살펴보면 n -> n/4 -> n/16 이므로 레벨 i 에서는 n/(4^i) 임을 유추할 수 있다. 따라서 4^i = n 일때까지 반복되므로 i = log_4(n) 이라는 정수일때 까지 반복된다. i는 0단계부터 였으므로 총 횟수 log_4(n) + 1개 이다. 레벨 i = log_4(n) 이다. ...
4.분할정복 4.3 점화식을 풀기 위한 치환 치환(Substitution)법 : 귀납 가정을 더 작은 문제에 적용할 때 추측한 해로 치환한다. 해의 모양을 추측한다. 상수들의 값을 찾아내기 위해 수학적 귀납법을 사용하고 그 해가 제대로 동작함을 보인다. 이 책에서는 결과로 나올 해의 모양을 추측하여 치환하는 것에 대한 설명이 많다. 하지만 실제로 양 변에서 공통된 모양을 추출하여 새로운 수열로 치환함으로서 풀 수 있는 점화식 이많다. 예시
4.분할정복 4.2 행렬곱셈을 위한 스트라센 알고리즘 행렬의 곱셈은 다음과 같다 1 2 3 4 5 6 7 8 n = A.rows C는 새로운 n x n 행렬이라 하자. for i - 1 to n for j = 1 to n c_ij = 0 for k = 1 to n c_ij = c_ij + (a_ik)(b_kj) return C 3중 반복문이기 때문에 수행시간 Θ(n^3)이다. Ω(n^3)이라고 예상하지만 사실 o(n^3) 방법이 있따. ...
4. 분할정복 Divide : 문제를 같지만 더 작은 단위로 나눈다. Conquer : 분할된 작은 문제들을 해결한다. Combine : 작은 문제에 대한 해결책을 본래의 문제로 조합하여 대입한다. Recursive case : 분할된 소문제들이 재귀적으로 풀 만큼 충분히 크면 Recursive case라고 부른다. 소문제들을 풀다보면 원래 문제와 동일하지 않을 때도 있는데, 이 떄는 Combine 단계의 일부이다. Recurrences 재귀식을 푸는 세 가지 방법 : 점근적인 Θ 또는 O 상한을 얻는 방법 Substitution method : 수학적 귀납법을 통해 추측을 증명 ...
3.2 표준 표기법과 흔히 사용되는 함수 단조성 m≤n일 때 f(m)≤f(n)이면 함수 f(n)은 단조증가 m≤n일 때 f(n)≤f(m)이면 함수 f(n)은 단조감수 m<n일 때 f(m)<f(n)이면 함수 f(n)은 순증가 m<n일 때 f(n)<f(m)이면 함수 f(n)은 순감소 내림과 올림 x의 내림 : 임의의 실수 x에 대해 x 이하의 정수 중 가장 큰 수 x의 올림 : 임의의 실수 x 에 대해 x 이하의 정수 중 가장 작은 수 a mon n = a%n = a를 n으로 나눈 나머지(remainder, residue) ...
3. Growhth of Functions 일반적으로 알고리즘의 정확한 실행 시간을 계산할 필요가 없다. 입력이 충분히 크면 최고차항간 비교만 유의미하기 때문이다. ex) 병합정렬(nlgn), 삽입정렬(n^2) 처럼 이전에 공부한 애들을 보면 알 수 있음. 입력이 충분히 커서 실행 시간의 증가율의 상대적 순서만 볼때, 우리는 알고리즘의 점근적(asymptotic) 효율성을 따지게 된다. 입력 크기가 아주 작을 때를 제외하고는 일반적으로 최선의 선택이 될 수 있다. 즉, 일반적인 상황이란 최고차항의 차수로 실행시간의 차이를 비교하는 때를 말하는데 이 때는 점근적으로 접근하게 된다. ...
삽입 정렬 : 점진적인 방법 사용 원소 A[j]를 정렬된 부분 배열 A[1 .. j-1]의 적절한 위치에 삽입 2.3.1 분할정복 접근법 재귀적 구조 : 주어진 문제를 풀기 위해 자기 자신을 재귀적으로 여러 번 호출함으로써 밀접하게 연관된 부분 문제를 다룸. => 분할정복 접근법 분할정복 접근법 : 전체 문제를 원래 문제와 유사하지만 크기가 작은 몇 개의 부분 문제로 분할하고, 부분 문제를 재귀적으로 품. 찾은 해를 결합하여 원래 문제의 해를 만들어 낸다. 분할정복의 3단계 ...