알고리즘11
[알고리즘] MST / Disjoint set / 크루스칼 알고리즘
MST 알고리즘크루스칼과 프림 알고리즘은 MST 를 구하는 알고리즘 의 2종류이며, 그리디 알고리즘을 이용한다. MST 와 그리디 알고리즘의 정보는 : https://programming119.tistory.com/78 크루스칼 알고리즘 나무와 숲 -> 크루스칼 알고리즘은 각각의 노드를 나무로 생각하고, 모든 노드의 집합을 숲 이라고 생각한다. 숲에 나무들이 많다. 이 숲은 마법의 숲이라 나무끼리 손을 잡는다. 나무들끼리는 손을 잡을 수 있을 수도 있고, 나무들끼리 손을 잡으려면 마력을 소비하고 각각 나무들끼리 몇의 마력이 드는지는 정해져 있다. 예시) A 와 B 나무는 손을 잡을 때 3의 마력이 들고 , A와 C는 손을 잡을 때 10의 마력이 들고, B와 C는 손을 못 잡는다. 나무 : 노드 숲 : 노..
[알고리즘] Minimal Spanning Tree 와 그리디 알고리즘
그리디 알고리즘 해결 방식으로 MST(Minimal Spanning Tree) 를 구해낼 수 있다. Minimal Spanning Tree(최소신장트리) 란? 한국말로하면 최소신장트리 로 그래프를 연결하는 가장 최적의 트리라 생각하면 된다. 모든 정점들을 포함해야하며, 사이클을 포함하면 안된다.(공간을 만들면 안됨) 가장 중요한 것은, 모든 간선의 가중치가 최소가 되는 트리를 Minimal Spanning Tree 라고 한다. 안전한 엣지(Safe edge)란? 안전한 엣지란, 우리가 MST를 구하는 과정에서, 현재 선택할 수 있는 엣지를 뜻한다. 예를들어 우리가 MST 를 구하고 있는 중인 어떤 상황일 때, A 엣지를 선택해서 MST를 만드는 경우도 있고 B 엣지를 선택해서 MST를 만들 수 있지만, ..
[알고리즘] Greedy strategy / 그리디 알고리즘 전략, 구성
그리디 알고리즘 구성하기 1. 문제의 최적의 부분구조를 만든다. (문제를 잘 이해하고 어떻게 해결할지 구성하라는 의미이다.) 2. 재귀적으로 해결책을 도출한다. 3. 재귀 내부의 어느 단계이든, 최적의 선택 중 하나는 반드시 greedy choice 임을 증명한다. 4. greedy choice 를 했을 때, 하나의 부분문제만 남는 것을 보인다. (계속해서 greedy choice를 해야되기 때문에) 5. 그리디 알고리즘을 완성시킨다. 6. 재귀적인 알고리즘을 iterative 하게 변환한다. * 재귀적인 알고리즘 -> iterative 알고리즘 과정을 거치는 이유는 생각하는데에 있어서 편하기 때문이지 바로 알고리즘을 구현할 수 있다면 굳이 거치지 않아도 된다. 출처 : 고려대학교 정순영 교수님 알고리즘..
[알고리즘] Greedy Algorithm 이란?
왜 Greedy일까? // Greedy = 욕심부리는, 탐욕스러운 // 필자는 Greedy 가 전체 문제에 대해 생각하기 귀찮고, 게으르기 때문에 현재 상황에 대한 답만을 구해서 최종 결과를 도출하는 알고리즘 이라고 생각하고 암기하고 있다 (현재만 생각하는 욕심을 부린다는 의미이다.) 그리디 알고리즘은 현재 놓여진 상태에서의 최적의 답만을 찾는다. Locally 한 최적의 답만을 찾기 때문에 항상 Global Solution (전체문제의 답) 을 찾아준다고 확신할 수는 없다. 하지만, 우리는 현재 상황만 생각하면 되기 때문에 속도면에서는 빠르게 해결 할 수 있다. 예제) 위 그래프에서 goal까지의 최저비용 거리를 구해보자. 1) start 에서 출발. start 에서 가장 낮은 비용은 b 로 가는 3 ..
[Quick Sort] Quick sort는 왜 빠를까? (1) : Randomized 된 Quicksort / Quick sort의 Worst running time (최악)
Quick Sort란? 피벗을 중심으로 작은쪽, 큰쪽으로 나누어 정렬하는 방식을 뜻한다. 메모리 소비가 없고 무엇보다 정렬속도가 빠르기 때문에 Quick sort로 이름이 붙여졌다. (* 참고 : https://coderkoo.tistory.com/7) Quick Sort의 시간복잡도 허나 다들 알다시피 Quick Sort의 시간복잡도는 O(n^2) ,Ω(n lgn) 이다. (이는 구글에 검색해보면 자료가 많으니 생략, 아까 링크한 블로그에 자세히 설명이 되어있다!) 최악과 최적 모두 Θ(n lgn) 인 Heap Sort와 Merge Sort 에 비하면 겉보기에는 느릴 수 있어보인다. 그렇다면 왜 Quick Sort는 Quick Sort 인 것일까? Randomized 된 Quicksort의 최악은? 우..