백준10211(Maximum Subarray)

jh Seo·2022년 12월 28일
0

백준

목록 보기
112/179

개요

백준 10211번: Maximum Subarray

  • 입력
    입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

    각 테스트케이스 별로 첫 번째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000)

    그리고 두 번째 줄에 배열 X의 내용을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 이때 주어지는 수는 절댓값이 1,000보다 작은 정수이다.

  • 출력
    각 테스트케이스 별로 maximum subarray의 합을 줄로 구분하여 출력한다.

접근방식

처음에 접근한 방식

  1. 부분배열의 합을 미리 Sum배열을 선언하여 입력값을 받을때 바로바로 저장을 해준다면
    부분배열의 합을 계산할때 빠르게 가능하다.

    	for (int i = 0; i < T; i++) {
    		cin >> N;
    		for (int j = 0; j < N; j++) {
    			cin >> inputArr[j];
    			//Sum[i+1]배열은 i번째 까지의 합 
    			Sum[j + 1] = Sum[j] + inputArr[j];
    		}
           
  2. 그냥 브루트포스 방식으로 , 부분배열의 합을 다 구해놓은 뒤,
    몇번째 배열에서 몇번째 배열을 뺐을 때 가장 큰지 구하는 식으로 구현하였다.

    //0부터 N까지의 index내에서 최대 부분배열 찾는 함수
    int Solution() {
    	if (N == 1) return Sum[1];
    	//싹다 음수일수도있으므로 최소값 0으로 잡으면 안 될듯
    	int maxSum= -1'000'001;
    	// 첫번째 원소를 포함헤야하므로 0부터 시작해서 인덱스N까지 포함해야함 
    	for (int i = 0; i < N; i++) {
    		for (int j = i+1; j < N+1; j++) {
    			maxSum = maxSum> Sum[j] - Sum[i]? maxSum: Sum[j]-Sum[i];
    		}
    	}
    	return maxSum;
    }

0번째 인덱스부터 다 더해가며 음수면 0으로 초기화하며 최대값 구하는 방식

하지만 위와 같은 방식이면, 케이스가 커지게되면 시간초과가 나는 방식이다.
따라서 테케당 O(N)의 시간복잡도를 유지하려면

int Solution() {
	//싹다 음수일수도있으므로 최소값 0으로 잡으면 안 될듯
	int maxSum= -1'000'001, tmpSum=0;
	if (isAllElemNeg) {
		for (int i = 0; i < N; i++) {
			maxSum = maxSum > inputArr[i] ? maxSum : inputArr[i];
		}
	}
	else {
		// 어차피 연속된 합이 음수가 아닌이상 최대값임 
		for (int i = 0; i < N; i++) {
			tmpSum += inputArr[i];
			//만약 더했는데 음수가나오면 최대값이 될수없으므로 0으로 초기화
			if (tmpSum < 0) tmpSum = 0;
			//매번 비교해서 최대값 갱신 
			maxSum = maxSum > tmpSum ? maxSum : tmpSum;
		}
	}
	return maxSum;
}

이런식으루 모든 원소가 음수인지 체크하는 isAllElemNeg변수로 체크 한 후,
모든 원소가 음수라면 제일 큰 원소 출력하고, 아니라면 차례대로 더하면서
음수면 0으로 초기화하고 다시 더하는 방식으로 최대 부분수열값 출력한다.

다이나믹 프로그래밍을 통한 방식

바로 위의 방식과 비슷하게 다이나믹 프로그래밍 방식으로도 풀 수 있는데,
각 dp배열마다 이전 단계의 최대합에 이번 원소 더한값과, 이번원소값만 비교해서
최대값 갱신하며 푸는 방식이다.
매번 비교할때마다 현재까지의 최대값 갱신해주면 답이 된다.

		for (int j = 0; j < N; j++) {
			cin >> inputArr[j];
			dp[j + 1] = max(dp[j] + inputArr[j], inputArr[j]);
			maxSum = max(maxSum, dp[j + 1]);
		}

첫 번째 방식 코드

#include<iostream>

using namespace std;
int inputArr[1001];
int Sum[1002];
int T = 0, N = 0;

//0부터 N까지의 index내에서 최대 부분배열 찾는 함수
int Solution() {
	if (N == 1) return Sum[1];
	//싹다 음수일수도있으므로 최소값 0으로 잡으면 안 될듯
	int maxSum= -1'000'001;
	// 첫번째 원소를 포함헤야하므로 0부터 시작해서 인덱스N까지 포함해야함 
	for (int i = 0; i < N; i++) {
		for (int j = i+1; j < N+1; j++) {
			maxSum = maxSum> Sum[j] - Sum[i]? maxSum: Sum[j]-Sum[i];
		}
	}
	return maxSum;
}

void Input() {
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N;
		for (int j = 0; j < N; j++) {
			cin >> inputArr[j];
			//Sum[i+1]배열은 i번째 까지의 합 
			Sum[j + 1] = Sum[j] + inputArr[j];
		}
		cout<<Solution()<<'\n';
	}
}



int main() {
	Input();
}

두 번째 방식 코드

#include<iostream>

using namespace std;
int inputArr[1001];
int T = 0, N = 0;
//모든 원소 음수인지
bool isAllElemNeg = true;

//0부터 N까지의 index내에서 최대 부분배열 찾는 함수
int Solution() {
	//싹다 음수일수도있으므로 최소값 0으로 잡으면 안 될듯
	int maxSum= -1'000'001, tmpSum=0;
	if (isAllElemNeg) {
		for (int i = 0; i < N; i++) {
			maxSum = maxSum > inputArr[i] ? maxSum : inputArr[i];
		}
	}
	else {
		// 어차피 연속된 합이 음수가 아닌이상 최대값임 
		for (int i = 0; i < N; i++) {
			tmpSum += inputArr[i];
			//만약 더했는데 음수가나오면 최대값이 될수없으므로 0으로 초기화
			if (tmpSum < 0) tmpSum = 0;
			//매번 비교해서 최대값 갱신 
			maxSum = maxSum > tmpSum ? maxSum : tmpSum;
		}
	}
	return maxSum;
}

void Input() {
	cin >> T;
	for (int i = 0; i < T; i++) {
		isAllElemNeg = true;
		cin >> N;
		for (int j = 0; j < N; j++) {
			cin >> inputArr[j];
			if (inputArr[j] > 0) isAllElemNeg = false;
		}
		cout<<Solution()<<'\n';
	}
}



int main() {
	Input();
}

세번째 방식 코드

#include<iostream>
#include<algorithm>

using namespace std;
int inputArr[1001];
int dp[1002];
int T = 0, N = 0, maxSum = -1'000'001;

void Input() {
	cin >> T;
	for (int i = 0; i < T; i++) {
		maxSum = -1'000'001;
		cin >> N;
		for (int j = 0; j < N; j++) {
			cin >> inputArr[j];
			dp[j + 1] = max(dp[j] + inputArr[j], inputArr[j]);
			maxSum = max(maxSum, dp[j + 1]);
		}
		cout<<maxSum<<'\n';
	}
}



int main() {
	Input();
}

문풀후생

첫번째 방식에선 인덱스 N을 포함시켜줘야 해서 j의 인덱스를 i+1부터 N까지 설정해줘야한다.
두번째 방식으로 푸는 과정에선 isAllElemNeg변수를 매 실행 마다 초기화를 안시켜줘서 많이 헤멨다.

profile
코딩 창고!

0개의 댓글