CS17 [알고리즘] Dijkstra 다익스트라 알고리즘 - 한 정점에서 여러 개의 다른 정점까지의 최단 거리를 구하는 알고리즘 (single source shortest path) - 간선에 양의 가중치가 존재한다. (음의 가중치 간선이 존재해서는 안된다.) - 구현시 배열 혹은 힙(우선순위큐)을 사용한다. 초기화 dis[V]: 시작점으로부터 V까지의 거리를 저장하는 배열 - V가 시작점인 경우만 0, 나머진 INF초 초기화 chk[V]: V를 선택해서 계산을 했었는지에 대한 배열 로직 1. chk가 false인 정점 중 dist가 가장 작은 정점 x를 선택한다. 2. x와 인접한 정점의 dist를 갱신한다. for( a : adj[x]) dis[a.v] = min(dis[a.v], dis[x.v] + a.cost) 3. chk를 true로 바꾼다. 4. 모.. 2020. 12. 30. [알고리즘] 정렬 - quick sort 퀵소트 - 불안정정렬, 비교정렬 - divide and conquer 사용 이름이 퀵소트인지라 best case에선 가장 빠른 시간복잡도를 가지지만 worst case에선 한없이 느려지는....양날의 칼느낌이다. 그냥 머지소트를 쓰는 걸로 하자. 시간 복잡도 best case O(n log n) worst case O(n^2) worst case는 어떤 경우냐 하면 오름차순 정렬인데 5 4 3 2 1로 배열이 제시되었을 경우이다. 퀵 소트의 구현 과정을 살펴보면 이해 가능하다. 퀵소트는 1. pivot이 있고 (보통 배열 왼쪽 끝 혹은 오른쪽 끝 값) 2. 피벗을 중심으로 좌측엔 피벗보다 작은값, 우측엔 피벗보다 큰 값을 배치한다. 3. 작은값, 큰 값 교차 지점에 피벗을 놓는다. 4. 피벗을 중심으로 .. 2020. 11. 29. [알고리즘] 정렬 - Merge Sort Merge sort 합병정렬 - 재귀를 사용하는데 자꾸 까먹어서 정리한다. - 크게 3부분으로 나뉜다. divide conquer combine Divide: 배열을 mid를 중심으로 두 부분으로 나눈다. 배열 사이즈가 1이 될때까지 반복한다. Conquer: 부분 배열을 정렬한다. 배열 size가 1일떄만 진행한다. Combine: 정렬된 배열을 합병한다. - 머지 소트를 하기 위해선 sorted된 리스트를 저장하기 위한 추가 배열이 필요하다. divide와 conquer: 배열 사이즈가 1일때까지 쪼갠다. merge: 정렬된 배열 2개를 하나의 sorted에 합친다. 시간 복잡도 O(NlogN) #include #define MAX_SIZE 1000000 + 1 int arr[MAX_SIZE]; //.. 2020. 11. 1. [알고리즘] 0-1 BFS edge가 0 혹은 1의 가중치를 가질 때 사용하는 bfs이다. 사용하는 자료 구조 - 덱 접근 - 다익스트라 알고리즘을 최적화시킨 것이다. 사실 다익스트라 써도 상관없다. 다익스트라도 가중치 있는 노드에서 최단 거리 찾는 알고리즘이기 때문. - 가중치가 0이라는 것은 이전 노드와 동일 레벨이 존재한다는 것이다. 가중치가 1이면 이전노드에 비해 한 레벨 아래에 존재한다는 의미. - 가중치가 0인 것을 우선으로 팝하기 위해 가중치가 0인 경우 큐 앞쪽에, 가중치가 1인 경우 큐 뒤쪽에 푸쉬한다. 하지만 일반적인 큐는 앞에 푸쉬하는 것이 불가능하기 때문에 덱을 사용해서 앞쪽에 푸쉬한다. #include int main(void){ deque dq; dq.push_front(시작노드); while(!dq.em.. 2020. 10. 29. 이전 1 2 3 4 5 다음
