코테 스터디 30일차 TIL + 오늘의 학습 키워드 Dynamic Programming

- 오늘의 학습 키워드 동적 계획법
- 공부한 내용 본인의 언어로 정리하기

동적 계획법 dynamic programming  이전 계산 결과를 저장하고 활용하여 중복 계산을 피한다.

Kadane's 알고리즘

1. 선택지 

   1-1.각 위치에서 현재 원소부터 새로운 배열 시작하기 or

   1-2.이전 부분 배열에 현재 원수 추가하기

2. 각 단계에서 지금까지의 최대합을 기록

 

수도코드

function maxSubArray(nums):
    현재까지의 최대 합 = nums[0]
    전체 최대 합 = nums[0]
    
    for i = 1 to nums.length-1:
        현재까지의 최대 합 = max(nums[i], 현재까지의 최대 합 + nums[i])
        전체 최대 합 = max(전체 최대 합, 현재까지의 최대 합)
    
    return 전체 최대 합

 

 

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

다이나믹 프로그래밍 이전 계산 결과를 저장하고 활용하여 중복계산을 피한다는 기억함, 적용 x
  - 어떻게 해결했는지

각 위치에서 두가지 선택하는 것을 비교

  현재 원소만 선택하여 새로운 부분 배열 시작 nums[i]

  이전 부분 배열에 현재 원소 추가 currentSum + nums[i] 중에서 더 큰값을 currentSum으로 갱신

maxSum은 최대 부분 배열합을 추적
  - 무엇을 새롭게 알았는지

kandane's 알고리즘

음수의 합이 누적된 부분 배열은 버린다. 현재 합이 음수이면 새로운 원소부터 다시시작하게한다.
  - 내일 학습할 것은 무엇인지