해커랭크 — DP (Max Array Sum, Abbreviation, Candies)

DP(다이나믹 프로그래밍: Dynamic Programming)

해커랭크 문제는 Edge Case에 대한 이해가 중요한 것 같다.

Max Array Sum

문제

Max Array Sum | HackerRank

풀이

DP Base Case 분석을 통한 점화식 구성

def maxSubsetSum(arr):
    if len(arr) == 1: # 예외처리
        return arr[0]
    dp = [arr[0], max(arr[:2])] + [0]*(len(arr)-2) # BaseCase + Memoization 대상들
    for i in range(2, len(arr)):
        dp[i] = max(arr[i], dp[i-1], dp[i-2]+arr[i])
    return dp[-1]

Abbreviation

문제

Abbreviation | HackerRank

풀이

• DP[i][j] : A[:i+1], B[:j+1] 를 일치하게 할 수 있는지 여부
• A[i]가 소문자인 경우, DP[i-1][j]가 참이면 참이다.
• DP[i-1][j-1]이 참인 경우, A[i]와 B[j]가 같거나, A[i]를 대문자로 바꾸어 B[j]과 같으면 DP[i][j]도 참이다.

출처: http://mrkimkim.com/study/coding_interview/coding-interview-abbreviation/

Candies

문제

Candies | HackerRank

풀이

def candies(n, arr):
    dp = [1]*n # 1로 초기화(최소값)
    for i in range(1, n):
        if arr[i] > arr[i-1]:
             dp[i] = dp[i-1] + 1
     for j in range(n-1, 0, -1): # 뒤에서부터 한번 더 검증
         if arr[j] < arr[j-1] and dp[j] >= dp[j-1]:
             dp[j-1] = dp[j] + 1
     
     return sum(dp)