동적계획법

개념

• 문제를 더 작은 문제로 분할
• 상향식 문제 해결

• 메모이제이션(Memoization) : 가장 작은 입력 사례의 해답을 테이블에 저장하고 필요할 때 꺼내 쓴다.

분할정복법 vs 동적계획법

• 문제를 작은 사례로 분할하여 해결한다는 점에서 동일

• 분할정복: 재귀 호출을 통해 분할하여 정복 (Top-Down)

• 동적계획: 메모이제이션을 통해 상향식으로 정복 (Bottom-Up) ex) 피보나치 수열

• 이항계수에서의 비교
  (시간복잡도/ 성능개선 측면)
  분할정복법 : nCk 동적계획법 : nk

python 코드

동적계획법으로 이항계수 풀기

정의

def bin2 (n, k):
  B = [[0] * (k + 1) for _ in range(n + 1)]
  for i in range(n + 1):
    for j in range(min(i, k) + 1):
      if (j == 0 or j == i):
        B[i][j] = 1

      else:
        B[i][j] = B[i - 1][j - 1] + B[i - 1][j]
  return B[n][k]

예시코드

for n in range(10):
  for k in range(n + 1):
    print(bin2(n, k), end =
    " ")
  print()

예시코드 결과

동적계획법으로 이항계수 풀기2

• 문제 : 2차원 리스트(배열)를 사용할 필요가 있는가?
  답 : 1차원 리스트(배열)만으로도 구현이 가능하다.

정의

def bin3 (n, k):
  if (k > n // 2):
    k = n - k

  B = [0] * (k + 1)
  B[0] = 1
  
  for i in range(1, n + 1):
    j = min(i, k)
      while (j > 0):
        B[j] = B[j] + B[j - 1]
        j -= 1
  return B[k]

예시코드

for n in range(10):
  for k in range(n + 1):
    print(bin3(n, k), end=" ")
  print()

print(bin3(9, 5))

예시코드 결과

• 과도한 먹방쇼 남발로 오래걸렸습니다. 안죄송합니다.