LeetCode 3주차 문제 풀이 정리 – Kadane’s Algorithm, Greedy, DP

이번 주 풀이 요약 Easy 1문제 Climbing Stairs Medium 5문제 Maximum Subarray Spiral Matrix Jump Game Merge Intervals Unique PAths Hard 0문제 이번 주 문제 & 학습 포인트 1. Maximum Subarray 문제 요약 정수 배열 nums가 주어질 때, 연속된 부분 배열(subarray) 중 합이 최대가 되는 값을 구하는 문제 (반드시 하나 이상의 원소를 포함해야 한다) 핵심 아이디어 “이 숫자를 포함한 상태로 계속 가는 게 이득인가, 아니면 여기서 새로 시작하는 게 이득인가?”

이 문제의 본질은 “합이 음수인가”가 아니라, 이전 상태를 이어갈 가치가 있는가, 아니면 여기서 새로 시작하는 게 나은가를 판단하는 것이다. 배운 핵심/교훈 실수 정리 첫 번째: 모든 수가 음수인 경우를 고려하지 못함 0을 “안 고른 상태”로 허용해버림 문제는 반드시 하나 이상의 원소를 포함한 subarray를 요구...