독학두비니

Coding_Algorithm/DS_Algorithm

Quick Sort

Quick Sort 0. 개요 Quick Sort는 특이하게도 Worst case로 따지자면 Merge Sort, Heap Sort보다 안좋은 성능을 보인다. 그러나 Runtime의 기댓값이 낮기 때문에 많이 사용하는 알고리즘이다. 후에도 언급하겠지만 이 핵심은 partition을 어떻게 정하느냐에 있고, 추후 글에는 randomized quick sort에 대해서도 다룰 것이다. 1. Pseudocode Quicksort는 partition을 정한 뒤, 참고: https://www.youtube.com/watch?v=COk73cpQbFQ 2. Randomized Quick Sort 2.1 Randomized Quick Sort Time Complexity O(nlgn)

Coding_Algorithm/DS_Algorithm

Heap Sort

Heap Sort 0. 개요 앞서 다뤘던 내용들은 자료구조를 사용하지 않는 알고리즘이었다. (Insertion Sort, Merge Sort 등) 그러나 자료구조를 사용할 경우 더 효율적으로 문제를 풀 수 있는 경우가 생기며, 대표적으로 Max heap를 사용하는 Heap Sort가 있다. 1. 자료구조 heap 자료구조 heap, 특히 max heap에 대해서 알아봅시다. Max Heap이 되기 위해서는 다음 조건을 만족해야한다. 1) a complete binary tree여야함 - tree 구조에서 마지막 level을 빼고는 모두 차 있어야 함 - 마지막 level은 왼쪽부터 오른쪽으로 차있음 2) Max-heap Property를 가지고 있어야 함 - key(x) >= keys(at x's chi..

Coding_Algorithm/DS_Algorithm

Probabilistic Analysis

Probabilistic Analysis 0. 개요 기존에는 알고리즘의 시간분석도를 계산할 때 알고리즘에서 실행되는 명령어의 수를 계산하는 방식으로 진행했다. 특히 worst case로 진행해 그러나 많은 알고리즘은 주어지는 입력에 따라 성능이 달라지는 경우가 많다. 이렇게 입력이 확률적으로 주어지는 상황에서, 입력에 대한 worst case로 성능을 보는 것이 아닌, 평균적인 성능으로 알고리즘의 성능을 분석하는 방법을 알고리즘의 확률적 분석이라고 한다. 다만 확률적 분석은 입력의 분포를 알고 있다는 가정 하에 진행된다. 입력의 분포를 모른다면 확률적 분포를 진행할 수 없다. 1. Hiring Problem Hiring Problem은 사람을 채용할 때의 문제를 칭한다. 각각 사람을 면접볼 때 비용이 들..

Coding_Algorithm/DS_Algorithm

Growth of Function

0. Asymptotic Notations 알고리즘을 만들다 보면 알고리즘을 평가해야 할 때가 많습니다. 너무나 당연한 이야기지만 슈퍼컴에서 돌릴 때와 내 작고 귀여운 5년된 노트북에서 돌릴 때 성능 차이는 당연히 날 것입니다.(아주많이..ㅠ) 따라서 알고리즘의 성능을 평가할 때는 컴퓨터의 성능과는 관계가 없는 방법으로 평가를 하게 됩니다. 이를 Asymptotic Notation(점근표기법)이라고 합니다. 한국어 이름 '점근'에서 볼 수 있듯이, Asymptotic Notation에서는 'n을 무한대로 보냈을 때 소요되는 시간이 얼마나 걸리는가'를 기준으로 봅니다. 예를 들어 어떠한 알고리즘의 시간소요량이 f(n)=5n^2+8n+10이라고 합시다. 이 경우 n을 무한대로 보내면, 5n^2의 값이 8n에..

Coding_Algorithm/DS_Algorithm

Divide and Conquer 관점에서 본 Merge Sort

Divide and Conquer 관점에서 본 Merge Sort 0. 개요 지난 글에 이어서 오늘은 Divide and Conquer approach에 대해서 알아보고, 나아가 Merge Sort에 대해서 알아보도록 하겠습니다. 1. Divide and Conquer 먼저 Divide and Conquer에 대해서 알아봅시다. 말 그대로 Divide(분할)한 뒤 Conquer(정복)하는 개념입니다. 가장 중요한 것은 Divide - Conquer - Combine의 순서로 진행된다는 점입니다. 이전 글이었던 Incremental approach와의 차이점에 대해서 이야기하자면, Incremental approach는 작게 문제를 나누어서 해결한 작은 문제를 기반으로 더 큰 문제를 풀어나간다면, 문제를 ..