1주 차
(Q) 이진 탐색(binary search)에 대해 조사한 후 간단히 요약하여 제출하시오.
1회전시 비교범위가 1/2로 줄어든다는 점에서 강력한 성능을 발휘할 수 있지만
탐색 전 모든 숫자들이 정렬되어 있어야 한다는 제약조건이 있기 때문에 정렬이 되어있는
상황에 맞춰서 좋은 효율을 낼 수 있다.
3주 차
복잡도의 점근적 표기에 대해 수업시간에는 O(Big-oh)-표기를 공부하였습니다. 또 다른 점근적 표기법인 o(small-oh)-표기에 대해서 조사한 후 간단하게 요약하여 제출하시오.
Small - O는 Big - O 에서 등호를 빼면 된다.
O(n)의 최악의 경우에도 n번 미만으로 수행이되면 프로그램은 끝낼 수 있게 된다.
또한 기존 Big - O는 실수 c > 0 중에서 하나만 성립해도 됐지만, Small - O는 모든 실수 C>0에 대해서 성립해야 한다는 점에서 차이를 둔다.
4주 차
퀵 정렬을 복습한 후 (1) 최악 경우 시간복잡도, (2) 최선 경우 시간복잡도, (3) 평균 경우 시간복잡도를 big-oh 표기법으로 나타내시오.
1). 최악의 경우 시간복잡도 => 피봇으로 가장 작은 값 or 가장 큰 숫자가 선택될 경우
(n -1) + (n - 2) + (n - 3) + ... + 2 + 1 = n (n - 1)/2 = O(n^2)
2). 최선의 경우 시간복잡도 => 각 층에서 1회씩 비교
O(n) x 층수 => O(n log n)
3). 평균의 경우 시간복잡도
O(n log n)
5주차
분할 정복을 적용하는 데 있어서 주의할 점을 간단히 요약하시오 (3.5장)
주의할 점
첫 번째, 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생하며,
스택에 다양한 데이터를 보관하고 있어야 하므로 stack overflow가 발생하거나 과도한 메모리 사용을 하게 될 수 있다.
두 번째, 입력이 분할될 때마다 분할된 부분문제의 입력 크기의 합이 분할되기 전의 입력 크기보다 매우 커지는 경우, 즉 피보나치 수를 구함에 있어서 분할 정복을 사용하는 경우 반복문을 사용하는 것이 더 바람직하다.
6 주차
두 가지 최소 신장 트리 알고리즘인 크러스컬 알고리즘과 프림 알고리즘을 비교하여 간단히 설명하시오.
프림의 알고리즘 시간 복잡도는 O(n^2)이며, 크루스칼 알고리즘의 시간 복잡도는 O(n log n)이다.
따라서, 그래프 내에 적은 숫자의 edge만을 가지는 Sparse Graph의 경우 크루스칼 알고리즘이 적합하고 그래프에 간선이 많이 존재하는 Dense Graph의 경우는 프림 알고리즘이 적합하다.
7주 차
Reverse-Delete Algorithm에 대해서 간단히 설명하시오.
(오타: 강의동영상에서 Reverse-Delete Algorithm을 Reserve-Delete Algorithm으로 잘못 표기하였으니 수정바랍니다.)
Reverse-Delete Algorithm 최소 신장 트리를 얻기위해 사용된다.
그래프가 끊어져있어도 그래프의 끊어진 각 부분에 대한 최소 신장트리를 찾으며 이를
minimum spanning forest라고 부른다.
이 알고리즘은 어떤 상황에서든 최선의 선택을 하는 Greedy 알고리즘이며, Kruskal 알고리즘의 반대 알고리즘이라고 생각하면 된다.
8주 차
이번주에 학습한 다음의 2가지 알고리즘을 복습한 후 각 알고리즘의 시간복잡도를 적어서 제출하시오.
1) 집합 커버 문제 (SetCover)
- 최적해를 찾는 대신에 최적해에 근접한 근사해(approximation solution)을 찾는 문제다.
보통 집합 문제의 최적해를 찾는 데는 지수 시간이 걸리지만, SetCover알고리즘은 O(n^3) 시간에 근사해를 찾을 수 있고, 그 값도 실질적으로 최적해와 비슷하다.
2) 작업 스케줄링 알고리즘 (JobScheduling)
- 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제이다. n개의 작업을 정렬하는데 O(n log n) 의 시간이 걸리고, while 루프의 총 횟수에 따라 O(mn)의 시간이 소요된다.
즉 JobScheduling 알고리즘의 시간복잡도는 O(n log n) + O(mn) 이다.
9주 차
힙 자료구조에서 삽입 연산의 시간복잡도는 얼마이며 그 이유는 무엇인지 간단히 설명하시오.
힙 자료구조에서 삽입 연산의 시간복잡도는 O(log n)이다.
최악의 상황에서 삽입 되는 값이 힙의 최정상(루트)에 저장된다면 힙의 높이가 logn이니
O(log n)의 시간복잡도가 나온다
10주 차
AllPairsShortest 예제 k=4일 때 3개의 원소가 갱신되는 것에 대해 설명하시오.
(참고) p.22에서 3개의 값이 갱신되는 식을 p.17의 D[4 2]와 같이 설명하면 됩니다. (그림은 선택)
k = 4 일 때,
D[2,1] = min{D[2,1],D[2,4]+D[4,1]} = min{2, 0} = 0
D[3,1] = min{D[3,1],D[3,4]+D[4,1]} = min{1, -1} = -1
D[5,1] = min{D[5,1],D[5,4]+D[4,1]} = min{-1, -3} = -3
셋 다 갱신
11주 차
행렬의 곱셈 A x B = C 에서 행렬 A의 크기가 d0 x d1 이고, 행렬 B의 크기가 d1 x d2 인 경우 다음 물음에 답하시오.
(1) C의 크기는 얼마인가요? ( ) x ( )
(2) A x B를 계산하기 위해서는 원소간 곱셈이 몇 번 필요한가요? ( ) x ( ) x ( )
-> (1). C의 크기 : d0 x d2
-> (2) 필요한 원소간 곱셈 회 수 : d0 x d1 x d2 번
12주 차
5.4 배낭 문제 Knapsack 알고리즘과 5.5 동전 거스름돈 DPCoinChange 알고리즘을 복습한 후 각각의 시간복잡도를 big-oh 표기로 간단히 설명하시오.
(1). Knapsack 알고리즘
- 주어진 배낭의 용량에 따른 물건의 최대 가치를 찾는 알고리즘이다.
시간복잡도 : 부분문제의 총 수는 배열 K의 원소 수인 N x C개이다. 총 시간복잡도는 O(1) x n x C 이니 O(nC)이다.
(2). DPCoinChange 알고리즘
- 최대한 적은 수의 동전으로 거스름돈을 받기 위한 알고리즘
시간복잡도 : 거스름돈 J가 1 ~ n까지 변하며, 각각의 J에 대해 최악의 경우 모든 동전을 1번씩 고려해야 한다고 보면 O(nk)이다.
13주 차
(3) 삽입 정렬
- 입력값들 정렬되어 있다면 원소의 이동이 없게된다. 따라서 (n - 1)번의 비교만 하면 정렬을 마치게 되고 이 경우가 바로 최선의 경우이다. 시간복잡도는 O(n)이 나온다.
14주 차
(Q) 내부정렬과 외부정렬에 대해서 간단히 비교 설명하시오.
내부정렬 : 입력의 크기가 주기억 장치의 공간보다 크지 않은 경우에 수행되는 정렬이다. 이전의 모든 정렬 알고리즘들이 해당된다.
외부정렬 : 내부정렬과는 다르게 입력 크기가 매우 커서 읽고 쓰는 시간이 오래 걸리는 보조 기억 장치에 입력을 저장할 수 밖에 없는 상태에서 수행되는 정렬을 일컫는다.
