코린이의 소소한 공부노트

1. 전략: bottom-up approach 1) 문제의 가장 작은 단위부터 사용할 수 있는 반복문을 작성한다. 2) 가장 작은 문제부터 차례대로 풀어나간다. 3) 저장된 결과를 재사용한다. 3) divide and conquer와의 공통점 - 문제를 작게 쪼개서 해결한다. 4) divide and conquer와의 차이점 - DAC의 경우 top-down 형식이기 때문에 중복 계산이 여러 개 생겨날 수 있다. - DP는 bottom-up 형식이기 때문에 중복 계산이 생기지 않는다. 2. 예시 - binomial coefficient - Floyd's algorithm for shortest paths - traveling salesperson problem - chained matrix multipl..

1. Problem - n개의 key를 오름차순으로 정렬하자 2. Input 1) 양수 low 2) 양수 high 3) 배열 S indexed from 1 to n 3. Output 1) 오름차순으로 정렬된 배열 S 4. PseudoCode void mergesort2(index low, index high, keyptype[] S){ index mid; if(low

1. Problem - n개의 key를 오름차순으로 정렬하자 2. Input 1) 양수 n 2) 배열 S indexed from 1 to n 3. Output 1) 오름차순으로 정렬된 배열 S 4. PseudoCode void mergesort(int n, keytype[] S){ if(n>1){ const int h = n/2, m = n-h; keytype U[1..h], V[1..m]; copy S[1]~S[h] to U[1]~U[h]; copy S[h+1]~S[n] to V[1]~V[m]; mergesort(h,U); mergesort(m,V); merge(h,m,U,V,S); } } // 정렬된 배열 U와 V의 요소를 합해서 정렬된 S를 만든다. void merge(int h, int m, co..

1. Problem - 크기가 n인 정렬된 배열 S에서 x를 찾아보자 2. Input 1) 양수 n 2) 오름차순으로 정렬된 S indexed from 1 to n 3) key x 3. Output 1) x의 위치 2) S에 x가 없다면 0 4. PseudoCode index location(index low, index high){ index mid; if(low>high) return 0; else{ mid = floor((low+high)/2); if(x==S[mid]) return mid; else if(x 13 -> 18 static int location(int low, int high, int[] S, int x) { int answer; if(low>high) answer = 0; else..

1. 전략: top-down approach 1) 문제를 둘 이상의 작은 문제들로 쪼갠다. 2) 쪼갠 문제들을 각각 해결한다. - 쪼갠 문제가 충분히 작지 않다면 다시 쪼갠다. 3) 쪼갠 문제들이 해결되면 그 해답을 합친다. 2. 예시 - binary search - merge sort - quick sort - strassen's matrix multiplication - arithmetic with large numbers; representation, multiplication

1. Problem - n번째 피보나치 수를 반복문을 이용해 찾아보자 2. Input 1) 음이 아닌 정수 n 3. Output 1) n번째 피보나치 수 4. PseudoCode int fib2(int n){ index i; int[0...n] f; f[0] = 0; if(n>0){ f[1] = 1; for(i=2 ; i0) { f[1] = 1; for(int i=2 ; i

1. Problem - 피보나치 수열에서 n번째 수를 재귀함수를 이용해 찾아보자 2. Input 1) 음이 아닌 정수 n 3. Output 1) n번째 피보나치 수 4. PseudoCode int fib(int n){ if(n

1. Problem - 정렬된 배열에서 x를 찾아보자 2. Input 1) 양수 n 2) 오름차순으로 정렬된 배열 S indexed from 1 to n 3) key x 3. Output 1) x의 위치 2) x가 없다면 0을 반환 4. PseudoCode index binsearch(int n, const keytype S[], keytype x, index location){ index low, high, mid; low = 1; high = n; location = 0; while(low

1. Problem - 두 n*n 행렬의 곱(product)을 구해보자 2. Input 1) 양수 n 2) 2차원 배열 A indexed from 1 to n 3) 2차원 배열 B indexed from 1 to n 3. Output 1) A*B의 결과가 담긴 2차원 배열 C indexed from 1 to n 4. PseudoCode void matrixmult(int n, const number[][] A, const number[][] B, number[][] C){ index i, j, k; for(i=1 ; i

1. Problem - n개의 요소를 오름차순으로 정렬해보자. 2. Input 1) 양수 n 2) 배열 S indexed from 1 to n 3. Output 1) 오름차순으로 정렬된 S 4. PseudoCode void exchangesort(int n, keytype[] S){ index i, j; for(i=1 ; i