본문 바로가기

프로그래밍

 (103)
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) 서로 대화를 통해 의견을 ..
5. Introduction of Sort 우리의 Sort의 목적은 정렬가능한 임의의 데이터 타입을 특정한 순서에 따라 정렬시키는 것이다. sort() 함수는 내부적으로 요소의 비교를 위해 compareTo() 함수를 호출할 수 있다. java에서 이것은 Comparable interface에 정의되어 있다. public interface implements Comparable{ public int compareTo(Item that){ } } 아래는 이것을 구현한 것이다. //comparable interface를 구현한 Date자료구조, total order를 만족하기때문에 정렬가능하다. public class Data implements Comparable{ private final int month, day, year; public Dat..
4. Bag, Stack, Queue bag, stack, queue는 모두 collection of object로, insert, remove, iterate, isEmpty의 연산을 가진다. Bag는 내부 item의 순서가 없고, 삽입과 랜덤한 순서로 iterate만 가능하다. Stack은 LIFO(Last In First out), Queue는 FIFO(First In First Out)의 구조를 갖는 Abstract Data Type이다. 우리는 구현의 방식을 여러개 가져갈 수 있는데, 이것은 Client의 입장에서 언제든 상황에 따라 다른 구현방식을 사용하게함으로서 유연하게 대처할 수 있도록 한다는 장점을 가져다준다. 1) Stack Stack의 기본 API는 다음과 같다. void push( item) pop() boolean i..
3. Analysis of algorithms 알고리즘을 분석하는 것은 여러 이해관계자의 관점에서 중요하다. 프로그래머는 코드를 개발하기 위해, 고객은 효율적으로 문제를 해결하기 위해, 이론가는 동작을 이해하기 위해 필요하다. 알고리즘을 분석한다는 것은, 우리가 프로그램이 어떻게 동작할 것인지 예측가능하게 하고, 여러 추후에 발생할 수 있는 문제들에 대해서 대비하고 대처할 수 있게 한다. 알고리즘의 성능을 예측하고 비교할 수 있는 한가지 프레임워크는 다음과 같다. Observe -> Hypothesize -> Predict -> Verify -> Validate 3-SUM 문제를 생각해보자. 이 문제는 N개의 요소를 가진 배열이 존재할 때, 서로 다른 3개의 요소의 합이 0이 되는 것이 몇 개나 존재하는지를 세는 문제이다. 1) Empirical a..

티스토리툴바