랄뚜기의 코딩일기

A greedy approach Pi/Wi를 내림차순으로 정렬한다.(Greedy) knapsack이 찰 때까지 item을 고른다. Implementation 1 Sort the item -> O(nlogn) Repeat the choice -> O(n) O(n+nlogn) = O(n logn) Implementation 2 Put the items in a heap -> O(n) Repeat the choice -> O(k logn) O(n+k logn) = ? Implementation2 방식으로 하면 k값에 따라 시간복잡도가 달라진다. 확실한 것은 가장 최악이 O(n logn)으로 Implementation1 방식보다 훨씬 효율적이다. Knapsack Example 2: n=6, W=10 Huffma..

Intractable은 아주 다루기 힘든이란 뜻으로 Intractable Problem이란 말 그대로 풀기 힘든 문제라는 뜻이다. 문제 P에 대한 효율적인 알고리즘은 발견 되지 않았지만, 그 문제가 많은 시간을 필요로 한다는 것을 증명한 사람도 없었다. 문제 P에 대한 exponential time algorithm 이 있지만 아무도 polynomial time algorithm을 찾을 수 없었고, P에 대한 exponential time algorithm이 존재하지 않음을 증명 할 수 있다. exponential time alogrithm 이 발견된 문제 중 가장 어려운 문제 그룹인 NP-Complete이 있는데 이 그룹의 문제에 대한 Polynomial time algorithm을 발견하면 expon..

Knapsack Problem 예를 들어 다음과 같은 option이 있고 이에 대한 Cost 와 Expected reach가 있다고 하자. 주어진 예산이 W가 될 것이고, Cost는 정의에서 w가 될 것이고 Expected reach는 p가 된다. Knapsack에서는 정해진 W를 넘지 않은 채로, Expected reach를 최대화 하는 것이 목적이다. 간단히 말하자면 주어진 예산 안에서 사람들이 최대한 많이 볼 수 있게 하는 것이 목적이다. Dynamic programming approach P(i,w)를 maximized profit, A*를 optimal subset이라고 가정하자. 그렇게 되면 위 처럼 두가지로 optimal subset에 포함되는 경우와 포함되지 않는 경우로 모든 경우의 수를 ..

The Gapped Alignment Problem 두개의 문자열이 주어졌을 때, score을 최대화하는 gapped alignment를 구하여라. match라면 1점, mismatch라면 -1점, gap이라면 -2점을 준다. 두개의 문자열이 주어졌을 때, Gapped Alignment가 생성되는 방법의 수는 3가지로 나오게 된다.(문자열 A,B가 있다고 가정) 1. 두 문자를 match하는 경우( 문자가 다를 수도 있음) 2. A의 문자열에 gap을 넣는 경우 3. B의 문자열에 gap을 넣는 경우 위를 식으로 표현하면 다음과 같다. #include #include using namespace std; // function to find out the minimum penalty void getMini..

The Checkerboard Problem cost table이 위와 같이 주어졌을 때, i=1에서 i=5까지 움직일 때, 최솟값을 찾는 문제이다. q(i,j) : the minimum cost to reach squrare(i,j)라고 할 때, 로 식을 짜게 되면 q[i][j]에는 최소값이 선언되게 된다. table P도 만들어서 어디서 왔는지 알려주면 된다. #include #define N 5 #define INFTY 100000 int c[N+1][N+2] = {-1,-1,-1,-1,-1,-1,-1, -1, 7, 3, 5, 6, 1,-1, -1, 2, 6, 7, 0, 2,-1, -1, 3, 5, 7, 8, 2, -1, -1, 7, 6, 1, 1, 4, -1, -1, 6, 7, 4, 7, 8, -..

위와 같은 문제가 있다고 하자. 위 식을 divde-and-conquer로 풀게 되면 1 (i=0,j>0) P(i,j)= 0 (i>0,j=0) (P(i-1,j)+P(i,j-1))/2 이 되고 T(n) = 2*T(n-1) + c가 되므로 O(2^n)이 되게 된다. 이를 해결하기 위해서는 중복된 값을 계산하지 않는 Dynamic Programming을 사용하면 된다. Source에서 sink까지 갈 때, 어떻하면 최댓값으로 갈 수 있을까? 경우의 수는 총 2^n*2^m으로 exponential하다. 하지만 직전의 것과만 비교하면 경우의 수가 n*m개로 줄게 된다. DP에서는 직전값들끼리 비교를하기 때문에 초깃값을 설정해주어야 한다. 2,3번은 초기값을 넣어준다는 말이다. 1 번은 직전것들끼리 비교하여 최댓값..

Selection of Both Maximum and Minimum Elements #define _CRT_SECURE_NO_WARNINGS #include #include struct Result { int minValue, maxValue; }; struct Result MAXMIN(int A[], int l, int r) { struct Result ret; if (l == r) { ret.minValue = ret.maxValue = A[l]; return ret; } else if (r - l == 1) { ret.minValue = (A[l] A[r] ? A[l] : A[r]); return ret; } stru..

Insertion Sort void insert_sort(int *A, int n){ int i,j,tmp; for(i =1;i0)&&(tmp

Divide : pivot element를 선택하고, pivot을 기준으로 subarray를 나누기 때문에 시간복잡도는 O(n)이다. Conquer : subarray를 recursive하게 정렬해준다. tree의 깊이에 비례하므로 시간복잡도는 O(logn)이고 subarray의 크기를 m1과 m2라고 했을 때, conquer의 비용은 T(m1)+T(m2)가 된다. combine : 할 필요가 없다.(O(1) or 0) void quick_sort(int *n, int left, int right){ int pivot; if(right-left>0){ //divide pivot=partition(n,left,right); //conquer quick_sort(n,left,pivot-1); quick_so..

Merge Sort Divide - merge sort에서 배열을 divide하는데 필요한 시간은 O(1)이다. (이미 배열의 index를 알고 있기 때문에) Conquer - 각각의 subarray를 recursive하게 sorting한다. T(n) = 2T(n/2)+cn Combine - 각각의 subarray를 merge하면서 sorted array로 바꿔준다. O(n) void merge_sort(int *n, int left, int right){ int middle; if(left