코린이의 소소한 공부노트

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

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