본문 바로가기

알고리즘/추가 자료5

Graph Solve the exercise problem 14 of the chapter 7 합병 정렬은 크게 분할, 정복, 합병으로 구성되어 있다. 이때 레코드 저장 횟수를 계산하기 위해서는 각 과정에서 레코드가 저장되는 횟수를 살펴보아야 한다. 1. 분할 과정 입력 배열을 반으로 나누는 과정에서는 레코드 저장이 필요하지 않기에 레코드 저장 횟수는 0이다. 2. 정복 과정 각각 작은 배열을 정렬하는 과정에서 레코드를 저장한다. 이때, 레코드 저장 횟수는 배열의 크기에 비례하기 때문에 작은 배열의 크기가 k인 경우 레코드 저장 횟수는 2klogk(양쪽 배열의 레코드 저장 횟수)이다. 3. 합병 과정 정렬된 작은 배열을 합병하여 더 큰 배열을 만들 때 레코드 저장이 필요하다. 두 배열의 요소를 비교하면서 더 작은 .. 2023. 4. 11.
Quick Sorting & Hash function 1. Describe linear median finding algorithm, Show that its time complexity is Θ(n) 일반적인 quick sort의 시간 복잡도는 최선일 때 O(nlogn)이고, 최악일 때 O(n^2)만큼 걸린다. 수열의 길이가 n일 때 알고리즘의 수행 시간의 기댓값을 T(n)이라고 하자. 수열이 a1, ... , an으로 주어졌을 때, 이를 오름차순으로 정렬한 것을 b1, ... , bn이라고 하면 {a1, ... , an} = {b1, ... , bn}고, b1 < ... < bn 이다. 만약 알고리즘이 단계 2에서 x = b_j+1을 골랐다고 하자. 그러면 |A < x| = j이고 |A ≥ x| = n − j가 된다. 따라서 다음 재귀 호출에서 살아 남.. 2023. 4. 1.
Direct Access Array & Sorted Array & Tree Tree n개의 노드가 존재할 때 가장 작은 tree의 높이가 Ω(log2 n) = log2(n+1) - 1임을 증명해보자. 높이가 가장 작은 트리를 만들기 위해서 완전 이진 트리이면 된다. 완전 이진 트리의 경우 자식이 생길때마다 노드가 2개씩 증가하게 되며, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다. Inductive Proof 트리의 시간 복잡도를 T(n) = clog2 n이라고 가정했을 때, clog2 n = clog2 (n+1) - O(1)이 된다. O(1) = clog2 (1+1/n)이 되며, n의 값이 커질수록 O(1)의 값은 0에 수렴하기 때문에 tree의 높이는 Ω(log2 n) = log2(n+1) - 1 식을 만족한다. Direct Access Array 배열의 인덱스와.. 2023. 3. 21.
Time complexity & Birthday problem with sorting Time Complexity Problem 이 문제는 아래 코드를 보고 시간 복잡도를 구하는 문제이다. 이 문제는 while문의 i와 j 형태를 보고 전반적인 시간 복잡도를 구할 수 있다. 34) What is the time complexity T(n) of the nested loops below? For simplicity, you may assume that n is a power of 2. That is, n = 2k for some positive integer k. i = n ; while ( i >= 1) { → log2 n j = i ; while ( j //Needs ( 1 ) j = 2 * j; → 안쪽 while문에서는 j에 2를 곱해주기 때문에 while문 반복 횟수가 2배 줄어든.. 2023. 3. 12.
Birthday Problem Birthday Problem 소개 생일 문제는 그룹내 무작위로 선택된 적어도 두 명의 사람이 같은 생일을 공유할 확률을 구하는 문제이다. Birthday Calculate 그룹 내에서 N명의 사람들 중 적어도 두 사람의 생일이 같을 확률을 구하는 문제인데, 이 문제는 직관적으로 생일이 같은 사람들의 모든 경우의 수를 구하기에는 접근이 어렵기 때문에 좀 더 간단한 방식을 이용하려 한다. (접근이 어려운 이유는 2명보다 더 많은 사람들이 같은 생일을 공유하고 있을 확률도 모두 고려해야하기 때문이다.) 그 방식은 전체 확률에서 그룹 내 모든 사람의 생일이 다를 확률을 빼서 구할 수 있다. 그러면 아래 예시를 통해 계산 방법을 확인해보자. Step 1. 비교할 두 사람의 생일이 다를 확률 구하기: '김'이 6.. 2023. 3. 4.

티스토리툴바