Computer/DataStructure3 [자료구조] MergeSort 합병정렬 알고리즘 구현 특징 1. Stable 한 정렬이다. 2. 추가적인 공간이 필요하므로 in-place algorithm 형식이 아니다. ** in-place algorithm 이란 적은 공간으로 처리하는 알고리즘을 의미한다고 한다. (In-place is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space.) 출처: 위키피디아 구현 KEY POINT 1. 분할을 한다 ( 더이상 쪼갤 수 없을 때까지 "/2" 로 인덱스를 나누어 계속 쪼갠다. ) lgN 2. 병합한다. ( 쪼개어진 값들을 다시 뭉친다. 뭉치면서 값을 비교하여 정렬한다. ) N 속도 : .. 2015. 3. 17. [자료구조] Double-Ended Queue (Dequeue) and Randomized Queue Double-Ended Queue (Dequeue) and Randomized Queue 더블엔디드큐 1. pop function call : 값 반환이 앞으로, 뒤로 가능함 ( removeFrist,removeLast ) 2. push function call : 값 삽입이 앞으로, 뒤로 가능함 ( addFirst, addLast ) 랜더마이즈 큐 1. dequeue function call 랜덤한 값을 반환하도록 한다. 2. enqueue function call 시에 할당된 Array 가 가득차있을경우 자동으로 늘려준다. MutableArray ! DOUBLE-Ended Queue ( Dequeue ) 아래의 코드는 부여된 Interface 에서 함수를 작성한 것이다. 이게 답이라고는 얘기할 수 없.. 2015. 3. 15. 다익스트라 Dijkstra algorithm다익스트라 알고리즘 알고리즘 개요데이크스트라 알고리즘은 각각의 꼭짓점 v에 대해 s에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 이 값은 s에 대해서는 0이고, (d[s]=0) 다른 모든 꼭짓점에 대해서는 무한대(∞) 값으로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.데이크스트라 알고리즘은 변 경감(edge relaxation)이라고 불리는 기본 연산을 바탕으로 한다. s에서 u까지의 최단 경로(d[u])를 이미 알고 있고, u에서 v까지의 변 (u, v)가 존재할 .. 2015. 1. 22. 이전 1 다음 반응형
