Python Algorithm class (Dynamic Programming - 2)

nathan·2021년 4월 11일
DPalgorithmdynamicprogrammingpython
1

Python Algorithm class

목록 보기
12/27

Dynamic Programming (동적 계획법 - 2)

  1. 양의 정수 n의 합 표현 방법(순서고려)
  2. 양의 정수 n의 합 표현 방법(순서 X)
  3. 거스름 돈 나누어 주는 방법

4. 양의 정수 n의 합 표현 방법(순서고려)

(1) 계단 오르기 (한 번에 한 개 혹은 두 개만 오르기)

  • 계단을 오를 때, 한 번에 한 개 혹은 두 개만 계단을 오를 수 있다. n개의 계단 아래에서 계단 꼭대기까지 올라가는 방법의 수를 구하시오

  • ex. 4개의 계단을 올라갈 수 있는 방법 = 4를 1과 2의 합으로 나타내는 방법과 동일

    • 1 + 1 + 1 + 1
    • 1 + 1 + 2
    • 1 + 2 + 1
    • 2 + 1 + 1
    • 2 + 2

  • C(i) : i개의 계단 아래에서 꼭대기까지 올라가는 방법의 수

    • C(0) = 1 (if i = 0)
      • i = 0일 때 0으로 두면 곤란하다.
      • ex. C(2) = C(1) + C(0) = 2가 되어야 하므로.
    • C(1) = 1 (if i = 1)
    • C(i) = C(i-1) + C(i-2) (if i > 1)
i0123456...
C[i]11235813...
def count(n):
   C = [0 for i in range(n+1)]
   C[0] = C[1] = 1
   for i in range(2, n+1):
      C[i] = C[i-1] + C[i-2]
   return C[n]

주요 연산 : C[i] = C[i-1] + C[i-2]
수행시간 : O(N)

++ 참고 : 2xN 타일링에서도 똑같이 동적 계획법으로 풀 수 있다.
백준알고리즘 1793번 문제 바로가기

(2) 양의 정수 n을 ~,~,~의 합으로 나타내는 방법의 수

  • 양의 정수 n을 1, 3, 4의 합으로 나타내는 방법의 수를 구하시오(1, 3, 4를 사용하는 횟수에 대한 제한은 없고, 합에 나타나는 숫자들의 순서를 고려한다.)
  • ex. n = 5인 경우 5가지 방법이 존재
    • 1 + 1 + 1 + 1 + 1
    • 1 + 1 + 3
    • 1 + 3 + 1
    • 3 + 1 + 1
    • 1 + 4
    • 4 + 1
  • C(i) : i를 1, 3, 4의 합으로 나타내는 방법의 수
    • C(0) = 1 (if i = 0)
      • i = 0일 때 0으로 두면 곤란하다.
      • ex. C(2) = C(1) + C(0) = 2가 되어야 하므로.
    • C(1), C(2) = 1 (if i = 1, 2)
    • C(3) = 2 (if i = 3)
    • C(i) = C(i-1) + C(i-3) + C(i-4) (if i > 3)
i0123456...
C[i]1112469...
def count(n):
   C = [0 for i in range(n+1)]
   C[0] = C[1] = C[2] = 1
   C[3] = 2
   for i in range(4, n+1):
      C[i] = C[i-1] + C[i-3] + C[i-4]
   return C[n]

주요 연산 : C[i] = C[i-1] + C[i-3] + C[i-4]
수행시간 : O(N)

(3) 양의 정수 n을 n1<n2<...\<nk의 합으로 나타내는 방법의 수

  • 양의 정수 n을 n1<n2< ...< nk의 합으로 나타내는 방법의 수를 구하시오. (각 수를 사용하는 횟수에 대한 제한은 없고, 합에 나타나는 숫자들의 순서를 고려한다.)
  • ex. n1 = 1, n2 = 3, n3 = 4
    • 1 + 1 + 1 + 1 + 1
    • 1 + 1 + 3
    • 1 + 3 + 1
    • 3 + 1 + 1
    • 1 + 4
    • 4 + 1
  • C(i) : i를 n1<n2< ...< nk의 합으로 나타내는 방법의 수
    • C(0) = 1 (if i = 0)
      • i = 0일 때 0으로 두면 곤란하다.
      • ex. C(2) = C(1) + C(0) = 2가 되어야 하므로.
    • 0 (if i < n1) -> 해당하는 경우가 없음!
    • C(i) = C(i - n1) + C(i - n2) + ... + C(i - nk) (if nj ≤ i < n(j+1) for 1 ≤ j < k-1) (그냥 i보다 nk가 큰 경우라고 생각하기)
    • C(i) = C(i - n1) + C(i - n2) + ... + C(i - nk) (if i ≥ nk)
i0123456...
C[i]1112469...
# numList[i] = ni+1
def count(n, numList):
   C = [0 for i in range(n+1)]
   C[0] = 1
   for i in range(numList[0], n+1):
      for x in numList:
         if i >= x:
            C[i] += C[i-x]
         else:
            break
    return C[n]

수행시간 : O(N*K) (K가 상수가 아닐 수 있다.)

(4) 양의 정수 n을 1부터 n까지의 숫자들의 합으로 나타내는 방법의 수

  • 양의 정수 n에 대하여, n을 1부터 n까지 숫자들의 합으로 나타내는 방법의 수를 구하시오. (순서 구분)

  • ex. n=4인 경우 다음의 8가지가 있다. (마지막에 오는 숫자를 기준으로 구분)

    • (1 + 1 + 1 + 1), (2 + 1 + 1), (1 + 2 + 1), (3 + 1)
    • (1 + 1 + 2), (2 + 2)
    • (1 + 3)
    • (4)

  • C(i) : i를 1부터 i까지의 숫자들의 합으로 나타내는 방법의 수

    • C(i) = 1 (if i = 0)
      ...
    • C(i) = C(i-1) + C(i-2) + ... + C(0) (if i > 0)
i0123456...
C[i]112481632...
def count(n):
   C = [0 for i in range(n+1)]
   C[0] = 1
   for i in range(1, n+1):
      for j in range(i):
         C[i] += C[j]
   return C[n]

수행시간 : O(N^2) : (1+2+3+ ... + n) = n*(n+1)/2
재귀 식을 잘 분석하면 C(n) = 2^(n-1) 이다.
(그냥 계산하면 C(7) = 64 니까)

(5) 양의 정수 n을 1부터 k까지 숫자들의 합으로 나타내는 방법의 수

  • 양의 정수 n에 대하여 n을 1부터 k까지 숫자들의 합으로 나타내는 방법의 수를 구하시오. (나열하는 숫자들의 순서를 고려)

  • ex. n = 4, k = 2인 경우 다음의 5가지가 있다.

    • (1+1+1+1), (2+1+1), (1+2+1), (1+1+2), (2+2)

  • C(i) : i를 1부터 k까지의 숫자들의 합으로 나타내는 방법의 수

    • C(i) = 1 (if i = 0)
    • C(i) = C(i-1) + C(i-2) + ... + C(0) (if i < k)
    • C(i) = C(i-1) + C(i-2) + ... + C(i-k) (if i ≥ k)
i = 4, k = 2 (i ≥ k)
C(4) = C(3) + C(2)

---
i = 4, k = 5 (i < k)
C(4) = C(3) + C(2) + C(1) + C(0)
i0123456...
C[i]112471324...
def count(n, k):
    C = [0 for i in range(n+1)]
    C[0] = 1
    for i in range(1, n+1):  
       for j in range(min(n+1, k+1)): # k가 n보다 클 경우를 대비
          if i >= j:
             C[i] += C[i-j]
          else:
             break
    return C[n]

수행시간 : O(N * k)

(6) 계단 오르기 (각 계단에 비용이 존재, 총 비용의 최솟값 구하기)

  • 계단을 오를 때, 한 번에 한 개, 세 개 혹은 네 개의 계단씩 오를 수 있으며, 각 계단을 밟을 때 비용이 있다. n개 계단 아래에서 계단 꼭대기까지 올라갈 때 밟는 계단의 총 비용의 최솟값을 구하시오.
  • ex. n = 6일 때, 비용 {2, 5, 13, 10, 6, 3} : 최소 비용 : 10
  • C(i) : i개의 계단 아래에서 꼭대기까지 올라갈 때 밟는 계단의 총 비용의 최솟값
    • C(i) = 0 (if i = 0)
    • C(i) = C(i-1) + cost[i] (if 1≤ i ≤2)
    • C(i) = cost[i] (if i = 3 or 4)
    • C(i) = min{C(i-1), C(i-3), C(i-4)} + cost[i] (if i > 4)
i01234567
C[i]027(=2+5)13108(=2+6)10(=7+3)...
P[i]00100126

P[i] : 이전에 어떤 계단을 밟고 왔는지를 기록. 

C = [0 for i in range(n+1)]
# costs = [2, 5, 13, 10, 6, 3, 2]
# k_list = [1, 3, 4]
C[0] = 0
C[1] = C[0] + costs[0]  # costs는 인덱스 0부터 시작!
C[2] = C[1] + costs[1]
C[3] = costs[2]
C[4] = costs[3]

for i in range(k_list[-1], n+1):
	C[i] = min(C[i-1], C[i-3], C[i-4]) + costs[i-1]

return C[n]

시간 복잡도 : O(N)

5. 양의 정수 n의 합 표현 방법(순서 X)

  • 양의 정수 n에 대하여, n을 1부터 n까지 숫자들의 합으로 나타내는 방법의 수를 구하시오. 단 나열되는 숫자들의 순서는 고려하지 않는다.
    (1+2와 2+1은 동일한 것으로 간주한다)

  • ex. n=4인 경우 다음의 5가지 경우가 존재한다.

    • 1+1+1+1
    • 1+1+2
    • 2+2
    • 1+3
    • 4

  • 숫자들의 합에서 숫자들의 순서는 고려하지 않으므로, 숫자들의 합 표현은 증가하는 숫자들의 합으로 표현

  • C(i, j) : i를 1부터 j까지 숫자들의 합으로 나타내는 방법의 수
    (나열되는 숫자와 순서는 고려하지 않음)

  • C(i, j) = 1 (if i = 0)

  • C(i, j) = C(i, i) (if i < j)

  • C(i, j) = C(i-j, j) + C(i, j-1) (if i ≥ j) // 숫자들 합의 표현에서 마지막 숫자가 j
    (j를 사용하는 경우와 j를 사용하지 않는 경우로 분리해서 봄)

=> C(n, n)을 구하면 된다.

def count(n, k):
   C = [[0 for j in range(n+1)]for i in range(n+1)]
   for i in range(n+1):
      for j in range(n+1):
         if j == 1:	# i를 1로 표현하는 방법의 수는 무조건 1
            C[i][j] = 1
         elif i == 1:	# 1을 1부터 j까지의 수로 표현하는 방법의 수는 무조건 1
            C[i][j] = 1
         elif i < j: 	# 이 때 j는 i까지만 표현이 가능함
            C[i][j] = C[i][i]
         else:	# i ≥ j, j를 포함하는 경우 + j를 포함하지 않는 경우
            C[i][j] = C[i-j][j] + C[i, j-1]
            
    return C[n][n]

6. 거스름 돈 나누어 주는 방법

  • 동전들의 단위 c1, c2, ..., cn이 있다. 이들 동전들을 이용하여 거스름돈 M을 나누어주는 방법의 수를 구하시오.

  • ex. n = 3이고, (c1, c2, c3) = (1, 3, 5), M = 10인 경우 다음의 7가지 방법이 있다.

    • 1+1+1+1+1+1+1+1+1+1
    • 1+1+1+1+1+1+1+3
    • 1+1+1+1+3+3
    • 1+3+3+3
    • 1+1+1+1+1+5
    • 1+1+3+5
    • 5+5

  • c1 < c2 < c3 < ... < cn이라 가정한다.

    • C(i, j) : 거스름 돈 i를 c1 부터 cj까지의 동전들을 이용하여 나누어주는 방법의 수
    • C(i, j) = 0 (if j = 0)
    • C(i, j) = 1 (if j > 0 and i = 0) : 0으로 두면 곤란, 다른 수 구 할 때 이용되기 때문
      (그냥 0원을 거슬러 주는 방법은 0개가 아닌 1개라고 생각하기!)
    • C(i, j) = 0 (if j = 1 and i < c1) : 동전의 최솟값보다 i가 더 작은 경우
    • C(i, j) = C(i, j-1) (if i < cj) : 마지막 동전의 값이 구하려는 값보다 클 때, 마지막 동전을 제외하고 계산
    • C(i, j) = C(i-j, j) + C(i, j-1) otherwise
      => C(M, n)을 구하면 된다.

수행시간 : O(M*N)

- C(10, 3) = C(10-5, 3) + C(10, 2) (C3 = 5) 
numList = [0, 1, 3, 5]

def count(n, m, numList):   # n : 거스름돈 개수, m : 거슬러 줘야하는 총 금액
    C = [[0 for j in range(n+1)] for i in range(m+1)]
    for i in range(m+1):
        for j in range(n+1):    # i = 5, j = 0, 1, 2, 3
            # C[i][j] : 거스름 돈 i를 c1 ~ cj까지 동전들을 이용해서 나눠주는 방법의 수
            if j == 0:
                C[i][j] = 0
            elif j > 0 and i == 0:
                # 0으로 두면 곤란, 다른 수 이용할 때 쓰이기 때문
                # 그냥 0원을 거슬러 주는 방법이 0개가 아닌 1개라고 생각하기
                C[i][j] = 1
            elif j == 1 and i < numList[1]:
                # 동전의 최솟값보다 i가 더 작은 경우 
                C[i][j] = 0
            elif i < numList[j]:   
                # 마지막 동전의 값이 구하려는 값보다 클 때는
                # 마지막 동전 제외시키기 
                C[i][j] = C[i][j-1]
            else:
                x = numList[j] # 마지막 동전을 제외시킬 변수 x 선언
                C[i][j] = C[i-x][j] + C[i][j-1]
    
    print(C)
    return C[m][n]

print(count(3, 10, numList))

++ 별첨

경로 찾기 문제 (중복순열과 유사)

  • 각 격자를 C(i, j)를 통하여 나타내고, 규칙은 오른쪽 또는 위쪽으로만 이동이 가능하다.
  • 하나의 경로를 U(위쪽)와 R(오른쪽)으로만 나타낼 수 이싿.
  • ex. 만약 출발지가 C(1, 1)이고, 도착지가 C(6,6)이라면, R을 5번, U를 5번 중복하여 나열하는 경우의 수와 같다.
    • 10! / 5! * 5! = 256
def findPath(n, k):
    C = [[0 for i in range(n+1)] for j in range(n+1)]
    for i in range(n+1):
        for j in range(n+1):
            if i == 0 or j == 0:
                C[i][j] = 1
            else:
                C[i][j] = C[i][j-1] + C[i-1][j]
    
    print(C)
    return C[n][k]

print(findPath(5, 5))

[1, 1, 1, 1, 1, 1],
[1, 2, 3, 4, 5, 6], 
[1, 3, 6, 10, 15, 21], 
[1, 4, 10, 20, 35, 56], 
[1, 5, 15, 35, 70, 126], 
[1, 6, 21, 56, 126, 252]]
profile
nathan
나는 날마다 모든 면에서 점점 더 나아지고 있다.
이전 포스트

Python Algorithm class (Dynamic Programming)

다음 포스트

Python Algorithm class (Dynamic Programming - 3)

0개의 댓글