본문 바로가기

Basic Learning/Algorithm Design

Approximation Algorithms * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Approximation Algorithm이란 최적의 결과를 제공해주지는 않지만 최적에 가깝고 어느 정도의 결과를 보장해주는 알고리즘이다. Load Balancing m개의 machine과 n개의 job이 있다. 그리고 각 job은 $t_j$라는 processing time을 가지고 있다. 여러개의 job이 하나의 machine에 할당되었을 때, 다음으로 load를 정의한다. $L_i = \sum{t_j}$ 모든 machine에 대한 load의 최대 값을 makespan이라 한다. makespan $L = max_i L_i$ Makespan을 최소화하는 문제를 Load balancing 문제이다. List-scheduling a.. Basic Learning/Algorithm Design 2020. 12. 8.
NP and Computational Intractability * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. NP (Nondeterministic Polynomial-time) Decision problem X는 set of strings, $X : A(s) =$ yes / no $iff \in X$ X는 dicision problem이고, A는 decision problem을 푸는 알고리즘이다. 즉, input이 들어갔을 때, yes/no로 답하는 문제를 decision problem이라 한다. 대표적으로 어떤 숫자가 소수인지 아닌지를 검사하는 문제가 있다. Polynomial time 모든 s에 대해 알고리즘을 돌렸을 때, input size에 대해 polynomial 시간에 돌아갈 수 있으면, 이 알고리즘은 polynomial-t.. Basic Learning/Algorithm Design 2020. 12. 7.
Polynomial-Time Reductions * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Polynomial-Time Reductions 만약, Problem X가 polynomial-time에 풀 수 있는 알고리즘을 가지고 있다 하자. 그리고 problem Y는 이 알고리즘을 이용하여 풀 수 있다면 Problem Y는 polynomial-timem reducible 이다. 아래와 같이 기호로 표기한다. $Y \le_P X$ X가 poly-time으로 풀린다면 Y 또한 poly-time으로 해결된다. 이는 문제의 상대적 어려움을 뜻한다. $Y \le_P X$ 이고, $X \le_P Y$ 이면, $X \equiv_P Y$로 표시한다. Claim VERTEX-COVER $\equiv_P$ INDEPENT-SET INDE.. Basic Learning/Algorithm Design 2020. 11. 27.
Maximum Flow and Minimum Cut * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Minimum Cut Problem Source와 Sink가 존재하는 directed graph를 flow network라 한다. 각 edge는 capacity를 가진다. 아래 그림과 같이 cut을 정했을 때 cut의 capacity 합이 최소값을 찾는 문제를 Minimum cut problem이라 한다. Maximum Flow Problem Flow는 capacity 내에서 흐를 수 있는데, source부터 sink까지 흐를 수 있는 최대 flow를 찾는 문제를 Maximum flow problem이라 한다. Cut을 기준으로 나가는 edge와 들어오는 edge를 통해 flow를 계산할 수 있다. Weak duality flo.. Basic Learning/Algorithm Design 2020. 11. 11.
Dynamic Programming * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Greedy : 근시안적으로 그때 그때 좋은 상태를 선택 Divide-and-conquer : 문제를 sub-problem으로 break up하여 독립적으로 해결 Dynamic programming : 문제를 overlapping sub-problem으로 break up Weighted Interval Scheduling 각 job들은 weight를 가지고 있음. 각 job이 같은 시간에 overlap하지 않으면서 maximum weight subset을 찾는 문제이다. 모든 weight가 1일때에는 Interval scheduling 문제이므로 greedy algorithm으로 해결 가능. 하지만, weighted interv.. Basic Learning/Algorithm Design 2020. 11. 9.
Closest Pair of Points * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Closest Pair of Points n개의 point들이 2D plane에 놓여져있을 때, 두 point사이의 거리가 가장 짧은 pair를 찾는 문제이다. 1D line상에 나열되어있는 것은 $O(nlogn)$으로 자명하다. 가정 : x 좌표가 같은 두개의 점은 없다. 접근 : Divide : 양쪽 점의 개수가 n/2가 되도록 vertical line을 긋는다. Conquer : 각 영역의 closest pair를 찾는다. Combine : 각 영역의 closest pair 2개와 두 영역간의 closest pair 중 거리가 짧은 것을 반환한다. 이 알고리즘에서 Combine 하는 과정이 핵심이다. 두 영역간의 모든 조합.. Basic Learning/Algorithm Design 2020. 10. 22.
Mergesort & Counting Inversions * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Mergesort array를 반으로 나누어 2개의 array를 만든다. 각 array에 대해 recursive하게 sort를 진행한다. Sort된 두개의 array를 이용하여 하나의 큰 sorted array로 merge한다. 두개의 array가 sort되었다고 가정하므로, 각 array에 대해 왼쪽에서 오른쪽으로 진행하면서 comparison을 진행하면된다. 그 결과, merge에 $O(n)$의 시간이 걸린다. Mergesort recurrence n을 2의 지수승이라 하면 다음과 같다. Time complexity : $O(nlogn)$ Proof by recursion tree Recursion을 tree로 표현할 수 있.. Basic Learning/Algorithm Design 2020. 10. 20.
Huffman Coding * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Prefix Code Symbol을 인코딩하는데 있어, 고정된 길이로 인코딩할 수 있지만, symbol 빈도수가 클수록 길이를 작게한다면 더 효율적일 것이다. Huffman coding은 symbol frequency가 주어졌을 때, symbol에 code를 할당하는 알고리즘이다. Prefix code : 1, 0으로 이루어진 code에서, 하나의 code가 다른 하나의 prefix가 되지 않는 code이다. ABL (Average Bits per Letter) Prefix code는 아래 그림과 같이 tree의 leaves에 할당함으로써 표현할 수 있다. 중간 노드에 할당이 될 수 없는데, 할당되면 아래 노드의 prefix가 .. Basic Learning/Algorithm Design 2020. 10. 17.

티스토리툴바