본문 바로가기

전체 글

 (142)
8. Tries 1. R-way tries Symbol table의 검색은 크게 red-black BST, hash table을 통하여 이루어 질 수 있었다. Hash table은 constant time의 검색/삽입/삭제를 지원하지만, ordered operation이 불가능하였고, red-black BST는 ordered operation이 가능하지만, logarithmic time의 검색/삽입/삭제가 이루어 졌다. 특별히 Symbol table의 Key가 String인 경우 우리는 character의 갯수가 R로 제한되어있다는 것을 이용하여 red-black BST보다 성능을 더 향상시키면서 ordered operation을 가능하게 할 수 있다. tries라는 이름은 retireval 로부터 나왔고, 우리는 tr..
7. String Sorts 1. Strings in Java String 는 Sequence of characters 이며, 굉장히 중요한 Abstraction이다. C언어에서 char은 8bit integer이고, 256개의 문자를 표현할 수 있으며, 7-bit ASCII를 지원한다. JAVA에서 char은 16bit unsigned integer이고, 16bit Unicode와 21bit Unicode 3.0을 지원한다. Java에서 Sting type은 immutable하고, 다음과 같이 구현된다. public final class String implements Comparable{ private char[] value; //문자들 privatee int offset; //첫번째 문자가 시작하는 지점 private int ..
6. Maximum Flow & Minimum Cut 1. Mincut & Maxflow problem mincut problem이란 source vertex s, target vertex t를 포함하는 그래프를 s를 포함하는 vertex set A와 t를 포함하는 vertex set B로 분할하였을 때, A->B로 향하는 모든 Edge의 capacity의 합을 최소로 하는 분할을 결정하는 문제이다. maxflow problem이란, 임의의 Edge/Vertex에 대해 아래 조건을 만족하면서 target vertex t로 들어오는 flow를 최대로 만드는 값을 찾는 것이다. 참고로 그래프에서 flow vlaue = inflow at t 이다. - Capacity constraint : 0 t 인 경로이며, 역방향인 backward edge도 선택될 수 있다..
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강의를 듣기 시작했다. 이것도 내용이 너무 좋아서 계속 볼것 같은데 큰일인듯.. (프로젝트는 언제하지.. ㅠ)

티스토리툴바