'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..

Knapsack Problem(배낭채우기 문제) 배낭채우기 문제는 최대용량 w를 가지는 배낭에 각각 다른 값어치,무게를 가지는 물건들을 넣을 때, 총 값어치(배낭에 넣은 물건들의 값어치의 합)가 최대가 되도록 물건들을 골라서 넣는 경우를 찾는 문제이다. 배낭에 책을 담으려고 한다. 배낭의 최대 용량은 W이며, 이를 초과해서 책을 담으면 배낭이 찢어질 것이다.각 책의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 책을 담는 방법은? knapsack problem 에는 두가지 버전이 있다. 0-1 Knapsack problem :배낭에 물건을 담거나, 안담거나. -Dynamic Programming 을 사용한다. Fractional Knapsack Problem: 배낭에 물..

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 에 대한..

1. 개요 DP(동적 계획법)은 큰 문제를 작은 부분문제들로 나누어서 푸는 하나의 문제해결 패러다임이다. 작은 문제들의 결과를 저장했다가 큰 문제를 풀때 재활용한다. 2. 목적 DP를 사용하는 이유는 일반적인 재귀는 동일한 작은 문제들을 반복해서 계산하기 때문에 비효율인 계산으로 시간이 오래걸리기 때문이다. ex) 피보나치 수열 피보나치 수열은 다음과 같다 1 1 2 3 5 8 13 21 34 55... 이를 재귀함수로 나타내면 f(n) = f(n-1) + f(n-2) 이다. f(5)를 재귀트리로 나타내면 아래와 같다. 이때 f(3)에서 f(2)를 계산했으나 f(4)에서 f(2)를 또 구해야 한다. 이러한 이유로 계산수가 기하급수적으로 늘어나게 되는데 이런 문제점을 저장했다가 다시 사용하는 방식으로 DP..