본문 바로가기

분류 전체보기

 (140)
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)..
6. Selection sort, Insertion sort, Shell sort 정렬의 설명은 오름차순을 기준으로 설명한다. 1. Selection sort selection sort는 1) 포인터가 가리키는 요소를 기준으로 오른쪽에 모든 요소중에서 가장 작은 요소를 선택하고, 그것을 포인터가 가리키는 요소와 교환한다. 2) 배열의 첫번째 요소부터 시작해서, 마지막요소까지 차례대로 포인터를 옮겨가며 정렬을 시도한다. 포인터를 기준으로 좌측 부분배열은 항상 우측의 어떤 요소보다도 작게된다. 다음의 예시에서, 포인터는 빨간글자이며 정렬은 다음과 같이 이루어진다. 1 4 2 5 3 1 4 2 5 3 1 2 4 5 3 1 2 3 5 4 1 2 3 4 5 따라서, 정렬은 입력에 관계없이 N개의 요소가 있을 때, 항상 (N-1) + (N-2) + ... + 1 + 0 ~ N^2 / 2 만큼의 ..
인터페이스(Interface)와 구현(Implementation)의 이해 (1) 내가 대학교 내내 C언어만 배우다가 객체지향언어를 처음으로 배우면서, 인터페이스란 단어를 접했던 것 같다. 당시에는 많은 자료를 검색해보아도 이해가 잘 안되었기 때문에, 이에 대한 내용을 최대한 이해하기 쉽고 디테일하게 설명하고자 한다. 먼저, 인터페이스에 대해서 알아보자 인터페이스라는 영어에서도 알 수 있듯이, Inter(상호간에) Face(얼굴을 맞대다)라는 뜻이다. 명사로서는 상호간에 얼굴을 맞대는 그러한 지점이라는 뜻이다. 따라서, 인터페이스를 위해서는 두 가지 조건이 충족되어야한다. 조건 1. 서로 다른 두개의 객체의 존재 조건 2. 상호작용 위의 조건이 충족된다면 언제나 인터페이스가 존재한다. 예를 들어보자. 미국에 있는 사람과 한국에 있는 사람이 존재하고(조건 1) 서로 대화를 통해 의견을 ..

티스토리툴바