카데인 알고리즘은 배열에서 최대 부분 배열 합을 찾는 효율적인 방법입니다. 아래는 C 언어를 사용해 카데인 알고리즘을 구현한 5가지 방법으로, 코딩 테스트 준비에 유용합니다.
방법 1: 기본 카데인 알고리즘
기본적인 카데인 알고리즘으로, 현재 합과 최대 합을 비교하며 배열을 순회합니다.
#include <stdio.h>
int maxSubArray(int arr[], int n) {
int max_sum = arr[0], current_sum = arr[0];
for (int i = 1; i < n; i++) {
current_sum = (current_sum + arr[i] > arr[i]) ? current_sum + arr[i] : arr[i];
max_sum = (max_sum > current_sum) ? max_sum : current_sum;
}
return max_sum;
}
int main() {
int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = sizeof(arr) / sizeof(arr[0]);
printf("최대 부분 배열 합: %d\n", maxSubArray(arr, n));
return 0;
}
방법 2: 카데인 알고리즘 (음수 처리 명시적)
음수 배열을 명시적으로 처리하며, 초기 값을 INT_MIN으로 설정해 모든 경우를 다룹니다.
#include <stdio.h>
#include <limits.h>
int maxSubArray(int arr[], int n) {
int max_sum = INT_MIN, current_sum = 0;
for (int i = 0; i < n; i++) {
current_sum += arr[i];
if (current_sum > max_sum) max_sum = current_sum;
if (current_sum < 0) current_sum = 0;
}
return max_sum;
}
int main() {
int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = sizeof(arr) / sizeof(arr[0]);
printf("최대 부분 배열 합: %d\n", maxSubArray(arr, n));
return 0;
}
방법 3: 시작과 끝 인덱스 추적
최대 부분 배열의 시작과 끝 인덱스를 추적하여 합뿐만 아니라 범위도 반환합니다.
#include <stdio.h>
#include <limits.h>
int maxSubArray(int arr[], int n, int* start, int* end) {
int max_sum = INT_MIN, current_sum = 0;
int temp_start = 0;
*start = 0; *end = 0;
for (int i = 0; i < n; i++) {
current_sum += arr[i];
if (current_sum > max_sum) {
max_sum = current_sum;
*start = temp_start;
*end = i;
}
if (current_sum < 0) {
current_sum = 0;
temp_start = i + 1;
}
}
return max_sum;
}
int main() {
int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int start, end;
int max_sum = maxSubArray(arr, n, &start, &end);
printf("최대 부분 배열 합: %d (인덱스 %d부터 %d까지)\n", max_sum, start, end);
return 0;
}
방법 4: 동적 프로그래밍 접근
카데인 알고리즘을 동적 프로그래밍 방식으로 구현하여 각 위치에서의 최대 합을 저장합니다.
#include <stdio.h>
#include <stdlib.h>
int maxSubArray(int arr[], int n) {
int* dp = (int*)malloc(n * sizeof(int));
dp[0] = arr[0];
int max_sum = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = (dp[i - 1] + arr[i] > arr[i]) ? dp[i - 1] + arr[i] : arr[i];
if (dp[i] > max_sum) max_sum = dp[i];
}
free(dp);
return max_sum;
}
int main() {
int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = sizeof(arr) / sizeof(arr[0]);
printf("최대 부분 배열 합: %d\n", maxSubArray(arr, n));
return 0;
}
방법 5: 분할 정복 접근
카데인 알고리즘을 분할 정복 방식으로 구현하여 배열을 나눠 최대 합을 계산합니다.
#include <stdio.h>
#include <limits.h>
int max(int a, int b) { return a > b ? a : b; }
int maxCrossingSum(int arr[], int left, int mid, int right) {
int sum = 0, left_sum = INT_MIN, right_sum = INT_MIN;
for (int i = mid; i >= left; i--) {
sum += arr[i];
if (sum > left_sum) left_sum = sum;
}
sum = 0;
for (int i = mid + 1; i <= right; i++) {
sum += arr[i];
if (sum > right_sum) right_sum = sum;
}
return left_sum + right_sum;
}
int maxSubArray(int arr[], int left, int right) {
if (left == right) return arr[left];
int mid = (left + right) / 2;
return max(max(maxSubArray(arr, left, mid), maxSubArray(arr, mid + 1, right)),
maxCrossingSum(arr, left, mid, right));
}
int main() {
int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = sizeof(arr) / sizeof(arr[0]);
printf("최대 부분 배열 합: %d\n", maxSubArray(arr, 0, n - 1));
return 0;
}
각 방법은 시간 복잡도와 코드 단순성 측면에서 장단점이 있습니다. 기본 카데인 알고리즘(방법 1, 2)은 O(n)으로 효율적이며 코딩 테스트에서 가장 일반적입니다. 인덱스 추적(방법 3)은 추가 정보를 제공하고, 동적 프로그래밍(방법 4)은 명시적 메모리 사용, 분할 정복(방법 5)은 복잡하지만 이해를 돕습니다.
설명
- 방법 1: GCD를 이용한 LCM (유클리드 알고리즘 반복): LCM(a,b) = (a * b) / GCD(a,b) 공식을 사용하며, GCD는 반복적 유클리드 알고리즘으로 계산. 시간 복잡도 O(log min(a,b)).
- 방법 2: GCD를 이용한 LCM (유클리드 알고리즘 재귀): GCD를 재귀적으로 계산하여 LCM을 구함. 코드가 간결하지만 스택 오버플로우 가능성 주의.
- 방법 3: 소인수분해를 통한 LCM: 두 숫자의 소인수분해에서 각 소인수의 최대 지수를 곱하여 LCM을 계산. O(min(a,b))로 비효율적.
- 방법 4: 이진 GCD를 이용한 LCM: 이진 GCD 알고리즘(슈타인)을 사용하여 GCD를 구한 후 LCM 계산. 비트 연산으로 나눗셈 연산 감소.
- 방법 5: 배수 나열: 두 숫자의 배수를 나열하여 첫 번째 공통 배수를 찾음. O(max(a,b) * min(a,b))로 매우 비효율적이나 이해하기 쉬움.
각 코드 예시는 a=12, b=18일 때 출력 예시: LCM(12, 18) = 36을 생성합니다. 코딩 테스트에서 요구되는 정확성과 효율성을 고려하여 작성되었으며, 특히 방법 1과 2가 가장 실용적입니다.
댓글
댓글 쓰기