본문 바로가기

학부 수업 정리/알고리즘 (21-2)

 (16)
[알고리즘] 16. LCA, Boruvka's Randomized MST Algorithm 1. LCA (Lowest Common Ancestor) Preprocessing 모든 노드에 레벨 정보가 기록된 트리에서 두 노드 a, b의 최소 공통 조상 x를 찾아보자. 먼저 각 노드들이 1, 2, 4, 8, 16, ..., $2^j$ 칸 위의 조상의 번호를 저장하는 과정이 필요하다. $\texttt{A[i][j]}$ 는 $i$번 노드의 $2^j$ 칸 위의 조상의 번호를 저장한다. 이때 $j$의 값은 0부터 $log n$까지이다. Base: $\texttt{A[i][0]}$: 나의 부모의 ID 값 Step: $\texttt{A[i][j+1] = A[A[i][j]][j]}$: 모든 노드가 $2^j$ 칸 위의 ID를 안다고 가정하면 $2^{j+1}$칸 위의 ID는 $2^j$칸 위로 올라간 뒤 ($\te..
[알고리즘] 15. Topological Sort, SCC DAG는 사이클이 없는 방향 그래프를 의미한다. (한 점에서 출발해 자기 자신으로 돌아오는 경로가 존재하지 않는 경우) 1. Topological Sort 위상 정렬은 DAG의 노드들을 왼쪽에서 오른쪽 방향(엣지 방향이 모두 오른쪽) 으로 정렬하는 것을 의미한다. DAG에 사이클이 존재하지 않으면 알고리즘은 항상 성공한다. DAG G에서 indegree = 0 인 노드 $x$를 제거한 그래프를 $G'$ 이라고 하자. (DAG에서 일부를 제거해도 DAG이다.) $G'$에서 Topological Sort 알고리즘을 다시 반복하면 재귀적으로 정렬이 완료된다. $x$의 indegree가 0이기 때문에 $x$에서 $G'$ 사이에는 모두 왼쪽에서 오른쪽 방향 Edge만 존재한다. 즉 재귀적으로 위상 정렬이 된 DA..
[알고리즘] 14. Cut Vertex 1. Cut Vertex 알고리즘 Cut Vertex (절단점)는 제거할 경우 그래프가 끊어지게 되는 노드를 의미한다. 각 노드마다 노드를 지우고 그래프가 끊어졌는지를 확인하면 $O(mn)$의 시간이 걸리게 된다. 하지만 DFS를 돌리고 DFS Tree를 생성하면 $O(m+n)$만에 절단점을 찾을 수 있다. Root Cut Vertex DFS Tree의 루트가 2개 이상의 자식을 가지면 Cut Vertex임을 보이자. 루트에 연결된 서브트리들 중 두개를 각각 S1, S2라 하자. S1에 포함된 노드 중 하나를 x, S2에 포함된 노드 중 하나를 y라 하자. x에서 y로 가기 위해서 x는 S1을 벗어나야 한다. Tree Edge만 사용할 경우: 이 경우 Root를 반드시 거칠 수 밖에 없다. Tree Ed..
[알고리즘] 13. Graph Traversal, Edge의 종류 1. Any-Order Traversal Anyorder Traversal: 어떤 노드 s에서 시작하고 s를 BOX에 넣는다. BOX가 비어있지 않으면 아래의 과정을 반복한다. 하나의 노드를 꺼내고 방문하지 않은 노드라면 방문한 뒤 어떤 계산을 수행한다. 그리고 노드와 인접한 모든 엣지들을 BOX에 넣는다. 이후 이 과정을 계속 반복한다. AnyOrder Traversal이 Reachable한 노드는 모두 방문한다는 것을 증명하자. 노드 t가 s에서 reachable 하다고 가정하자. (Box에 들어가는 노드는 모두 reachable 하다는 것은 invariant 이다.) $t=s$인 경우 s를 방문하는 것이 t를 방문하는 것이므로 성립한다. $s\rightarrow a_1 \rightarrow a_2 ..
[알고리즘] 12. Dynamic Programming (2) 6. 편집거리 (Edit Distance) 문제 정의: 편집 거리는 한 문자열을 다른 문자열로 변경하기 위해 필요한 편집 연산들의 최소 수를 의미한다. 연산의 종류는 [삽입, 삭제, 교체, 유지]가 있다. Idea: $D(i,j)$는 두 문자열 $S_1,\ S_2$ 에 대한 편집거리를 나타낸다고 하자. 제일 오른쪽 문자부터 비교를 하면서 연산들 중 값이 가장 작아지는 것을 고르면 된다. $D(i, j)$의 값은 아래 4가지 값들 중 가장 작은 값이다. $D(i, j-1) + 1$ - 삽입 $D(i-1, j) + 1$ - 삭제 $D(i-1, j-1) + diff(i, j)$ - 같으면 유지(0), 다르면 교체 (1) 7. LCS (Longest Common Subsequence) 문제 정의: 부분 서열 (..
[알고리즘] 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가 답이..

티스토리툴바