개발자 노트

문제설명 연속 합 중에서 최댓값을 구하라. 접근 방법 유튜브에 본 권오흠 교수님의 설명대로, DP문제를 풀 때 optimal substructure를 나타내는 순환식을 작성해야 한다. 사고 과정은 아래 이미지에 나타나 있는대로 접근하였다. DP문제를 풀다보니 다음을 반드시 고려해야만하고, 이를 고려하면 문제의 구조를 잘 이해하게 된다. 단계를 어떤 변수로 설정하였는가? (이 문제에선 i,i+1,i+2..번째 수를 단계로 보았다.) i번째 단계에서 최적 값에 영향을 주는 변수는 무엇인가? i번째 단계의 최적 값은 이전에 구한 최적값으로 어떻게 표현할 수 있는가? 즉, optimal substructure을 구하라. 1번째 2번째 단계의 최적 값을 푸는 건 간단하다.(이게 어렵다면 정말 어려운 문제다.) 앞..