Max_Min 알고리즘
최대값과 최소값을 구하는 알고리즘
1. 메인 함수
1 2 3 4 5 6 7 8 9 10 |
int main(int argc, char** argv) { int A[9] = {9, 3, 2, 0, 5, 18, 8, 11, 16}; int n = sizeof(A) / sizeof(A[0]); int tmax=-999, tmin=999; seq_max_min(A, n); max_min(A, 0, 8, &tmax, &tmin); printf("Divide Conquor Method Max : %d, Min : %d\n", tmax, tmin); return 0; } |
2. 순차 알고리즘
1 2 3 4 5 6 7 8 9 |
void seq_max_min(int A[], int n){ int tmax=-999, tmin=999; for(int i=0; i<n; i++){ if(tmax < A[i]) tmax = A[i]; if(tmin > A[i]) tmin = A[i]; } printf("Sequence Method Max : %d, Min : %d\n", tmax, tmin); } |
3. 분할 정복 방법 사용
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
void max_min(int A, int i, int j, int *tmax, int *tmin){ if(i == j){ *tmax = A[i]; *tmin = A[i]; } else if(i == j-1){ if(A[i] < A[j]){ *tmax = A[j]; *tmin = A[i]; } else{ *tmax = A[i]; *tmin = A[j]; } } else{ int gmax, gmin, hmax, hmin, middle; middle = (i+j)/2; max_min(A, i, middle, &gmax, &gmin); max_min(A, middle+1, j, &hmax, &hmin); *tmax = (gmax > hmax)? gmax : hmax; *tmin = (gmin < hmin)? gmin : hmin; } } |