프로그래밍/Algorithm - 1 (14) 썸네일형 리스트형 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.. 11. Balanced Search Tree 1. 2-3 search trees 2-3 search tree는 2-node(1 key, 2 children), 3-node(2 key, 3 children)을 가질 수 있는 추상적 search tree이다. 일반적인 binary search tree와는 다르게 root node부터 시작하게 recursive하게 탐색하고 더 이상 탐색할 수 없는 null link를 만나는 경우, node를 새로 생성하는 것이 아닌 마지막으로 탐색한 node에 key값을 넣은 뒤, node내부의 key갯수가 3개가 되면 node를 분리시켜 tree를 성장시킨다. 2-node에서 left children은 parent의 key보다 작고, right children은 parent의 key보다 크다. 3-node에서 left.. 10. Symbol tables & Binary search trees(BST) 1. Symbol table Symbol table은 DNS lookup시 참조하는 테이블과 같이, key-value쌍이 mapping된 정보를 가지는 추상화된 테이블이다. Key값이 주어지면, 우리는 value를 search한다. API는 다음과 같다. void put(Key key, Value val) Value get(Key key) void delete(Key key) boolean contains(Key key) boolean isEmpty() int size() Iterable keys() 여기서 Value는 null이 될 수 없고, get연산시 key가 없다면 null이 return 된다. put연산시 기존에 key값이 있다면 해당 key의 value값을 update한다. Key값은 immu.. 9. Priority Queue 1. Prioity Queue Priority Queue란 여러 요소를 집어넣고 나올 때는 우선순위에 따라 나오도록하는 자료구조이다. 즉, item을 빼낼 때마다 가장 크나 작은 아이템이 Queue에서 remove된다. API는 다음과 같다. void insert(Key v) Key delMax() boolean isEmpty() 만약,. N개의 item중에서 가장 큰 M개의 item을 찾고 싶다고 하자. 가장 쉬운 방법은 sorting이다. 하지만, 만약 N개의 item을 저장할 충분한 공간이 없다면 어떻게 할까? mininum prioity queue에 key값을 집어넣고 queue의 size가 M보다 커질 때 제거한다면 가장 작은 item이 제거된다. item을 넣음을 반복하고 M보다 커질 때마다 .. 8. Quick sort 1. Quick sort quick sort는 다음과 같다. 1) 배열을 shuffle한다. 2) 배열의 첫번째 요소를 기준점 pivot 으로 삼고, 두번째 요소, 마지막요소를 가리키는 두개의 포인터를 둔다. 3) 좌측의 포인터를 i, 우측의 포인터를 j라고 하면, pivot보다 커질 때까지 i를 우측으로 이동시키고, pivot 보다 작아질 때까지 j를 이동시킨다. 더 이상 i, j가 이동하지 못하면, a[i]와 a[j]를 교환한다. 그러면 다시 i가 가리키는 것은 pivot보다 작아지고, j가 가리키는 것은 pivot보다 커지므로 이동가능하게 된다. 이렇게 이동하다가 멈추면서 i가 j보다 크거나 같아지는 순간, pivot이 가리키는 값과 a[j]를 교환한다. 이때 a[j]의 값은 pivot의 값보다 항.. 7. Merge sort 1) Merge sort merge sort는 전체 배열을 좌우 두 배열로 나누어 각각 자기사진 sort함수를 호출해 정렬하고, merge(병합)한다. sort함수에서 sort함수를 호출하기 때문에, recursive하게 실행된다. merge함수는 좌우가 정렬되어있다는 것을 확인한 후, 현재 배열을 복사하고, 그것을 이용하여 원래의 배열에 값을 집어넣으면서 정렬한다. 배열에 값을 집어넣은 merge방식은 다음과 같다. 1) 복사 배열의 좌우 배열의 맨 왼쪽에 각각 포인터를 두고, 원 배열의 맨 왼쪽에 포인터를 둔다. 2) 좌우배열의 포인터들의 값을 비교해 작은 값을 원 배열의 포인터에 집어넣는다 3) 원 배열의 포인터를 오른쪽으로 이동시키고, 값을 삽입한쪽 부분배열의 포인터를 오른쪽으로 이동시킨다. 4).. 이전 1 2 다음
