티스토리 뷰

golang

Maximum Subarray Problem

주먹불끈 2019. 6. 19. 15:30

문제. 가장 연속한 부분합 구하기

 

정수들의 리스트가 입력으로 들어옵니다.

정수들의 리스트를 일부분만 잘라내어 모두 더했을 때의 값을 부분합이라 부릅니다.

이때 가장 부분합을 구해봅시다.

 

예를 들어, [-10, -7, 5, -7, 10, 5, -2, 17, -25, 1] 입력으로 들어왔다면 [10, 5, -2, 17] 모두 더한 30 정답이 됩니다.

 

※입력에는 최소 하나 이상의 양수가 존재합니다.

※이 문제에는 여러 종류의 풀이법이 존재합니다. 각 풀이법의 시간 복잡도를 고려하면서 여러가지 방법으로 문제를 풀어 봅시다.

 

def maxSubArray(nums):

    return 0

 

def main():

    print(maxSubArray([-10-75-7105-217-251])) # 30이 리턴되어야 합니다

 

if __name__ == "__main__":

    main()

 

 

결론부터

 

Kadane's Algorithm 사용하면 된다. (Joseph B. Kadane: http://www.stat.cmu.edu/~kadane/)

- 나는 처음에 멍청하게 Dynamic Programming 으로 풀었다.

 

링크

 

참고 링크

- 한글 블로그: https://blog.naver.com/7005ye/221070006057

- YouTube: https://youtu.be/86CQq3pKSUw (좀더 인싸이트를 얻게 되었다)

 

구현 링크

- GitHub: https://github.com/nicewook/max-sub-array

- Go Playground: https://play.golang.org/p/fNmvqPgo_xu

 

 

Solution. 양수 존재 여부와 상관없이 짜보자

 

- 유튜브 ( https://youtu.be/86CQq3pKSUw ) 보고 좀더 체계적인 개념이 잡혔다.

 

1) 순차적으로 index 하나씩 올려가며 계산을 하는데

2) 각각의 index 마지막 값인 경우들 중에서 최대값을 구해본 다음 ( 개념 이해가 중요하다)

3) 그러한 index 최대값들 중에서의 최대값을 찾아내는 것이다.

 

 

예시를 통해 이해해보자

 

입력 배열 tArray {-10, -7, 5, -7, 10, 5, -2, 17, -25, 1} 이라고 하자

 

index

sum 계산

0

index 0 마지막으로 하는 연속한 부분 배열은 {-10} 하나 뿐이므로

sum = -10

따라서, maxSum = -10 이다.

1

{-7} 경우 sum = -7

{-10, -7} 경우 sum = -17

따라서 maxSum = -7

2

{5} sum = 5

{-7, 5} sum = -2

{-10, -7, 5} sum = -12

maxSum = 5

3

{-7} sum = -7

{5, -7} sum = -2

{-7, 5, -7} sum = -9

{-10, -7, 5, -7} sum = -19

maxSum = -2

 

뒤는 생략하였지만 깨닿게 되는 부분이 있다.

1) 현재 index 마지막으로 하는 연속된 부분 배열 합을 계산할때에

2) 현재 바로 앞까지의 합이

- 음수라면 모두 무시하고 현재 index 값만을 sum 으로 계산하고

- 양수라면 이를 포함하여 sum 계산하면 된다는 것이다.

 

 

이제 코딩해보자

 

index 까지 추적하였더니, 오히려 코드 이해에 방해가 되는 것도 같다.

부분은 생략하고 분석해보겠다.

 

1) index 0 일때의 값을 sum maxSum 넣어준다.

- sum 현재 index 마지막 값으로 연속한 부분 집합의 중에서 가장 값이 되고

- maxSum 그야말로 지금까지 가장 값이다. sum of sum

 

2) index 0 일때는 이미 계산한 것이고, index 1 부터 끝까지 루프를 돌며 계산을 시작한다.

 

3) 이전까지의 sum 값을 현재 index 값과 더하는 것이 큰지 아닌지를 판단해서

- 값을 sum 으로 한다.

 

4) 그렇게 계산한 sum 값과 지금까지의 maxSum 값을 비교해서

- 값이 maxSum 으로 한다.

 

 

 

테스트 부분은 아래와 같다. (Dynamic Programming 무시하자)

 


 


반응형

'golang' 카테고리의 다른 글

gRPC Deadline  (0) 2019.06.26
Golang 개발시 Makefile 사용해보기  (0) 2019.06.24
Concurrent Logging - in Golang  (0) 2019.06.17
gRPC - Go Quick Start  (1) 2019.06.10
Protocol Buffers - Golang Tutorial  (0) 2019.06.07
반응형
잡학툰 뱃지
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함