연속부분최대의합을 통한 문제풀이 접근법

문제

N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다.

 

입력

첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두 번째 줄에 n개의 정수가 주어진다.

 

출력

연속된 부분을 선택하였을 때의 최댓값을 출력한다.

 

예제 입력

8

2 3 -5 8 -3 4 2 -9

예제 출력

11

예제 입력

5

-1 -2 3 -2 4

예제 출력

5

 

 

문제해결의 절차

1. 문제를 정확히 이해한다.
2. 문제를 해결하는 알고리즘을 개발한다.(설계)
3. 알고리즘이 문제를 해결한다는 것을 수학적으로 증명한다.
4. 알고리즘이 제한 시간내에 동작한다는 것을 보인다.(시간복잡도)
5. 알고리즘을 코드로 작성한다.
6. 제출 후 만점을 받는다.

 

#완전 탐색 : 단순설계를 통한 구현(탐색공간 : 문제해결을 위해 고려해야하는 모든 경우) -- 완전탐색(Brute Force Search)

#시간복잡도 : O(n^3)

import sys 
 
if __name__ == "__main__":
  n = int(sys.stdin.readline())
  data_list = list(map(int, sys.stdin.readline().split()))
  
  myMax = -99999
  for start in range(n):
    for end in range(start, n):
      mySum = 0
      for k in range(start, end+1):
        mySum += data_list[k]
      if mySum > myMax:
        myMax = mySum
        
  print(myMax)

입력

10
2 3 -7 5 8 -3 5 7 -10 8

 

출력

22

--> n의 범위가 1000 인 경우 위와같은 O(n^3) 방식으로는 안된다.

#시간복잡도 줄이기

아이디어 : start~end 합 시간복잡도를 O(1)로 줄인다.

#시간복잡도 : O(n^2)

import sys 
 
if __name__ == "__main__":
  n = int(sys.stdin.readline())
  data_list = list(map(int, sys.stdin.readline().split()))
  sum = [0 for _ in range(100)] # sum[x] = 첫 번째 숫자부터 x번째 숫자까지의 합
  
  sum[0] = data_list[0]
  for i in range(1, n):
    sum[i] = sum[i-1] + data_list[i]
    
    
  myMax = -99999
  for start in range(n):
    for end in range(start, n):
      mySum = 0
      
      # start ~ end 까지의 합
      # (1~end까지의 합) - (1~(start-1)까지의 합)
      # sum[end] - sum[start-1]
      if start == 0:
        mySum = sum[end]
      else:
        mySum = sum[end] - sum[start-1]
      
      if mySum > myMax:
        myMax = mySum
        
  print(myMax)
 

입력

10
2 3 -7 5 8 -3 5 7 -10 8

 

출력

22

 

--> n의 범위가 10000 인 경우 위와같은 O(n^2) 방식으로는 안된다.

 

**완전 탐색

장점
 - 확실하며, 알고리즘이 비교적 단순하다.
 - 비교적 풀이를 떠올리기가 쉽다.
단점
 - 느리다.

무조건 완전 탐색부터 시작
- 탐색 공간을 파악하는 것이 문제 해결에서 가장 중요함.
- 모든 경우를 고려해서 시간 내에 해결이 된다면 OK
- 시간내에 해결이 되지 않으면 경우의 수를 줄이는 시도를 함.

완전탐색이 안될 때(시간복잡도 초과), 문제해결을 위한 접근법
- Brute-Force(완전 탐색법)
- Divide & Conquer(분할 정복법)
- Dynamic Programming(동적계획법)
- Greedy Approach(탐욕적 기법)
- Graph Algorithm(그래프 알고리즘)

 

- Divide & Conquer(분할 정복법) 을 이용한 접근법

#설계

음...지저분한점은 죄송...

#시간복잡도

#구현

import sys
 
# 재귀함수를 작성하기 위한 과정
# 1. 함수를 말로 정의한다.
# 2. 기저조건일 때 제대로 동작하게 작성한다.
# 3. 함수가 제대로 동작한다고 가정하고 완성한다.
 
def getSubMax(start, end):
  # data의 start부터 end까지 구간 중 연속부분 최대합을 구해주는 함수.
  # 기저조건 : data의 숫자가 하나밖에 없을 때
  if start >= end:  
    return data[start]
  else:
    mid = (start + end)//2
    
    left = getSubMax(start, mid)
    right = getSubMax(mid+1, end)
  
    # 중간부분을 포함하는 연속부분 중 최대합을 구하자.
    # 1 8 -5 3 | 2 5 -10 2
    leftSum, leftMax = 0, -987987987
    for i in range(mid, start-1, -1):
      leftSum += data[i]
      if leftMax < leftSum:
        leftMax = leftSum
      
    rightSum, rightMax = 0, -987987987
    for i in range(mid+1, end+1):
      rightSum += data[i] 
      if rightMax < rightSum:
        rightMax = rightSum
    
    myMax = leftMax + rightMax
    
    if left >= right and left >= myMax: return left
    elif right >= left and right >= myMax: return right
    else: return myMax
    
    
if __name__ == "__main__":
  n = int(sys.stdin.readline())
  data = list(map(int, sys.stdin.readline().split()))
  print(getSubMax(0, n-1))

 

- 동적계획법을 이용한 접근법(Dynamic Programming)

#설계

#코드

import sys
 
# 1. Table 정의
# 2. 점화식
 
# Table(i) = i번째 숫자를 오른쪽 끝으로 하는 연속 부분 최대합
# Table(i) = max(Table(i-1) + Data(i) or Data(i))
 
if __name__ == "__main__":
  Table = [0 for _ in range(100)]
  n = int(sys.stdin.readline())
  data = list(map(int, sys.stdin.readline().split()))
  
  Table[0] = data[0]
  for i in range(1, n):
    if Table[i-1] + data[i] > data[i]:
      Table[i] = Table[i-1] + data[i]
    else:
      Table[i] = data[i]
  
  myMax = -987987987
  for i in range(n):
    if Table[i] > myMax:
      myMax = Table[i]
      
  print(myMax)

#시간복잡도 : O(n)