'The Influences of Caches on the Performance of Sorting '리뷰 O(nlogn) 정렬 알고리즘이 O(n)정렬 알고리즘보다 빠르다??1. Introduction:Cache miss penalty의 문제가 performance에 큰 영향을 미침 & instruction count를 최소화 하기 위한 알고리즘이 필요.ex) radix sort는 lowest instruction count가 있으나, poor cache performance로 인해 merge sort, quicksort에 비해 성능이 떨어진다.이 논문의 목적은 4개의 정렬 알고리즘: heapsort, mergesort, quicksort, radixsort 를 cache의 측면에서 개선(메모리 최적화를..

2023.08.20 - [CS(Computer Science)/Algorithm] - DynamicProgramming(DP)-알고리즘08 그리디 알고리즘(탐욕법) 그리디 알고리즘(탐욕법): 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 방법이다. 그러니까 어떤 문제를 풀기위하여 여러 단계를 거쳐 갈때, 각 단계에서 최적의 선택을 선택 해 나가면서 최적해에 도달하는 방법이다. 사용 예시) A에서 B를 거쳐서 C까지 가는 최단경로는? A->B 최적의 방법:150km B->C로 최적의 방법: 140km 따라서 A->B->C의 최단경로는 290km 그러나 그리디 알고리즘은 언제나 최적의 해답을 구하지는 못한다. 아래를 보자. 다음 트리에서 가장 숫자가 큰 노드를 선택 하여라.(R..

1. LCS? 우선 아래 개념부터 확인하고 출발하자. Subsequence vs Substring Substring: 문자열에서 연속된 부분 문자열 ex) abcde-> ace 는 substring 아님. abcde->abc 는 substring Subsequence: 문자열에서 연속된 문자열이 꼭 아니어도 되는 부분 문자열 ex) abcde-> ace 도 subsequence Common Subsequence: 두 문자열중 공통된 subsequence ex) abcde, bzxchje -> 'bce' 따라서 LCS란, 두 문자열 사이에서, 가장 긴 공통 부분 문자열(Longest Common Subsequence)을 뜻한다. 두 문자열이 주어졌을 때, LCS를 어떻게 찾을까? 2.DynamicProgr..

막대 자르기(Rod cut algorithm) 길이가 n인 막대와 i = 1,2,3,...,n에 대한 가격 $ p_{i} $의 표가 주어지면 해당 막대를 잘라서 판매했을떄 얻을 수 있는 최대수익 $r_{n}$을 결정한다. 길이가 n인 막대의 가격 $p_{n}$이 충분히 비싸면 최적해는 자르지 않은 것일 수도 있다. 아래 예시를 보자. n=4 일 때, 위의 그림은 길이가 4인 막대를 자르는 방법을 모두 보여준다. 길이 4의 막대를 길이 2의 막대 두개로 나누면 최적의 수익으로 $ p_{2} $ + $ p_{2} $ = 5 + 5 = 10 이 발생함을 알 수 있다. 브루트포스 길이가 n인 막대는 $2^{n-1}$ 개의 다른 방법으로 나눌 수 있는데 제일 왼쪽에서 부터 i = 1,2,3,...,n-1 에 대한..

Worst Case Partitioning 퀵 정렬의 수행시간은 분할 후 양쪽 구역의 크기가 비슷한지 그렇지 않은지에 따라 달라진다. 즉 퀵 정렬에서 pivot을 기준으로 분할을 할 때, pivot이 무엇이냐에 따라 연산횟수가 달라진다. 연산횟수를 최대로 만드는 pivot은 무엇일까? 일단 퀵 정렬의 시간복잡도는 T(n)= T(q) + T(n-q-1) + O(n) 이었다. 여기서 q가 n-1이라면 T(n)= T(n-1) + T(1) + O(n) = T(n-2) + T(1) + O(n-1) + T(1) + O(n) =... 이다. 한마디로 배열을 n-1개짜리와 1개짜리 로 분할을 하는 pivot을 선택하는 것이 퀵정렬에서의 최악의 경우이다. 따라서 T(n)=O(n^2) 인데 이를 증명하자. 재귀트리를 이용..

퀵정렬 많은 정렬 알고리즘 중에 퀵정렬을 다뤄본다. 퀵정렬을 공부하다보면 얻게 되는 것이 많다. Divide and Conquer(분할정복) , Pivot , Partition 에 대한 개념을 같이 공부하게 된다. 퀵 정렬은 다음과 같은 과정으로 정렬을 한다. (Input=array:ARR[0]) 1. 배열의 원소중 하나를 골르는데 이를 pivot이라고 한다. 2. pivot보다 큰 값의 원소들은 pivot의 오른쪽으로, pivot보다 작은 원소들은 pivot의 왼쪽으로 자리를 옮긴다 (partition) 3. pivot을 기준으로 왼쪽 배열과 오른쪽 배열을 분할을 해서 각각의 배열에 대해 1,2의 과정을 반복한다. (Divide and Conquer) pivot을 정하는 방법과 partition의 방법..