문제 요약
길이 N인 수열이 주어진다.
연속된 몇 개의 수를 선택해서 만들 수 있는 합 중 최대값을 구하는 문제.
수는 양수, 음수 모두 나올 수 있다.
“수열에서 연속된 구간 하나를 골랐을 때, 그 합이 최대가 되는 값을 구하라”
풀이 과정
1️⃣ 첫 시도 (오답 접근)
처음 내가 세운 전략은 이랬다.
“음수는 구간 합을 감소시키는 요소니까
양수들만 더해서 그중 최대합을 고르면 되지 않을까?”
하지만 이는 틀린 전략이다. 반례를 살펴보자.
1 2 -1 10내 로직대로 하면 1 + 2 = 3 → -1에서 끊고 3 저장.
하지만, 실제 최대 연속합은 음수를 포함한다. 1 + 2 - 1 + 10 = 12
음수가 포함되어 있더라도, 뒤에 나오는 큰 양수들이 그 음수를 덮고도 남으면
음수를 포함한 긴 구간 전체가 최대합이 될 수 있다.
이 지점을 간과해서 틀렸다.
2️⃣ 정답 풀이 — DP(kadane 알고리즘)으로 해결하기
dp[i] = i번째 원소로 끝나는 연속 부분 수열의 최대 합
즉, “i에서 끝난다고 가정했을 때, 최선의 합” 만을 관리하는 것.
이때 i에서 할 수 있는 선택은 딱 두 가지다.
-
이전까지의 연속합에 현재 값을 이어붙인다
→ dp[i-1] + seq[i] -
현재 값 하나로 새 구간을 시작한다
→ seq[i]
그럼 점화식은 자연스럽게 이렇게 나온다.
dp[i] = max(dp[i-1] + seq[i], seq[i])
최종 정답은?
→ 전체 i 중에서 dp[i]의 최댓값이 바로 우리가 원하는 “연속합 최댓값”
✅ 최종 코드
내가 작성한 정답 코드는 아래와 같다.
n = int(input())
seq = list(map(int, input().split()))
dp = [0] * n
dp[0] = seq[0]
for i in range(1, n):
dp[i] = max(dp[i-1] + seq[i], seq[i])
print(max(dp))코드 한 줄씩 해석해보기
dp[0] = seq[0]첫 번째 원소로 끝나는 최대 연속합은 당연히 그 원소 하나뿐.
for i in range(1, n):dp[i-1] + seq[i]→ 이전까지 이어오던 구간에 지금 값을 붙였을 때의 합
seq[i]→ “아, 그냥 여기서부터 새로 시작하자”라고 마음먹었을 때의 합
- 둘 중 더 큰 걸
dp[i]에 저장.
- 마지막에
max(dp)→ “각 위치에서 끝나는 최대합들” 중 가장 큰 값을 정답으로 출력.
💬 GPT의 이런 알고리즘을 떠올리는 팁 정리
이번 문제 풀면서 “어떻게 이런 점화식을 생각해낼까?” 스스로도 궁금했는데,
정리해보니까 이런 사고 흐름을 타면 훨씬 수월해진다.
1. “이전 결과가 항상 좋은 건 아니다”를 인정하기
연속합 문제라 해서
“앞에서 이어붙이는 게 무조건 이득이겠지?”
라고 생각하면 함정에 빠진다.
예시:
-999 100
999 + 100 = -899100혼자 = 100
이런 예시를 떠올리면
“아, 이전까지의 합이 오히려 발목을 잡을 수도 있구나”
라는 생각이 자연스럽게 든다.
그 순간,
“그럼 어떤 지점에서는 과감히 새로 시작해야겠다”
는 아이디어가 나온다.
2. “현재 위치에서 선택지는 딱 두 개뿐”이라고 생각하기
DP 점화식 만들 때 제일 큰 힌트:
“i번째 칸에서 내가 할 수 있는 선택이 뭔지 다 써보자”
이 문제에서 i번째 위치에서 할 수 있는 선택:
-
이전까지의 구간에 이어붙이기
→
dp[i-1] + seq[i] -
새로 시작하기
→
seq[i]
딱 둘뿐이다.
선택지를 정리하면 점화식도 훨씬 쉽게 보인다.
3. “전체 답”이 아니라 “한 칸 한 칸 최선의 선택”에 집중하기
우리는 자꾸 이런 생각을 한다.
“최대 연속합 구간이 어디부터 어디까지일까…”
근데 DP의 관점에서는
“i에서 끝나는 최대 연속합만 잘 관리하면,
나중에 전체 최댓값은
max(dp)로 한 번에 구할 수 있다.”
즉,
완성된 구간을 한 번에 찾는 게 아니라, 각 위치에서 최선의 결과를 쌓아가는 느낌을 익히는 게 중요하다.
4. “언제 구간을 끊고 새로 시작할지” 기준 세우기
이 문제에서도 구간을 끊는 기준은 명확하다.
“이전까지의 합에 현재 값을 더한 것” vs “현재 값 하나만”
둘을 비교해봤을 때
현재 값 하나로 시작하는 게 더 크면 과감히 이전 구간을 버린다.
이 패턴은 다른 DP/그리디류 문제에서도 꽤 자주 등장하는 사고방식이다.
🧠 배운 점 정리
- 음수라고 해서 무조건 버리면 안 된다. → 뒤에 나오는 큰 양수가 그 음수를 덮을 수 있다.
dp[i]를 어떻게 정의할지가 문제의 절반 → 이 문제에서는i에서 끝나는 최대 연속합으로 정의하면서 길이감이 확 줄어든다.
- 현재 위치에서 할 수 있는 선택을 “두 가지” 정도로 좁혀서 생각해보기 → 이어붙일지 / 새로 시작할지
- 최종 답은
dp배열 전체를 보고max(dp)로 고를 수 있다는 감각 익히기.
이제 1912번은 그냥 “연속합 = 카데인 알고리즘”으로 기억해두고,
비슷한 DP 문제(최대 부분 수열, 누적합 + DP 등)에서 이 패턴을 계속 써먹으면 감각이 훨씬 빨리 늘어날 것 같다.
💡 카데인 알고리즘이란?
“연속된 부분 배열(subarray)의 최대 합”을 가장 빠르게 구하는 알고리즘이다.
현재 위치에서 끝나는 최대 연속합을 매 순간 업데이트하면서,
그 중 가장 큰 값을 고르는 알고리즘.
카데인의 강점은 한 번의 반복(O(N))만으로 정답을 구할 수 있다는 점이다.
카데인 알고리즘의 핵심 포인트 요약
1) 전체를 한 번에 보지 않고, “i에서 끝나는 최댓값”만 본다
복잡한 문제를 작은 부분 문제로 쪼개는 DP 사고의 정석.
2) 과거의 합이 미래에도 유리하리란 보장이 없다
과거에 아무리 많이 쌓아왔더라도
지금 값 하나가 더 크면 그냥 리셋하는 게 낫다.
3) 음수를 만나도 끊지 않는다
음수를 건너뛰는 게 아니라, 음수를 포함한 전체가 뒤에서 이득이 될 수 있기 때문.
