프로젝트 도중 인기여행지, 여행지 지역 카테고리에 따른 데이터 반환이 느려 이를 해결했다. 여행지 지역카테고리에 대해서는 (도,시)의 복합인덱스를 사용하였다.복합인덱스여러개의 컬럼을 함께 사용하여 만든 인덱스.  효과적인 이유?다음 예를 보자SELECT * FROM TABLEWHERE columnA = 1 AND columnB = 1 이때 복합인덱스가 아닌, A 혹은 B로 인덱스를 형성한다면 DB에서 카디널리티가 높은 컬럼에 대해 인덱스를 활용한다. 그 후, 나머지 조건에 대한 필터링은 서버 엔진으로 전달해서 실행하는데 이는 cpu, 메모리 리소스를 더 많이 사용한다.A의 인덱스를 활용했고 A = 1에 관한 데이터가 1000개 라면, 1000개의 데이터를 얻고 서버엔진에서 B = 1에 대해 필터링을 한다..

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