본문 바로가기

Algorithm

[C code] 계수 정렬 (Counting Sort) 첫번째 방법 - 기존의 Array 정렬 #include #include // Function to sort an array using counting sort void CountingSort(int arr[], int n) { //in arr, max value == max == counting_arr max index int max = 0 , i; for(i=0 ; i max) max = arr[i]; } int output_arr[n]; int counting_arr[max]; for(i=0 ; i output_arr[6] = 5; (후에 output_arr[6]--;) ... arr[0]의 값인 1 -> counting_arr[1]의 값인 0 -> output_arr[0] = 1; ​ -Geeksf.. 더보기
[C code] 삽입 정렬 (Insertion sort) #include #include // Function to sort an array using insertion sort void InsertionSort(int arr[], int n) { int key, i, j; for(i=0 ; i=0 && arr[j]>key) { arr[j+1] = arr[j]; j--; } arr[j+1] = key; } } /* Function to print an array */ void PrintArray(int arr[], int size) { printf("\n**********************\n"); for(int i=0 ; i 더보기
[C code] 버블 정렬 (Bubble sort) #include #include void Swap(int *xp, int *yp) { int temp = *xp; *xp = *yp; *yp = temp; } // A function to implement bubble sort void BubbleSort(int arr[], int n) { int i, j; for (i = n-1 ; i > 0 ; i--) // arr[n-1] ~ arr[1] put bigger number { for (j = 0 ; j arr[j+1]) Swap(&arr[j], &arr[j+1]); } } } /* Function to print an array */ void PrintArray.. 더보기
[C code] 피보나치 수열 (동적계획법 ; DP) Dynamic Programming은 전체 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법들을 결합하여 최종 문제를 해결하는 문제 해결 방식이다. 피보나치 수열을 구현할 때, #include #include int fibonacci(int n, int* z, int* o)//num & zero & one { if (n == 0) { (*z)++; return 0; } else if (n == 1) { (*o)++; return 1; } else { return fibonacci(n-1, z, o) + fibonacci(n-2, z, o); } } int main() { int cnt, zero, one; int num; scanf("%d", &cnt); for(int i=0 ; i 더보기
[C code] 보이어-무어 알고리즘 (Boyer-Moore Algorithm) 앞서, 아래 PDF가 이해하기 쉽게 잘 나와있음 http://www.cs.jhu.edu/~langmea/resources/lecture_notes/boyer_moore.pdf 보이어-무어 알고리즘 Boyer-Moore Algorithm 대부분의 워드 검색 기능에서 채택되어 사용되는 알고리즘 ​ 나쁜 문자 이동 (Bad Character Method)와 착한 접미부 이동 (Good Suffix Method) 의 방법이 있음 본 게시글은 나쁜 문자 이동 방법을 다룸 ​ 나쁜 문자 이동 1) 나쁜 문자 발견 2) 패턴의 나쁜 문자와 본문 문자열의 나쁜 문자 위치를 일치하도록 패턴 이동 +) 불가한 경우 -> 문자열의 나쁜 문자 위치보다 패턴의 나쁜 문자 위치가 뒤쪽인 경우 -> 착한 접미부 이동 방식 이용 o.. 더보기

티스토리툴바