학부 수업 정리 (43) 썸네일형 리스트형 [알고리즘] 11. Dynamic Programming (1) 1. Fibonacci Number [Ver 1] 단순 재귀: 이 경우 n이 커질수록 중복 호출되는 경우가 많아져서 시간 복잡도가 지수적으로 증가한다. [Ver 2] 메모이제이션: 계산 결과를 미리 저장해두고 계산한 적이 있다면 재귀 없이 리턴한다. [Ver 3] DP: 재귀 없이 단순히 반복문으로 피보나치 수열을 구할 수 있다. (DP 배열에 이미 계산이 되어 있다고 확신) int DP[1000]; int Fi(int n) { DP[0] = DP[1] = 1; for (int i=2; i [알고리즘] 10. Convex Hull 1. Convex Hull, CCW Algorithm Convex Hull 은 평면좌표에서 어떤 점들이 있을 때 모든 점들을 포함하는 가장 작은 볼록 다각형을 의미한다. (점들의 바깥에서 고무줄을 놨을 때 만들어지는 도형) 점들을 정렬하는 과정이 필요하기 때문에 Convex Hull 을 만드는 알고리즘의 시간 복잡도는 $O(nlog n)$보다 빠를 수 없다. 앞으로 세 점의 관계를 알아낼 때 CCW (Counter Clock Wise) 알고리즘을 사용하는 경우가 많으므로 미리 알아두자. 세 점 $(x_1,y_1), (x_2,y_2), (x_3, y_3)$ 에 대해서 1 -> 2 -> 3 방향으로 이동할 때 아래 값을 이용하여 회전 방향을 판단할 수 있다. $$x_1(y_2-y_3) + x_2(y_2-y_.. [알고리즘] 9. Closest Pair 1. Closest Pair Idea 주어진 점들 중에서 가장 가까운 쌍을 찾는 문제 유형이다. 1차원인 경우에는 단순히 정렬을 통해서 구할 수 있고, 2차원의 경우 두 점 사이의 거리 공식을 이용해 일일이 비교하여 구할 수 있다. 하지만 이 경우 시간 복잡도가 $O(n^2)$이나 걸리므로 분할 정복을 이용하여 효율성을 높일 수 있다. 점들을 x좌표에 따라 오름차순으로 정렬한다. x좌표를 기준으로 배열을 반반으로 분할한다. ($base case: n \le (2$ 이상의 자연수$)$) 왼쪽에서의 답과 오른쪽에서의 답을 각각 $DL, DR$ 이라 하자. 그리고 $D = min(DL, DR)$ 을 구하면서 재귀적으로 합치면 된다. 하지만 왼쪽 영역의 점과 오른쪽 영역의 점이 합쳐진 경우가 존재하여 D가 답이.. [알고리즘] 8. Approximate Median 1. Selection Strategy with Approximate Median $a_1, a_2, ..., a_n$ 중에서 $[rn, (1-r)n]$ 등까지 있는 원소를 찾는다. 예를 들어 $r=0.3, n=100$인 경우 $[30, 70]$ 등 사이에 있는 것들을 Approximate Median 이라고 한다. Selection 문제는 n개의 원소에서 k등(정렬했을때 k번째) 원소를 찾는 것이다. 이때도 pivot을 이용하면 $O(n)$의 시간만에 구할 수 있다. Quick Sort에서 pivot을 기준으로 왼쪽 오른쪽으로 분류한 것과 같이 나눈 뒤 k등이 pivot 보다 왼쪽에 있으면 왼쪽 부분만 재귀적으로 Selection을 수행한다. k등이 pivot보다 오른쪽이면 오른쪽 부분만 재귀적으로 S.. [알고리즘] 7. Merge Sort, Quick Sort 1. Merge Sort와 Merge 알고리즘 Merge Sort는 주어진 배열을 가운데에서 쪼개어 두 개로 만든 뒤 이들을 각각 재귀 호출을 하여 정렬한다. 그 후 정렬된 두 배열을 Merge 알고리즘을 통하여 하나로 합쳐서 정렬된 배열을 얻는다. Merge 알고리즘: 배열 A, B를 병합하여 배열 C에 저장하고자 한다. A, B의 원소들을 가리키는 포인터가 각각 존재한다고 하면 처음에는 그 포인터가 $A[0], B[0]$ 에 존재한다. 배열 C에는 두 포인터가 가리키는 값 중 더 작은 값이 들어가게 되고, 그 값을 가리키던 포인터는 한칸 뒤로 이동하게 된다. 이 과정을 두 포인터가 모두 배열의 끝에 갈때까지 반복한다. 이 알고리즘 자체는 포인터가 이동하면서 n개의 원소를 이동시키므로 $O(n)$이 걸.. [알고리즘] 6. Tape Storage 1. 문제 정의 N개의 Data가 있다. 각 Data는 $D_i=(L_i, F_i)$ 으로 구성되어 있고, $L$은 Length of Data, $F$는 Frequency of Usage를 의미한다. 테이프에는 각 Data들을 단 한번만 쓸 수 있고, 읽는 것은 무제한으로 가능하다. 하지만 모든 읽기 작업은 항상 테이프의 첫부분부터 읽는다. 이때 가장 효율적으로 데이터를 배치하는 방법은 무엇일까? 직관적으로 $L_i$가 짧을수록 앞에 배치하고, $F_i$가 클수록 앞에 배치하는 것이 좋다고 생각할 수 있다. 따라서 $F_i/L_i$의 값이 큰 것부터 내림차순으로 정렬하여 테이프에 쓰면 된다. (Greedy 알고리즘) 2. 정당성 증명 증명에 앞서, $C_i(cost) = f_i\sum_{k=1}^n l_.. [알고리즘] 5. Deadline Scheduling 1. 문제 정의 N개의 Job $J_1, J_2, ..., J_N$이 있다. 각 Job은 $J_i=(D_i, P_i)$ 으로 구성되어 있고, $D$는 Deadline, $P$는 Profit을 의미한다. 1시간 단위의 타임 슬롯이 존재하고, 모든 일은 1시간이 소요된다고 가정하자. 이때 가장 Profit을 많이 얻을 수 있는 스케줄링 방법은 무엇일까? 모든 데드라인은 $N$ 이하라고 가정. ($\because N$보다 크면 $N$으로 바꿔 생각해도 아무 문제가 없음) Job들은 Profit이 큰 것부터 작은 순으로 내림차순 정렬되어 있는 상태라 가정. 최적 스케줄에선 데드라인 이후의 일은 안 나온다고 가정. 직관적으로, 높은 이익의 일들을 먼저 빈자리들 중 가장 뒤에 배치하는 것이 제일 효율적이라고 생각할.. [알고리즘] 4. 최단 거리 - Dijkstra 알고리즘 1. Shortest Path Shortest Path (이하 $S.P.$) 문제는 Source (시작점) 부터 다른 모든 노드로 가는 $S.P.$를 구하는 것이 목적이다. 예를 들어 서울에서 부산까지의 $S.P.$에는 서울과 부산 사이에 지나가는 모든 지역까지의 $S.P.$도 포함되어 있다. 즉, $S.P.$의 모든 부분은 $S.P.$이다. Versions of S.P. - 각 노드별 $S.P.$의 길이만 구하기 - 각 노드별 실제 $S.P.$ 구하기 - 각 노드별 모든 가능한 $S.P.$ 구하기 2. Dijkstra 알고리즘의 Idea 용어 정의 - $G = (V, E)$: 그래프 입력 - 정점과 엣지들 - $n$: 노드의 총 개수 - $v_0$: Source Node - $d_{min}$: $S.P.. 이전 1 2 3 4 5 6 다음
