Maximum Subarray - 백준10211, leetcode 53 알고리즘 성능 비교

• 백준 문제 : https://www.acmicpc.net/problem/10211
• leetCode 문제 : https://leetcode.com/problems/maximum-subarray/description/

10211번: Maximum Subarray

Maximum Subarray - LeetCode

 

 

두 문제의 요지는 최대부분배열 Maximum Subarray)합을 구하는 것이다.

(개인적으로 성능이나 테스트 케이스가 정확히 나오는 leet code를 선호하는 편..)

 

최대부분배열합이란?

→ 연속된 배열 중 합이 가장 큰 서브배열 (음수가 섞여있다)

1. brute-force solution

→ 부분배열의 시작점을 i, j라고 할때(1≤ i ≤ j ≤ n) i와 j 값을 모두 대입해보는 방법

if __name__ == "__main__":
	TCNum = int(input())
	for n in range(0,TCNum) :
	    size = int(input())
	    array = [int(x) for x in input().split()]
	    max = array[0]
			# 이중 포문을 이용해 모든 가능성을 비교한다. 
	    for i in range(0,size):
	        sum = 0
	        for j in range(i,size):
	            sum += array[j]
	            if max <= sum :
	                max = sum
	    print(max)

해당 코드 실행시간은 배열 size * size 따라서 O(n²)이라고 볼 수 있다.

실행결과 :

백준 알고리즘에서는 통과했지만 leet code에선 201번째 테스트케이스에서 무려 타임 리밋이 나버렸다..;;

 

2. divide-and-conquer solution

→ 배열을 왼쪽 오른쪽으로 나누어 두 부분에서 최대배열 합을 찾고, 두 부분을 관통하는 부분에서 최대배열 합을 찾는 방식

def findMax(arr, low, high):
	if low == high:
	    return arr[low]
	else:
		mid = int((low + high)/2)
		Lsum = findMax(arr,low,mid)
		Rsum = findMax(arr,mid+1,high)
		Msum = findMidMax(arr,low,mid,high)
		return max(Lsum,Rsum,Msum)

def findMidMax(arr,low,mid,high):
	Lsum = float("-inf")
	Rsum = float("-inf")
	sum = 0
	for i in range(mid,low-1,-1):
		sum = sum + arr[i]
		if sum > Lsum:
			Lsum = sum
	sum = 0			
	for j in range(mid+1,high+1):
		sum = sum + arr[j]
		if sum > Rsum:
			Rsum = sum
	return Lsum+Rsum

if __name__ == "__main__":
	TCNum = int(input())
	for n in range(0,TCNum) :
	    size = int(input())
	    array = [int(x) for x in input().split()]
	    print(findMax(array, 0, size-1))

merge sort와 비슷한 방식으로 실행시간은 O(nlogn) 이라고 볼 수 있다.

실행결과 :

brute force처럼 런타임에러는 나지 않지만 썩 성능이 좋아보이지도 않는다 ㅋㅋ..

그도 그럴것이 이 문제 해결법 중에 선형 O(n)으로 푸는 방법이 있다는데 ..

 

3.  추후에 정리... 

 

+) 결과 비교시

백준에서 두 결과 비교시 시간복잡도가 O(n²)과 O(nlogn) 풀이법의 시간이 현저히 차이나는 것을 볼 수 있다.