본문 바로가기

프로그래밍

 (105)
5. Shortest Paths Shortest path 문제는 edge-weighted digraph가 주어졌을 때, s에서 t로 가는 최단 경로를 찾는 문제이다. 네비게이션, 네트워크 라우팅 등 여러 응용에 쓰인다. 여기서는 하나의 출발지에 대한 모든 다른 지점까지의 shorest-path를 계산하는 single-source shorest paths에 대해 고려할 것이다. 1. APIs Weighted directed edge의 API는 다음과 같다. DirectedEdge(int v, int w , double weight) int from() int to() double weight() EdgeWeightedDigraph의 API는 다음과 같다. EdgeWeightedDigraphp(int V) void addEdge(Dired..
4. Minimum spanning tree(MST) Mininum spanning tree란 weight를 가진 undirected graph가 주어졌을 때, 모든 vertex를 연결하면서 비용을 최소로하는 tree형태(cycle x)의 subgraph이다. 클러스터 분석등 여러 가지 응용에서 쓰인다. 1. Greedy algorithm Greedy algorithm은 매 순간 최적인 선택을 하며 그러한 방식으로 진행할 때, 최종적으로 해답에 도달하게 되는 알고리즘이다. 모든 문제에 대해서 적용되는 것은 아니지만, MST를 구할 때 이것을 적용할 수 있다. - 가정 : connected graph, distinct weights - Cut : 그래프가 주어졌을 때, 두개의 집합으로 vertex들을 분할하는 것 - crossing edge : 한 집합의 v..
3. Directed Graph(Digraph) Directed graph는 edge의 방향이 존재하는 그래프이다. 우리 주변에 매우 많은 것들은 서로 연결되어있고, 가리키는 방향이 정해져있다. 프로그래밍으로 따지면, 상속관계, 함수의 호출구조 등이 있고, 응용은 무궁무진하다. 사실 이전에 배웠던 Undirected graph는 양방향 directed graph로도 볼 수 있다. 1) Digraph API Diagraph는 Undirected graph와 동일하게 Sparse Matrix를 표현할 때 사용하는, Adjacency-list를 주로 사용한다. Digraph API는 Undirected graph의 API와 완전히 동일하며, 모든 Edge의 방향을 바꾸는 연산이 추가된다. Digraph reverse() 구현 또한 완전히 동일한데, addE..
2. Undirected Graphs 1. Terminology Graph란 edges로 연결된 vertices 집합이다. 지하철 노선도, 우주 은하 등 세상에 존재하는 수많은 것들을 그래프로 추상화하여 표현할 수 있다. Vertices의 이름은 symbol table로 Integer로 mapping하여 사용하면된다. 특히 Undirected graph는 edge의 방향이 존재하지 않는다. - Path : sequence of vertices connected by edges - Cycle : 첫번째와 마지막 vertex가 같은 Path 2. API & Representation Graph의 API는 다음과 같다. Graph(int V) // V개 vertice를 가진 그래프 생성 Graph(In in) // Input stream에 따라 ..
1. Introduction 알고리즘 강의를 다 들었다... 너무 유익한 강의였다! 그런데... 이게 알고보니 조금 더 내용은 어려운데 강의가 part2로 하나 더 있었다! 그래서 이걸 공부하면서 내용을 정리해보려고 한다...! 근데 또 욕심이 생겨서 최근에 시간날 때마다 MIT의 Computer Structure강의를 듣기 시작했다. 이것도 내용이 너무 좋아서 계속 볼것 같은데 큰일인듯.. (프로젝트는 언제하지.. ㅠ)
14. Symbol Table Applications 1) Sets - Exception filter 수학적으로 set은 집합이란 뜻으로, distinct key의 모음이다. set의 API는 다음과 같다. void add(Key key) boolean contains(Key key) void remove(Key key) int size() Iterator iterator() 이것을 이용하면, Exception filter를 구현할 수 있다. 먼저 파일의 White list의 모든 단어들을 읽어서 모든 단어를 Symbol Table에 집어넣는다. 이 때 삽입은, Hash function으로 구현하면 constant time, Red-black BST로 구현하면 logarithmic time이 걸린다. 다음로 우리가 검사하고자 하는 파일에서 한단어씩 꺼내서 ..
13. Hash tables 1. Hash function Key에 순서가 있는 경우, BST에 넣어서 Symbol table을 구현할 수 있었다. 만약 Key에 순서가 없는 경우 Hash table을 이용하면 logarithm time이 아닌 constant time에 search가 가능하다. hash table의 기본적인 아이디어는, key에 hash function을 적용한 값이 배열의 Index가 되도록 하는 것이다. 이렇게 된다면 우리는 key에 단순히 hash function으로 연산을 하거나, 그 값을 cache에 저장시켜놓고 사용함으로서. 배열의 임의의 요소의 접근시간은 constant time이므로 빠른 searching이 가능하다. 하지만, 한가지 문제는 (key, value)쌍의 갯수보다 배열의 공간이 작을 경우..
12. Geometric application of BSTs 이번 주제는 Binary search tree를 이용해 Geometric objects 간의 Intersection을 찾는 것이다. 1. 1d range search 1차원 상에서 여러가지 점들이 있을 때, 특정 범위(range)에 존재하는 점들을 찾는 문제이다. 각각의 점들의 BST에 넣고 다음, range count(범위 내 점 갯수) 코드는 아래와 같고, rank함수는 logarthmic time이므로, range count도 그렇다. public int size(Key lo, Key hi){ if(contains(hi)) return rank(hi) - rank(lo) + 1; else return rank(hi) - rank(lo); } range search는 root부터 시작해 current..

티스토리툴바