Dynamic Programming

in Notes / Codingtest / Algorithms

and memoization

  • TODO: DP vs memoization 확실히 구분

Prefix Sum (누적합)

\[O(n*m)\Longrightarrow O(n)\]
일반 (A):63-24-105
Prefix Sum Array:6971110105
  • PSA[ i ] = PSA[ i - 1 ] + A[ i ]

  • Calculate [ 2 , 6 ] \(\Rightarrow\) [ 0 , 6 ] - [ 0 , 1 ]

  • Calculating Prefix Sum Array: \(O(n)\)

  • Perform Range Sum : \(O(1)\)

  • 2D Array:

    63-24-10-5
    69-24-10-5
    6974-10-5
    69711-10-5
    69711100-5
    697111010-5
    6971110105
    6971110105

  • 연습문제:

    • 연속된 부분 수열의 합 (프로그래머스, LV2) 6/27 PS
      답 
        def solution(sequence, k):
      n = len(sequence)
      answer = [0, n]
      if sequence[0] == k:
          return [0, 0]
      prefix = [0] # prefix = [0, x, x, x...] 
      startptr = 0
      for i in range(n):
          prefix.append(sequence[i]+prefix[i]) # 누적합 (a[i] = b[i] + a[i-1])
          # print("PREFIX ARRAY: ", prefix)
          if sequence[i] == k: # 본 sequence에서 같으면 바로 답임 (길이 = 1이기 때문)
              return [i, i]
          elif prefix[i+1] >= k: # prefix 앞에 0이 붙어 있어 index값에 1 더해줌
            # startptr에서 시작하거나 현재 지점에서-(현재 찾은 답안 중 제일 짧은 길이) 에서 시작
              for j in range(max(startptr, i-(answer[1]-answer[0])), i): 
                  if prefix[i+1]-prefix[j]==k:
                      answer = [j, i] if i-j < answer[1]-answer[0] else answer
                      break
                  elif prefix[i+1]-prefix[j] < k:
                      startptr = j
                      break

      return answer
    • BOJ 10986 나머지 합 6/29 PS
      답 
      ```py
def findCount(li, m):
    modarr = [-1]*m
    modarr[0] = 0
    count, prefix = 0, 0
    for i in range(len(li)):
        prefix += li[i]
        if modarr[prefix%m]==-1:
            modarr[prefix%m]=0
        else:
            modarr[prefix%m]+= 1
            count += modarr[prefix%m]
    return count

n, m = map(int, input().split())
li = list(map(int, input().split()))

print(findCount(li, m))
```