728x90
Maximum Contiguous Subsequence Sum
n개의 정수 a1, a2, ..., an이 주어졌을 때 연속적인 부분수열의 합이 최대가 되는 구간의 합을 계산하시오.
리트코드 사이트의 문항을 이용해 코드로 연습해보았다.
https://leetcode.com/problems/maximum-subarray/
📍 [방법1] Brute-force
가능한 모든 부분 수열에 대해서 계산을 하고 이 중 가장 큰 합을 찾는다. index i는 부분 수열의 시작 인덱스를, j는 마지막 인덱스를 의미한다. 단순하지만 O(n^3)만큼의 시간복잡도를 가진다. 매우 효율적이지 않다.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int localSum = 0;
int globalSum = 0;
int start, end;
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
localSum = 0;
for(int k=i;k<=j;k++){
localSum += nums[k];
}
if(localSum>globalSum){
start = i; end = j;
globalSum = localSum;
}
}
}
cout<<start<<" "<<end<<endl;
return globalSum;
}
};
📍 [방법 2] 방법1의 개선
O(n^3)의 시간복잡도를 가지는 브루트포스를 O(n^2)로 개선할 수 있다. i부터 j까지의 부분수열을 계산하는 과정에서 반복문을 사용하지 않고 합을 누적하면서 비교하는 것이다. 다음 숫자 하나만 더 해주면 되므로 다시 처음부터 계산할 필요가 없기 때문이다.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int globalSum = 0;
int localSum = 0;
for(int i=0;i<n;i++){
localSum = 0;
for(int j=i;j<n;j++){
localSum += nums[j];
if(localSum>globalSum){
globalSum = localSum;
}
}
}
return globalSum;
}
};
📍 [방법3] 카데인 알고리즘(Kadane's Linear Algorithm)
카데인 알고리즘을 이용하면 O(n)만에 답을 구할 수 있다. 카데인 알고리즘은 DP(동적 프로그래밍)을 이용한 것이다. 너무 헷갈렸다 ....
DP를 이용한 부분은 i번째 원소까지의 최대 합은 (i-1번째 원소까지의 최대합+i번째 원소) 혹은 i번째 원소가 된다는 것이다. ...
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int globalMax = nums[0];
int localMax = nums[0];
for(int i=1;i<n;i++){
localMax = max(nums[i],localMax+nums[i]);
globalMax = max(globalMax, localMax);
}
return globalMax;
}
};
728x90
반응형
'알고리즘' 카테고리의 다른 글
[알고리즘] 정렬알고리즘 #4 합병정렬 (Merge Sort) (0) | 2024.10.23 |
---|---|
[알고리즘] 정렬알고리즘 #3 버블정렬 (Bubble Sort) (1) | 2024.10.22 |
[알고리즘] 정렬알고리즘 #2 선택정렬 (Selection Sort) (0) | 2024.10.22 |
[알고리즘] 정렬알고리즘 #1 삽입정렬 (insertion Sort) (1) | 2024.10.22 |
[알고리즘] 유클리드 알고리즘(유클리드 호제법) (1) | 2023.12.20 |