코린이의 소소한 공부노트

1. Problem - nCk를 계산해보자. 2. Input 1) 음이 아닌 정수 n 2) 음이 아닌 정수 k - 이때 k

1. Problem - nCk를 계산해보자. 2. Input 1) 음이 아닌 정수 n 2) 음이 아닌 정수 k - 이때 k

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*n 행렬의 곱을 해보자. 여기서 n은 2의 거듭제곱이다. - 슈트라센은 행렬을 4개로 나눠서 계산하는 방식을 택했다. 2. Input 1) 행렬의 길이 n 2) n*n 행렬 A 3) n*n 행렬 B 3. Output 1) A와 B의 곱이 담긴 행렬 C 4. PseudoCode void strassen(int n, matrix A, matrix B, matrix C){ if(n

1. Problem - n개의 key를 오름차순으로 정렬해보자 - 퀵 정렬은 특정 값(pivot)을 기준으로 그 값보다 작은 것과 큰 것으로 나눠서 정렬한다. 2. Input 1) 양수 n 2) 배열 S 1-indexed 3. Output 1) 오름차순으로 정렬된 S 4. PseudoCode void quicksort(index low, index high){ index pivotpoint; if(low 작은 값(1)의 인덱스 -> 작은 값과 pivot의 위치를 바꾼다. -> 1 {2} 6 3 5 4 // -> pivot이었던 2의 위치는 확정됐고, 2의 위치를 기준으로 왼쪽은 2보다 작은 값, 오른쪽은 큰 값이 된다. // 2를 기준으로 나눠진 왼쪽과 오른쪽에 대해서도 퀵 정렬을 똑같이 진행한다. //..

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