학부 수업 정리/알고리즘 (21-2) (16) 썸네일형 리스트형 [알고리즘] 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.. [알고리즘] 3. MST - Kruskal 알고리즘 1. Kruskal 알고리즘의 Idea 모든 Edge들을 weight가 작은 순서부터 대입하기 (No Cycle) Spanning Tree가 될때까지 이 과정을 반복 (최종적으로 node $n$개 - edge $n-1$개가 되어야 함) 2. Kruskal 알고리즘의 정당성 증명 - 입력 그래프: $G = (V, E)$ - Edge Set인 $T_{mst}$ 는 정답 중 하나라고 가정 - 알고리즘이 끝난 후 Prim 알고리즘이 가지고 있는 edge set $T$는 $T_{mst}$가 될 것이다. ※ 주의사항: $T_{mst}$는 증명 중간에 바뀔 수 있기 때문에 미리 잡고 시작할 수 없다. 하지만 정답이라는 사실은 항상 유지된다! $\exists\ T_{mst} \rightarrow T \subseteq .. [알고리즘] 2. MST - Prim 알고리즘 1. Minimum Spanning Tree (MST) Spanning Tree는 그래프의 모든 정점과 간선의 부분집합으로 구성된 부분 그래프이다. MST는 주어진 그래프의 연결 그래프들 중 엣지들의 비용이 최소가 되도록 하는 그래프를 의미한다. (단, 사이클을 생성하지 않아야 한다.) 2. Prim 알고리즘의 Idea 아무 노드 중 하나의 노드를 가진 트리에서 시작 트리에 인접한 edge들 중에서 가장 작은 weight를 가진 edge를 추가 (단, 사이클을 만들지 않아야 함) Spanning Tree가 될때까지 이 과정을 반복 (최종적으로 node $n$개 - edge $n-1$개가 되어야 함 3. Prim 알고리즘의 정당성 증명 - 입력 그래프: $G = (V, E)$ - Edge Set인 $T_{.. [알고리즘] 1. 수학적 귀납법과 재귀 1. 수학적 귀납법 $P(1)$ 이 참이고, $P(n-1) \xrightarrow{} P(n)$ 이 참이면 $P(n)$ 은 모든 자연수 $n$ 에 대해서 참이다. $P(n-1)$ 이 참이라고 가정하는 이유: $P(n-1)$ 이 거짓이면 $P(n-1) \xrightarrow{} P(n)$ 전체가 Vacuously True 이므로 할 말이 없다. 2. Recursive Sum Function int sum(int x) { if (x x) return search(a, m-1, x); else { int r = search(a+m+1, n-m-1, x); if (r == -1) return -1; else return r + m + 1; } } For some i, if $a[i] = x$, search() .. 이전 1 2 다음
