최악의 경우에도 선형 시간에 중간값 을 선택할 수 있는 알고리즘은 다음과 같다. 아래는 median을 찾는 예이지만, k번째 작은 값 찾는 문제에 적용 가능하다. Element select(SetOfElements S, int k) 중앙값만 찾는 거라면 k 파라미터가 필요 없지만, 일반적인 선택 문제로 확장하면 k 파라미터가 필요함. k는...

min, max 모두 찾을 때 조금 더 효율적인 방법 배열에서 최댓값과 최솟값을 모두 찾는 단순하고 일반적인 방법은 최대키, 최소키를 각각 찾는 방법이다. 이런 방식은 최대키를 찾는데 \(n-1\)번 비교, 최소키를 찾는 문제도 이와 같으므로 총 \(2n-2\)번 비교하게 된다. 다음과 같은 방법을 사용하면 최댓값과 최솟값을 모두 찾는데 \(3\lf...

5개의 원소를 7번 비교로 정렬하기 정렬의 lower bound는 \(\lceil\lg{n!}\rceil\)이므로, 5개의 원소를 정렬하려면 최악의 경우 최소 7번은 비교해야 한다. (quick, merge, heap 모두 최악의 경우 8번 비교하게 된다.) 최악의 경우에도 7번만 비교하는 알고리즘의 핵심은 이미 정렬된 부분에 대해서 binary s...

## Celsius to fahrenheit .data msg: .asciiz "Enter celsius : " const9: .float 9.0 const5: .float 5.0 const32: .float 32.0 zeroF: .float 0.0 .text .globl main main: ## Expand stack...

조건부 확률 사건 B가 일어났다는 전제 하에 사건 A가 일어날 확률. 사건 B가 이미 일어났으니 \(P(B)\)를 전체로 보고 \(P(A \cap B)\)를 구하면 된다. \[P(A|B) = \frac{P(A \cap B)}{P(B)}\] * 이를 이용해 A, B가 독립이면 \(P(A \cap B) = P(A)P(B)\)를 유도할 수 있다. ** \(...

\(f(n) = \Theta(g(n)) \approx a = b\) \(f(n) = O(g(n)) \approx a \le b\) \(f(n) = \ o(g(n)) \approx a < b\) \(f(n) = \Omega(g(n)) \approx a \ge b\) \(f(n) = \omega(g(n)) \approx a > b\) ...

\(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …\) 피보나치 수 는 다음 점화식으로 정의된다. \(F_0 = 0\) \(F_1 = 1\) \(F_i = F_{i-1} + F_{i-2}\qquad(i \ge 2)\) 보통 피보나치 수를 구할 때 앞에서부터 두항 씩 더해 구해나갈텐데, 다음 성질을 이용해서 구하는 방법도 있다...

특징 폰 노이만 성님이 개발함. in-place 정렬이 아닌 대표적인 정렬 알고리즘. 정렬된 결과가 저장될 리스트가 1개 더 필요하니까 배열 크기 만큼의 공간 n이 하나 더 있어야 하는 것인데… 잘 짜면 n/2 만큼만 더 사용하도록 할 수도 있음. 외부 정렬도 가능 (메모리에 정렬 대상을 다 ...

ER 스키마 » 릴레이션 사상 간단한 요소에서 복잡한 요소 순으로 사상한다. 단계 1: 정규 엔티티 타입 단계 2: 약한 엔티티 타입 단계 3: 2진 1:1 관계 타입 단계 4: 정규 2진 1:N 관계 타입 단계 5: 2진 M:N 관계 타입 단계 6: 3진 관계 타입 단계 7: 다치 애트리뷰트 정규화 Normalizat...

Quicksort 기본 동작 방식 ko.wikipedia.org/wiki/퀵 정렬 일단 기본적인 동작 방식은 이걸 참고. en.wikipedia.org/wiki/Quicksort 목차를 보면 영문 위키가 더 상세하다. pivot 고르는 법, 다양한 퀵소트 wiki/Sorting_algorithm#Comparison_of_algorithm...