본문 바로가기

프로그래밍/Algorithm - 1

 (14)
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 만큼의 ..
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..
2. Union-Find Union-Find는 다음과 같은 문제를 해결한다. N개의 Object가 주어졌을 때 두 Object가 연결되어있는지 여부(Find) API : boolean connected(int p, int q) 두 Object의 연결(Union) API : void union(int p, int q) 연결내부에 순서가 없기때문에 집합의관점에서 같은집합인지여부확인(Find) 합집합 생성(Union) 용도로 사용가능하다. 이것을 이용하면 물리적인 문제뿐만 아니라, 격자형태에서 연결구조인 사진, 분산화된 네트워크 연결구조 등 여러 문제를 풀 수 있다. 결론적으로 가장 최적의 성능을 내는 알고리즘은 weighted QU + path compression 이다. AlgorithmWorst-case timequick-fin..
1. Introduction Cousera에서 무료로 제공하는 강의중에, 프린스턴 대학 교수님께서 설명해주는 알고리즘 강의 내용이 평이 좋아 듣게 되었다. Cousera앱을 깔아서 스마트폰으로 어디서든 강의를 수강할 수 있다는게 장점인 것 같다. 대부분에 현실에 존재하는 많은 문제들을 풀기 위해서 우리는 알게 모르게 알고리즘을 사용한다. 알고리즘의 핵심은 Abstracted Problem을 해결하는데 있다. 문제의 해결방법은 1)추상화시켜 문제 정의, 2)추상화된 문제 해결방법을 아는 것, 이렇게 2가지 능력이 있어야 한다. 즉, 내가 예전에 공학해결방법론에서 배웠듯이, 디테일한 문제를 우리가 해결가능한 문제로 바꾸는 능력, 사실상 이 능력이 중요하다. 하지만, 이것을 하기 위해서는 해결가능한 문제가 어떤 것인지부터 알아야 하기 때..

티스토리툴바