https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog
https://www.acmicpc.net/problem/1912
문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
예제 입력 1
10
10 -4 3 1 5 6 -35 12 21 -1
예제 입력 2
10
2 1 -4 3 4 -4 6 5 -5 1
처음에 DP로 DP를 2차배열로 만들고 이중 for문을 사용하였으나, 메모리초과가 발생하였다.
다음으로 DP를 1차배열로 만들고 이중 for문을 하나만 사용하였으나, 시간초과가 발생하였다.
첫 시도: 틀린답
def solution(nums):
N = len(nums)
largest_num = max(nums)
# 1차원 dp 배열로 변환
dp = [0] * N
for i in range(N):
dp[i] = nums[i]
current_sum = nums[i]
for j in range(i + 1, N):
current_sum += nums[j]
dp[i] = max(dp[i], current_sum)
if dp[i] > largest_num:
largest_num = dp[i]
return largest_num
if __name__=="__main__":
N = int(input())
nums = list(map(int, input().split()))
print(solution(nums))
현재 코드의 시간 복잡도는 O(N^2)입니다. 이는 모든 구간의 합을 일일이 계산하고 그 중에서 최대값을 찾는 방식이므로, N이 클 경우 성능 문제가 발생할 수 있습니다.
이 문제는 카데인 알고리즘(Kadane's Algorithm) 을 사용하여 시간 복잡도를 O(N)으로 줄일 수 있습니다. 카데인 알고리즘은 연속된 부분 배열 중 가장 큰 합을 구하는 효율적인 알고리즘입니다.
1차원배열로 1중 for문으로 구현이 필요하다.
각 원소 i마다 그 앞의 부분합을 구할 필요는 없음.
즉, 부분합을 구해서 배열에 넣고 dp에 저장해봐야 메모리 초과, 시각 복잡도만 증가한다.
매 수간 '현재까지의 연속합'과 '현재 값' 간의 최대값을 정하자.
'현재값'이 '현재까지의 연속합'보다 크면, 이제 '현재값'부터 시작이다.
정답
def solution(nums):
# 현재까지의 최대 부분합과 전체 최대 부분합 초기화
current_sum = nums[0]
largest_sum = nums[0]
for i in range(1, len(nums)):
# 이전까지의 합(current_sum)과 현재 숫자(nums[i]) 중 더 큰 값 선택
current_sum = max(nums[i], current_sum + nums[i])
# 전체 최대 부분합 갱신
largest_sum = max(largest_sum, current_sum)
return largest_sum
if __name__=="__main__":
N = int(input())
nums = list(map(int, input().split()))
print(solution(nums))
설명하자면
10 -4 3 1 5 6 -35 12 21 -1
에서
-35와 -35까지의 연속합 -14 중 더 큰 값은 -14이다. 가장 큰 연속합은 (10-4+3+1+5+6=21)이다.
12와 12까지의 연속합 -2 중 더 큰 값은 12이다. 여전히 가장 큰 연속합은 (10-4+3+1+5+6=21)이다.
즉 '이전까지의 연속합'+'현재 값'과 '현재 값'부터 시작 중
'현재 값'이 더 커지면 이제 '현재 값'부터 연속합을 살펴보면 된다.
그러나 이전에 연속합 중 가장 최적의 값은 여전히 기억 중 이다. (10-4+3+1+5+6=21)
그러다가 12+21로 연속합 값이 이전 가장 큰 연속합 값보다 커지면
갱신된다.
다른 사람 풀이
def solution(nums):
for i in range(1, len(nums)):
nums[i] = max(nums[i], nums[i] + nums[i-1])
return max(nums)
if __name__=="__main__":
N = int(input())
nums = list(map(int, input().split()))
print(solution(nums))
와우
