이번 글에서는, 유명한 greedy 알고리즘에 대해 살펴볼 것이다. 1. Single-source shortest paths Problem source vertex(=s)에서 그 외 나머지 vertex까지의 최소 경로를 구하는 문제다. 이 문제의 핵심은 다음과 같다. "최소 경로의 하위 경로도 최소 경로"다!! Approach (Dijkstra's algorithm) 빈 F, Y에서 시작해 T가 MST가 될 때까지 edge를 순차적으로 추가한다. selection procedure: "V-Y의 vertex 중 s와 가장 가까운 vertex(=v)"를 선택한다. feasibility check: 바로 v와 Y를 잇는 edge(=$e$)를 T에 추가하고, v를 Y에 추가한다. (왜냐하면, $e$를 추가한 T..

이번 글에서는, greedy 접근법에 대해 살펴볼 것이다. Geedy algorithm Definition Greedy 접근법은 항목(=item)의 연속적인 선택을 기반으로 문제를 푼다. 이때, 선택되는 항목은 "현재 선택 가능한 항목 중에서 가장 좋은 항목"이다. Approach Greedy 알고리즘은 빈 집합(=S)에서 시작해 instance의 solution이 될 때까지 항목을 순차적으로 추가한다. selection procedure: "현재 선택 가능한 항목 중 가장 좋은 항목(=item)"을 선택한다. feasibility check: S ∪ {item}이 solution이 될 수 있는지 점검한다. 만약 될 수 있다면, S에 item을 추가한다. solution check: S가 solution..

이번 글에서는, dynamic programming 기법을 활용한 유명 알고리즘에 대해 살펴볼 것이다. 1. Chained Matrix Multiplication 다음과 같은 행렬 곱을 생각해보자. $$\underset{20 \times 2}A \quad \times \underset{2 \times 30}B \quad \times \underset{30 \times 12}C \quad \times \underset{12 \times 8}D$$ 어느 순서로 행렬 곱을 하든, 결과는 같다. 하지만 연산 횟수에는 영향을 준다. $$A(B(CD)) \rightarrow 3680 \\ (AB)(CD) \rightarrow 8880 \\ A((BC)D) \rightarrow 1232 \\ ((AB)C)D \rig..

이번 글에서는, divide-and-conquer와 매우 비슷한 기법인 dynamic programming에 대해 살펴볼 것이다. Dynamic Programming Definition divide-and-conquer와 개념이 매우 흡사하다. 작은 instance(s)의 solution을 기반으로 original instance의 solution을 푼다. 이때, 작은 instance(s)의 solution(s)을 저장하여, 중복 계산을 방지한다. Approach dynamic programming 알고리즘은 다음 2단계 절차를 기반으로 설계돼야 한다. 작은 instance(s)의 solution으로 original instance의 solution을 구하는 재귀 속성($\approx$점화식)을 찾는다...

이번 글에서는, divide-and-conquer 기법을 활용한 유명 알고리즘에 대해 살펴볼 것이다. 1. Quicksort Problem 정렬 문제다. 즉, 크기가 n인 배열(=S)을 정렬하는 문제다. Algorithm pivot item(=S[0])으로 배열 S를 partition(=분할)한다. pivot item보다 작으면 pivot 왼쪽으로 이동 pivot item보다 크면 pivot 오른쪽으로 이동 분할된 2개 부분 배열을 각각 정렬한다. (만약, 부분 배열을 더 분할할 수 있다면, 재귀를 통해 정렬한다.) 정렬된 부분 배열 2개와 pivot item을 연결시켜, original 배열을 정렬한다. Analysis base operation: pivot item과 S[i]간의 비교 연산 input..

이번 글에서는, 알고리즘 설계 시 사용되는 접근법들 중 하나인 divide-and-conquer에 대해 살펴볼 것이다. Divide-and-Conquer Definition divide-and-conquer는 instance를 작은 instance(s)로 쪼개 푼 것을 기반으로, original instance를 푼다. Approach divide-and-conquer 알고리즘은 다음 3단계 절차를 기반으로 설계돼야 한다. (문제의) instance를 (같은 문제의) 작은 instance(s)로 쪼갠다.(즉, 정렬 instance를 작은 정렬 instance로 쪼갠다.) 작은 instance(s)를 푼다. (이때, 작은 instance를 더 쪼갤 수 있다면, 재귀를 통해 푼다.) 작은 instance(s..