심화 과정 15 일차

1. 자료구조 및 알고리즘 15일차 수강하기

 

 -  다이나믹 프로그래밍(DP)

 

2. 새롭게 알게된 지식

 

 - DP : 이전의 결과값이 다음 결정에 필요할 때, 이전의 결과값을 업데이트 하면서 프로그래밍 하는 알고리즘

 

과제 1 : 최대 서브 배열 : https://leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

 

 

 - 접근 : 

 

 1. 음수가 나오는 순간 결과값이 작아짐으로 음수를 기준으로 특징 분석

 2. 누적합을 들고 다니다가 누적합이 음수가 되는 순간 누적합 0으로 변경

 3. 매번 최댓값 갱신

 

 - 코드 구현 : 

 

 

 

 

과제 2 : 계단 오르기 : https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

 

 

 - 접근 : 

 

 

 - 코드 구현 : 

 

 

 

 

과제 3 : 집 도둑 : https://leetcode.com/problems/house-robber/

House Robber - LeetCode

 

 

 - 접근 : 

 

 

 

 - 코드 구현 :