[BOJ] 백준 10211번 Maximun Subarray (Java)

#10211 Maximum Subarray

난이도 : 실버 3

유형 : DP/ 누적 합

10211번: Maximum Subarray

▸ 문제

크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있다.

여러분은 N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하자. 즉, max1 ≤ i ≤  j ≤ N (X[i]+...+X[j])를 구하자.

 

▸ 입력

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

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

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

 

▸ 출력

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

 

 

 

문제 풀이 🖋  

dp와 누적합을 사용하며 풀이하는 문제이다. 배열을 순차적으로 모두 조회하면서 그 중 누적합이 최대가 되는 구간을 찾으면 된다.

 

📚 조건

   ∙ 테스트 케이스의 수 T

   ∙ 배열의 크기 N (1 <= N <= 1,000)

   ∙ 배열에 들어있는 값 X ( |X| < 1,000)

 

(1 <= N <= 1,000) 해당 조건은 효율성에 크게 무리가 가지 않는 크기이다. 

 

누적 합 < 0이 되는 구간에 dp값을 0으로 초기화해준다. 누적합이 음수가 되는 순간 그 뒤에 있는 수들은 새로운 누적합(0)을 구하는게 더 최댓값을 가져오기 때문이다.

 

 

 

풀이 코드 ✔︎ 

한 가지 주의할 점은 idx가 0일 때 누적합이 최대일수도 있기 때문에 비교연산을 할 때 초기값을 arr[0]으로 해줘야한다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	
	static int[] arr;
	static int[] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int t = Integer.parseInt(br.readLine());
		for(int test =0; test<t; test++) {
			int n = Integer.parseInt(br.readLine());
			arr = new int[n];
			dp = new int[n];	
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int i=0; i<n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			solve();
		}
	}
	
	static void solve() {
		
		int max = arr[0];
		dp[0] = arr[0];
		for(int i=1; i<arr.length; i++) {
			if(dp[i-1] < 0) dp[i-1] =0;
			dp[i] = dp[i-1] + arr[i];
			max = Math.max(max, dp[i]);
		}
		System.out.println(max);
	}
	
}

 

+

분할정복의 방식도 한번 사용하면 좋을 것 같아서 연습해봤다.

 

 

mid를 기준으로 left, right로 나누어 계산해주는 방식이다.

 

arr[] = {2 1 -2 3 -5}이 있을 때 분할정복 방식은 다음과 같이 이루어진다.

분할정복 풀이

 

분할정복 풀이 코드 ✔︎  

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	
	static int[] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int t = Integer.parseInt(br.readLine());
		for(int test =0; test<t; test++) {
			int n = Integer.parseInt(br.readLine());
			arr= new int[n];
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			for(int i=0; i<n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			
			System.out.println(solve(0,n-1, arr));
			
		}
	}
	
	static int solve(int left, int right, int[] arr) {
		if(left == right) return arr[left];
		int mid = (left+right)/2;
		
		int mSide= divconq(left,right,mid,arr);
		int lSide = solve(left,mid, arr);
		int rSide =  solve(mid+1, right, arr);
		
		if(mSide >= lSide && mSide>= rSide) return mSide;
		else if(lSide >= rSide && lSide >= mSide) return lSide;
		else return rSide;
		
	}
	
	static int divconq(int left, int right, int mid, int[] arr) {
		int lSum=0, rSum=0;
		int lMax = Integer.MIN_VALUE;
		int rMax = Integer.MIN_VALUE;
		for(int i=mid; i>=0; i--) {
			lSum += arr[i];
			lMax = lSum > lMax? lSum : lMax;
		}
		
		for(int i=mid+1; i<right+1; i++	) {
			rSum += arr[i];
			rMax = rSum > rMax? rSum : rMax;
		}
		
		return rMax + lMax;
		
	}
}

 

 

이렇게 Optimal Substrue(최적 부분 구조)를 풀이하는데 Top-down 하향식으로 문제를 작게 쪼개어 답을 구하는 알고리즘은 DP와 분할정복이 동일하다. 단지 DP와 분할정복의 차이는 중복 부분 문제에 대한 처리 능력에 있다. 하위 문제 중복으로 인해 반복적인 연산량이 형성되는 경우 DP를 사용한다. 

 

어떻게 보면 분할정복 + 중복문제 해결  → DP라고 보면 된다.

 

분할정복 알고리즘 자체로도 이해를 하고 있어야 한다. 분할정복 알고리즘 종류로는 이분탐색, 합병정렬, 퀵정렬, 최대값 찾기, 임계값의 결정, 쉬트라센 행렬곱셈 등으로 많은 곳에서 활용된다.

 

분할정복 알고리즘 장단점은 Top-down이 그렇듯이 어려운 문제를 잘게 쉽게 쪼개주어 해결한다는 점이 있지만 재귀함수 호출방식으로 메모리를 많이 사용한다는 점이다.

 

 

분할 정복은 주말에 따로 포스팅을 해야겠다!