배열에서 최대값과 최소값을 찾는 문제는 코딩 테스트에서 기본적인 문제입니다. 아래는 C 언어를 사용해 배열의 최대/최소 요소를 찾는 5가지 방법으로, 코딩 테스트 준비에 유용합니다.
방법 1: 단순 순회
배열을 한 번 순회하며 최대값과 최소값을 동시에 갱신합니다.
#include <stdio.h>
#include <limits.h>
void findMaxMin(int arr[], int n, int* max, int* min) {
*max = INT_MIN;
*min = INT_MAX;
for (int i = 0; i < n; i++) {
if (arr[i] > *max) *max = arr[i];
if (arr[i] < *min) *min = arr[i];
}
}
int main() {
int arr[] = {4, 2, 7, 1, 9, -3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int max, min;
findMaxMin(arr, n, &max, &min);
printf("최대값: %d, 최소값: %d\n", max, min);
return 0;
}
방법 2: 첫 번째 요소 기준 순회
배열의 첫 번째 요소를 초기 최대/최소값으로 설정하고 나머지를 비교합니다.
#include <stdio.h>
void findMaxMin(int arr[], int n, int* max, int* min) {
*max = arr[0];
*min = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > *max) *max = arr[i];
if (arr[i] < *min) *min = arr[i];
}
}
int main() {
int arr[] = {4, 2, 7, 1, 9, -3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int max, min;
findMaxMin(arr, n, &max, &min);
printf("최대값: %d, 최소값: %d\n", max, min);
return 0;
}
방법 3: 분할 정복
배열을 재귀적으로 분할하여 최대값과 최소값을 찾습니다.
#include <stdio.h>
void findMaxMinRecursive(int arr[], int left, int right, int* max, int* min) {
if (left == right) {
*max = arr[left];
*min = arr[left];
return;
}
if (right - left == 1) {
*max = arr[left] > arr[right] ? arr[left] : arr[right];
*min = arr[left] < arr[right] ? arr[left] : arr[right];
return;
}
int mid = (left + right) / 2;
int left_max, left_min, right_max, right_min;
findMaxMinRecursive(arr, left, mid, &left_max, &left_min);
findMaxMinRecursive(arr, mid + 1, right, &right_max, &right_min);
*max = left_max > right_max ? left_max : right_max;
*min = left_min < right_min ? left_min : right_min;
}
int main() {
int arr[] = {4, 2, 7, 1, 9, -3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int max, min;
findMaxMinRecursive(arr, 0, n - 1, &max, &min);
printf("최대값: %d, 최소값: %d\n", max, min);
return 0;
}
방법 4: 쌍 비교
배열을 쌍으로 나누어 비교 횟수를 줄이며 최대값과 최소값을 찾습니다.
#include <stdio.h>
void findMaxMin(int arr[], int n, int* max, int* min) {
int i;
if (n % 2 == 0) {
*max = arr[0] > arr[1] ? arr[0] : arr[1];
*min = arr[0] < arr[1] ? arr[0] : arr[1];
i = 2;
} else {
*max = arr[0];
*min = arr[0];
i = 1;
}
for (; i < n - 1; i += 2) {
if (arr[i] > arr[i + 1]) {
if (arr[i] > *max) *max = arr[i];
if (arr[i + 1] < *min) *min = arr[i + 1];
} else {
if (arr[i + 1] > *max) *max = arr[i + 1];
if (arr[i] < *min) *min = arr[i];
}
}
}
int main() {
int arr[] = {4, 2, 7, 1, 9, -3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int max, min;
findMaxMin(arr, n, &max, &min);
printf("최대값: %d, 최소값: %d\n", max, min);
return 0;
}
방법 5: 정렬 후 선택
배열을 정렬한 후 첫 번째(최소)와 마지막(최대) 요소를 선택합니다.
#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
void findMaxMin(int arr[], int n, int* max, int* min) {
int* temp = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) temp[i] = arr[i];
qsort(temp, n, sizeof(int), compare);
*min = temp[0];
*max = temp[n - 1];
free(temp);
}
int main() {
int arr[] = {4, 2, 7, 1, 9, -3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int max, min;
findMaxMin(arr, n, &max, &min);
printf("최대값: %d, 최소값: %d\n", max, min);
return 0;
}
각 방법은 시간 복잡도와 코드 단순성 측면에서 장단점이 있습니다. 단순 순회(방법 1, 2)는 O(n)으로 효율적이며 코딩 테스트에서 가장 일반적입니다. 쌍 비교(방법 4)는 비교 횟수를 약간 줄일 수 있고, 분할 정복(방법 3)은 재귀 학습에 유용합니다. 정렬(방법 5)은 O(n log n)으로 비효율적이지만 직관적입니다.
설명 및 출력 예시
입력 배열: [4, 2, 7, 1, 9, -3, 5]
출력: 최대값: 9, 최소값: -3
- 방법 1: 단순 순회: 배열을 한 번 순회하며 최대/최소값을 갱신. 시간 복잡도 O(n), 공간 복잡도 O(1). 코딩 테스트에 가장 적합.
- 방법 2: 첫 번째 요소 기준 순회: 첫 번째 요소를 초기값으로 설정. 방법 1과 유사하며, INT_MIN/INT_MAX 없이 간단함. 시간 복잡도 O(n).
- 방법 3: 분할 정복: 재귀적으로 배열을 분할하여 최대/최소값 계산. 시간 복잡도 O(n), 공간 복잡도 O(log n) (재귀 스택). 교육적.
- 방법 4: 쌍 비교: 배열을 쌍으로 비교하여 비교 횟수를 약 3n/2로 줄임. 시간 복잡도 O(n), 실용적.
- 방법 5: 정렬 후 선택: 배열을 정렬하여 최대/최소값을 선택. 시간 복잡도 O(n log n), 공간 복잡도 O(n). 비효율적이지만 이해 쉬움.
특징
- 모든 코드는 동일한 배열 {4, 2, 7, 1, 9, -3, 5}를 사용하며, 최대값 9와 최소값 -3을 출력.
- 입력 배열 크기(n)는 동적으로 계산되며, 메모리 누수를 방지하기 위해 동적 할당 해제 포함(방법 5).
- 코딩 테스트에서는 방법 1 또는 2가 가장 실용적이며, 방법 4는 비교 최적화에 관심 있을 때 유용.
- 블로그용으로 깔끔한 HTML/CSS 스타일을 적용하여 코드 가독성을 높였습니다.
댓글
댓글 쓰기