본문 바로가기
반응형

프로그래머의 길/알고리즘22

Dijkstra Algorithm Shortest Path - Dijkstra Algorithm 방향그래프(Directed Graph)의 간선이 양수의 Weight를 가질 때 임의의 출발 정점에서 도착 정점까지의 경로 중 경로의 길이가 최소인 경로를 최단경로라고 정의한다. 이러한 최단경로는 도로망, 항공로 지도, 작업공정계산 등에 널리 응용된다. 최단경로는 다익스트라의 알고리즘으로 구할 수 있다. 다익스트라의 알고리즘 인접행렬 상태로 각 간선의 가중치(Weight)가 존재하도록 한다. 정점 i에서 i까지의 가중치는 0이고 정점 i에서 j까지의 간선 E(i, j)가 존재치 않으면 가중치는 무한대(∞)가 된다. 집합 S와 T를 정하는데 S는 출발 정점을 초기값으로 하고 집합 T는 출발 정점을 제외한 모든 정점을 포함하도록 초기화한다. 출발 .. 2009. 2. 2.
Dijkstra Algorithm Dijkstra Algorithm 동적 혹은, Adaptive즉, 적응적 Routing기법 알고리즘등으로 불리는 유명한 알고리즘에 대해 공부했던 내용을 Review한다.또한 Dijkstra’s Algorithm에 대해서도 언급하고 있다. Picture 1. example of Dijkstra’s Algorithm Source node를 1이라고 하고, Destination Node를 8이라고 할 때, 인접배열을 위한 table이 위처럼 작성될 수가 있다. 처음 1의 입장에서 2와 6은 인접해 있기에 그 거리를 기록할 수가 있다. 즉 알수 있다고 보는 것이다. 이에 반해서, 나머지 node는 보이지 않는다. 아득한 거리로 보자는 것이다. 역시 만약 2번 path를 타기로 결정했다면, 2에서 볼 때, 1,3.. 2009. 2. 2.
qsort 함수에 대하여.. 2007. 4. 3.
이진탐색 (Binary Search) 알고리즘 이진탐색 (Binary Search) 알고리즘. N개의 데이터를 가진 배열 list[]가 있고, 우리가 찾고자 하는 값이 key라고 하자( list[0], list[1], ..., list[N-1] ). 이진 탐색은 배열의 중간요소(list[N/2])와 찾고자하는 값(key)을 비교한다. 찾고자하는 값이 중간요소 보다 작다면 배열의 중간요소 보다 큰 요소들(list[N/2] ... list[N-1])에는 찾고자 하는 데이터가 없는 것이다. 즉, 데이터의 절반은 검사 할 필요가 없어진다. 나머지 요소들에 대해 똑같이 반복한다. (Recusive) 탐색방법 입력 : 리스트,시작인덱스,마지막인덱스,검색값 출력 : 해당 키의 인덱스 ( 찾는 값이 있으면 ) 또는 아니오 ( 찾는 것이 없으면) 1. 각 값의 의미.. 2007. 4. 3.
퀵 정렬(Quick Sort) 4. 퀵 정렬 퀵 정렬은 C.A.R. Hoare가 만든(The Computer Journal, 5:10-15, 1962.) 가장 우수한 편에 속하는 평균 수행능력을 갖는 정렬 방식이다. (단, 조건에 따라서는 분포수 정렬, 역사상 정렬, 래딕스 정렬방법이 빠르다.)버블정렬이나 선택정렬의 경우, 바로 옆의 데이터를 서로 비교하여 교환하는 방식인데, 이러한 방식은 데이터가 최종으로 정렬될 위치에서 멀면 멀수록 비효율적이라고 할 수 있다. 퀵 정렬은 멀리 떨어진 데이터를 서로 교환함으로써 이러한 비효율성을 개선하였다. 간단히 설명하면, 'Pivot' 이라 불리는 임의의 값을 설정한 후에 배열의 양끝방향에서부터 탐색을 시작해서 Pivot값보다 큰 값과 작은값을 발견하여 서로 치환하는 방식이다. 단점으로는, Pi.. 2007. 4. 3.
쉘 정렬(Shell sort) u 삽입 정렬을 간단하게 변형 u 멀리 떨어진 원소끼리 교환이 가능하게 하여 정렬 속도를 향상시킴 u h-정렬 화일 : 모든 h번째 원소를 정렬한 화일 u 증가 순서의 예 : …, 1093, 364, 121, 40, 13, 4, 1 u 특징 Ø 순열 h가 1, 4, 13, 40, … 일 때, 쉘 정렬의 비교회수는 N 3/2 을 넘지 않음 Ø 안정적인 제자리 정렬 ShellSort(a[], n) for (h ← 1; h 0; h ← h/3) do { // h 값을 감소시키며 진행 for (i ← h + 1; i ≤ n; i ← i+1) do { v ← a[i]; j ← i; while (j >h and a[j-h] >v) do { a[j] ← a[j-h]; j ← j-h; } // while A[j] ← .. 2007. 4. 3.
반응형

티스토리툴바