본문 바로가기

전체 글

 (142)
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..
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가지 능력이 있어야 한다. 즉, 내가 예전에 공학해결방법론에서 배웠듯이, 디테일한 문제를 우리가 해결가능한 문제로 바꾸는 능력, 사실상 이 능력이 중요하다. 하지만, 이것을 하기 위해서는 해결가능한 문제가 어떤 것인지부터 알아야 하기 때..
5. Kanban Board 사용 (Trello) 프로젝트 관리를 위해서 칸반보드를 사용하기로 하였다. 트렐로는 다른 많은 상용 프로젝트 관리툴보다 가볍기 때문에 지식이 거의 없는 개인이 이용하기에 효과적이다. 먼저 검색엔진에서 트렐로를 검색하고, 사이트를 접속하면 된다. 로그인을 하면 무료버전으로 나의 Workplace를 확인할 수 있고, 기존에 존재하는 템플릿을 활용해서 Workspace에 보드를 생성하거나, 아예 새롭게 생성 할 수 있다. 기존에 존재하는 Kanban Template으로 Market Analysis System Project라는 보드를 생성하였다. Manage Your Team’s Projects From Anywhere | Trello Task management Use Trello to track, manage, complete..

티스토리툴바