Coursera 에서 제공하는 Stanford 대학교의 Algorithm Design & Analysis 수업 중 3 번째 챕터입니다. 이번엔 지난시간에 배운 randomized algorithm 을 새로운 domain 인 그래프에 적용해 보고, contraction algorithm 이 무엇인지 알아본다. Graphs 용어 정리부터 시작하자. edge (E) 는 pair of vertices 와 같은 말이다. (E) 는 directed or undirected 일 수 있으므로 unordered pair 또는 … Continue reading Algorithm Design & Analysis 3 – Graphs, The Contraction Algorithm
Coursera 에서 제공하는 Stanford 대학교의 Algorithm Design & Analysis 수업 중 2 번째 챕터입니다. Intuition 중복이 없는 n 개의 원소를 가진 배열에서 i 번째로 큰 원소를 얻고 싶다고 하자. 간단한 방법은 먼저 정렬을 한 뒤 거기서 i 번째 원소를 고르면 된다. 이 방법을 reduction 이라 부르는데 selection 문제를 sorting 문제로 바꾸어 푼 것이다. 이 경우 … Continue reading Algorithm Design & Analysis 2 – Randomized Selection
Coursera 에서 제공하는 Stanford 대학교의 Algorithm Design & Analysis 수업 중 1 번째 챕터입니다. Divide and Conquer (분할 정복) 을 배운다. merge, quick sort 를 배우고 이 과정에서 왜 combine 단계가 O(n) 이 되어야 하는지 알아본다. 뒷부분에서는 Big O 뿐만 아니라 master method, decomposition approach 를 이용해 성능을 분석한다. Divide and Conquer 각 level 의 … Continue reading Algorithm Design & Analysis 1 – Divide And Conquer
Coursera 에서 제공하는 Princeton 대학교의 Algorithm 수업인 Algorithm Part 1 의 8 번째 수업입니다. Data Compression 주된 이유는 전송 시간과 저장 공간을 절약하기 위해서다. 무어의 법칙이 말해주듯이 제품의 성능은 점점 좋아지는데, 그럼에도 불구하고 사람들이 만들어 내는 데이터의 양은 더 급격히 증가한다. 그래서 압축이 필요하다. 이번시간에 배울 기법은 3 가지다. Run-length Huffman LZW data compression 응용은 … Continue reading Algorithm 8 – Data Compression, Huffman, LZW
Coursera 에서 제공하는 Princeton 대학교의 Algorithm 수업인 Algorithm Part 1 의 7 번째 수업입니다. Min Cut edge weighted 그래프에서 st-cut 이란 vertices 를 두개의 disjont sets 으로 나누는 것이다. 이때 s, t 는 각각 다른 집합 A, B 에 속해있다. (http://en.wikipedia.org) capacity 란 컷으로 나뉘어진 두 집합 A, B 를 기준으로 A 에서 B 로 … Continue reading Algorithm 7 – Maximum Flow (Ford-Fulkerson)
1ambda 