백준 1912 - 연속합

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

해당 문제는 답이 나오긴 했는데 시간 초과 때문에 통과되지 못했다.

뿌엥

그래서 구글링을 해봤더니..굉장히 간결하게.. WOW.. 쩝ㅋ

 

시간초과 나온 풀이코드는 굉장히 여러 개가 있었는데 그 중 가장 마지막까지 수정한 코드는 다음과  같다.

n = int(input())
result = []
flag = 0
nums = list(map(int, input().split()))
a = -1e9
maxi = max(nums)
if maxi > 0:
    for i in range(len(nums)-1):
        s = 0
        cnt = 0
        if len(result) !=0:
            a = min(result)

        if nums[i] > 0:
            for j in range(i, len(nums)):
                if nums[j] < 0:
                    if s > maxi:
                        maxi = s
                s += nums[j]
                if s <0 or s<a:
                    break
                if j == len(nums)-1:
                    if s > maxi:
                        maxi = s
                if cnt == 0 and nums[j]<0:
                    cnt += 1
                    flag = j
        i = flag + 1

print(maxi)

시간초과가 나온 코드이지만 어떤 알고리즘을 짰는지 정리를 하자면 다음과 같다.

1. 숫자 리스트를 입력 받고 그 리스트의 최대값을 구한다.

만약 최대값이 0보다 작거나 같을 경우 해당 리스트는 양수가 하나도 들어가지 않았기 때문에 여러 반복문을 돌면서 연속합의 최대를 구해볼 가치가 없다.

 

2. 이중 반복문을 사용해서 연속합을 구하고자 했다. 만약 연속합 계산을 시작하는 i번째 숫자가 양수일 경우에만 연속합을 계산할 수 있도록 하였다. 

 

3. 이중 반복문 안에 보면 만약 연속합 계산을 시작하는 i번째 숫자가 양수일 경우, j가 i부터 끝까지 반복문을 돌며 연속합을 계산하기 시작하는데 이 때 j번 째 숫자가 음수일 경우, 연속합의 최대값을 갱신하도록 했고 만약 중간 연속합이 0보다 작거나 최대값보다 작으면 더 이상 연속합을 계산하지 않도록 j반복문을 빠져나왔다.

 

4. 반복문의 계산을 줄이기 위해 이중 반복문에서 첫 음수가 나왔을 때의 인덱스를 flag에 저장하여 i가 음수가 나오고 그 다음 순서부터 돌아갈 수 있게끔 했다.

 

뭐 최대한 반복문의 계산을 줄이고자 했는데 그건 가장 밖에 있는 반복문이지 정작 시간을 많이 잡아먹는 이중반복문을 줄이지는 못 해서 시간초과가 나온 것 같다..

 

 

이제 정답 코드를 리뷰해보도록 하자.

위 문제는 DP(Dynamic Programming) 동적 계획법을 사용하여 구현하는 문제이다. 

DP에 대해 한 번도 정확하게 설명한 적이 없기 때문에, 이 문제를 리뷰하는 김에 같이 정리하고 넘어가도록 하겠다.

여기서 정리하고자 하는 dp는 다른 분의 포스팅을 참고하였는데, 굉장히 자세하게 설명되어 있으니 참고할 것

https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)

 

DP란, 동적 계획법이라고 불리며 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결하기 위해 저장한 값들을 사용하여 해결하는 것으로, 특정한 알고리즘이 아닌 하나의 문제해결 패러다임이다.

그렇다면, 왜 DP를 사용할까?

일반적인 재귀와 DP는 매우 유사하다.

다만, 재귀방식은 동일한 작은 문제들이 여러 번 반복 계산되기 때문에 비효율적인 계산 방식이라는 것이다.

따라서, 굉장히 많은 계산 횟수일 때는 더 효율적인 방식인 DP를 사용하여 문제를 해결하는 것이 더 효율적이다.

 

DP방식이 적용되기 위해서는 다음 2가지 조건을 만족해야 된다.

1. 겹치는 부분 문제

- DP는 기본적으로 큰 문제를 작은 문제로 나누고 그 작은 문제의 결과들을 재활용해서 큰 문제를 해결한다.

따라서, 작은 문제들이 반복적으로 나타나는 경우에만 사용이 가능하다.

2. 최적 부분 구조

- 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우에만 사용이 가능하다.

즉, 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과 값이 변하지 않을 때 DP 사용이 가능하다.

 

DP는 2가지 방법으로 구현될 수 있다.

1. Bottom-Up => 반복문 사용

- 아래에서 부터 계산을 수행하고 누적시켜서 전체 문제를 해결

2. Top-Down => 재귀 사용

- 위에서 부터 바로 호출을 시작하여 맨 아래까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용

 

다시 문제 리뷰로 돌아와서, 그럼 왜 이 문제에 대해 DP방식을 적용하여 풀이하는지부터 살펴보자.

이 문제는 말 그대로 연속합의 최대값을 구하는 문제이다. 먼저, 연속합의 최대값을 구하기 위해서는 여러 연속합들을 구한 후, 그 연속합에서 최대값을 골라야한다. 아래에서부터 연속합을 계산하여 저장하며 최종적으로 연속합의 최대값을 구하기 위해 계속 끌고 와야 한다. 큰 문제를 해결하기 위해 작은 연속합들의 최대값을 계속 끌고와 저장해야되므로 DP를 사용해야 하는 것이다.

 

풀이 코드에서는 연속합을 저장하기 위해서 크기 n의 배열을 선언 한 뒤, 반복문을 사용하여 그 리스트의 값을 새로 계산하는 값으로 넣어주었다.

n = int(input())
nums = list(map(int, input().split()))
dp = [0]*n
dp[0] = nums[0]
for i in range(len(nums)-1):
    dp[i+1] = max(dp[i]+nums[i+1], nums[i+1])

print(max(dp))

dp가 작은 문제들 즉, 연속합을 계속 저장할 리스트이다.

dp[0]을 맨 처음 수인 nums[0]으로 초기화하지 않으면, 아래 반복문이 돌아가면서 index error가 나오기 때문에 반드시 초기화 해주어야 한다.

for i in range(len(nums)-1):
    dp[i+1] = max(dp[i]+nums[i+1], nums[i+1])

처음에는 이 코드가 이해가 바로 안됐었는데, 생각해보면 작은 연속합들을 저장하는 이유는 결국 연속합의 최대값을 구하기 위함이고, 중간까지의 연속합이 입력받은 숫자보다 작다면 굳이 계속 끌고가며 저장할 필요가 없다.

따라서, 둘 중에서 큰 값만 저장하면 되는 것이다.

말로는 이해가 안될 수 있으니 그림까지 첨부해보고자 한다.

맨 처음 숫자들을 입력받아 array에 저장했다고 해보자.

dp에 연속합을 저장하기 위해 계속 합을 구하며 끌고 올건데, 해당 연속합이 입력받은 i번째 수보다 작을 경우, 해당 i번째 수부터  연속합을 다시 계산하면 더 큰 연속합을 구할 수 있기 때문에 그저 연속합의 최대값을 구하기 위해서는 해당 i 번쨰 수보다 작을 경우엔 끌고 와서 저장할 필요가 없다. 

==> 따라서, 우리가 필요한 것은 연속합과 i번째 수 둘 중에서 더 큰 값이다.

==> max를 사용하여 더 큰 값만을 저장하며 사용하면 된다.