컴퓨터 지식64
[알고리즘] Greedy Algorithm 이란?
왜 Greedy일까? // Greedy = 욕심부리는, 탐욕스러운 // 필자는 Greedy 가 전체 문제에 대해 생각하기 귀찮고, 게으르기 때문에 현재 상황에 대한 답만을 구해서 최종 결과를 도출하는 알고리즘 이라고 생각하고 암기하고 있다 (현재만 생각하는 욕심을 부린다는 의미이다.) 그리디 알고리즘은 현재 놓여진 상태에서의 최적의 답만을 찾는다. Locally 한 최적의 답만을 찾기 때문에 항상 Global Solution (전체문제의 답) 을 찾아준다고 확신할 수는 없다. 하지만, 우리는 현재 상황만 생각하면 되기 때문에 속도면에서는 빠르게 해결 할 수 있다. 예제) 위 그래프에서 goal까지의 최저비용 거리를 구해보자. 1) start 에서 출발. start 에서 가장 낮은 비용은 b 로 가는 3 ..
[DB] DB / DBMS / DBS / DB Application 의 차이 / 개념
DB (DataBase) 데이터들의 집합, 모음 자체를 뜻한다. 단순한 모음이 아니라 일반적으로 잘 정리되어 표준화된 모음을 의미한다. DBMS (DataBase Management System) 사용자들이 데이터베이스에 있는 데이터들을 접근하고 사용하기 위해 쓰이는 시스템이다. DB 자체만을 가지고 데이터를 이용하려면 무척이나 불편하고 힘들것이다. DBMS 에 내장된 질의어들을 통해 사용자들은 DB에 접근할 수 있다. 예) Oracle, Mysql ... 등등 DB Application 데이터베이스가 사용되고 적용되는 것을 의미한다. 생산분야에서는 재고, 주문, 생산 부분에서 DB가 이용될 것이고, 대학교에서는 대학 등록, 학생 관리, 성적들에 DB가 사용된다. 이처럼 데이터베이스가 적용되는 시스템을 ..
[Quick Sort] Quick sort는 왜 빠를까? (2) : 기대값을 고려한 Quick sort / Quick sort의 Expected running time /
Expected Running Time이란? 만약 동전을 100번 던진다고 치자. 우리는 앞면이 최대 100번 나올 수 있는 것을 당연히 알고 있다. 하지만, 또한 우리는 앞면이 평균 50번 정도가 나올 것도 알고 있다. 50번보다 조금 나올 때도 있을 것이고, 50번보다 많이 나오는 때도 있을 것이지만, 우리는 시행이 거듭될 수록, 50번에 수렴한다는 것을 직감적으로 알고 있다. 이 50이라는 숫자가 이 100번 던지는 시행의 기대값이다. Quick Sort의 경우에도 우리가 정렬을 사용할 때를 적용하려면 최악의 경우가 아닌 이런 기대값 Running Time 이 중요할 것이다! QuickSort 의 Expected Running Time 앞서 말했듯이 input값이 랜덤한 값들로 들어온다고 했을때, ..
[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의 최악은? 우..