[BOJ 1912] 파이썬 - Kadane 알고리즘 ?

핀·2024년 3월 29일

kadane's algorithm 카데인알고리즘

파이썬 알고리즘풀이

목록 보기

3/3

Kadane's Algorithm?

이제 다이나믹 프로그래밍을 처음 접해서 여러가지 시도를 하고 있는데, 역시 DP문제들은 쉬운게 없는거 같다..

백준 1912번 연속합 문제 최대 부분 배열 합 문제를 파이썬으로 풀어보면서 Kadane의 알고리즘에 대해 알아보도록 하겠습니다.

문제는 나름 간단해보이는 것 같았는데, 어떻게 DP로 풀 지?하면서 결국 for문을 명륜진사로 쓰다가 답지를 보게됐다.

그 과정에서 Kadane알고리즘 사용하는 문제라는 이야기가 많아서 이거랑 엮어서 블로그를 쓰면 괜찮겠다!(굿 아이디어!) 싶어서 작성하게 되었습니다.

~카다네? 알고리즘으로 읽었는데 찾아보니 카데인 이라고 부르는 것 같다..

굿 아이디어

📚 문제 설명

n개의 정수로 이루어진 임의의 수열이 주어졌을 때, 연속된 몇 개의 수를 선택하여 구할 수 있는 합 중 가장 큰 합을 구하는 문제입니다. 단, 수는 한 개 이상 선택해야 합니다

문제에서 주어진 수열

10 -4 3 1 5 6 -35 12 21 -1

이 수열에서 최대 부분 배열 합은 12 + 21 = 33 이 된다.

🔍 Kadane의 알고리즘

Kadane의 알고리즘은 동적 프로그래밍을 통해서 선형 시간 복잡도로 문제를 해결할 수 있다고 한다!

Kadane's Algorithm 아이디어

현재 위치까지의 부분 배열 합을 계산
현재 위치까지의 부분 배열 합이 음수라면, 새로운 부분 배열을 시작
현재 위치까지의 부분 배열 합과 전체 배열에서 발견된 최대 부분 배열 합을 비교하여 더 큰 값을 저장합니다.

💻 1912번 코드

def max_subarray_sum(arr):
    max_so_far = float('-inf')
    max_ending_here = 0
    
    for num in arr:
        max_ending_here = max(num, max_ending_here + num)
        max_so_far = max(max_so_far, max_ending_here)
    
    return max_so_far

# 입력 받기
n = int(input())
arr = list(map(int, input().split()))

# 최대 부분 배열 합 계산
max_sum = max_subarray_sum(arr)

# 결과 출력
print(max_sum)

위의 코드를 실행하면 주어진 수열에 대한 최대 부분 배열 합을 출력합니다.

파이썬에서 float('-inf')는 음의 무한대를 나타내는 값으로, 초기 최대 부분 배열 합을 음의 무한대로 설정하여 어떤 값과도 비교했을 때 작은 값이 되도록 합니다.

시각화하면?

주어진 수열

10 -4 3 1 5 6 -35 12 21 -1

알고리즘은 수열의 각 요소를 순회하면서 다음 단계를 수행합니다:

10: 현재 부분 배열 합 10, 최대 부분 배열 합 10

현재 부분 배열 합: 10
최대 부분 배열 합: 10

-4: 현재 부분 배열 합은 6(10 - 4) 최대 부분 배열 합은 그대로 10
```
현재 부분 배열 합: 6
최대 부분 배열 합: 10
```
3: 현재 부분 배열 합은 9(6 + 3) 최대 부분 배열 합은 그대로 10
```
현재 부분 배열 합: 9
최대 부분 배열 합: 10
```
1: 현재 부분 배열 합은 10(9 + 1) 최대 부분 배열 합도 10
```
현재 부분 배열 합: 10
최대 부분 배열 합: 10
```
5: 현재 부분 배열 합은 15(10 + 5) 최대 부분 배열 합은 15로 갱신
```
현재 부분 배열 합: 15
최대 부분 배열 합: 15
```
6: 현재 부분 배열 합은 21(15 + 6) 최대 부분 배열 합은 21로 갱신
```
현재 부분 배열 합: 21
최대 부분 배열 합: 21
```
-35: 현재 부분 배열 합은 -14(21 - 35)로 음수가 되었으니 새롭게 부분 배열 시작
```
현재 부분 배열 합: -35
최대 부분 배열 합: 21
```
12: 현재 부분 배열 합은 12(-35 < 12), 최대 부분 배열 합은 그대로 21
```
현재 부분 배열 합: 12
최대 부분 배열 합: 21
```
21: 현재 부분 배열 합은 33(12 + 21), 최대 부분 배열 합 33으로 갱신
```
현재 부분 배열 합: 33
최대 부분 배열 합: 33
```
-1: 현재 부분 배열 합은 32(33 - 1) 최대 부분 배열 합 33
```
현재 부분 배열 합: 32
최대 부분 배열 합: 33  
```