백준 9251 : 문제링크

• 문제유형 :

  • 동적 프로그래밍

• 설명

  • 곡의 개수가 N, 볼륨의 최댓값은 M이므로 동적프로그래밍을 이용하여 시간 복잡도 O(NM)

  • 핵심 아이디어: 모든 볼륨에 대하여 연주 가능 여부 계산

  • D[i][j+1] => i번째 노래일 때 j 크기의 볼륨으로 연주 가능한지 여부

  • 노래를 순서대로 확인, 매 번 모든 크기의 볼륨을 검사

  • D[i][j - V[i]] = True if D[i-1][j] = True

  • D[i][j + V[i]] = True if D[i-1][j] = True

    

• 풀이

      n, s, m = map(int, input().split())
      array = list(map(int, input().split()))
  
      dp = [[0] * (m + 1) for _ in range(n + 1)]
      dp[0][s] = 1
  
      for i in range(1, n + 1):
          for j in range(m + 1):
              if dp[i - 1][j] == 0:
                  continue
              if j - array[i - 1] >= 0:
                  dp[i][j - array[i - 1]] = 1
              if j + array[i - 1] <= m:
                  dp[i][j + array[i - 1]] = 1
  
      result = -1
      for i in range(m, -1, -1):
          if dp[n][i] == 1:
              result = i
              break
  
      print(result)

Comment and share

백준 2655 : 문제링크

• 문제유형 :

  • 동적 프로그래밍

• 설명

  • 벽돌의 수가 N개일 때, 시간복잡도 O(N^2)

  • 벽돌의 번호를 출력해야함 -> 계산된 테이블 역추적 가능해야함

  • 먼저 벽돌을 무게 기준으로 정렬

  • D[i] = 인덱스 i인 벽돌을 가장 아래에 두었을 때의 높이

  • 모든 0 <= j < i에 대해, D[i] = max(D[i], D[j] + height[i]) if area[i] > area[j]

    

  • 이후에 Max Value에서 테이블 역추적

• 풀이

      n = int(input())
      array = []
  
      array.append((0, 0, 0, 0))
      for i in range(1, n + 1):
          area, height, weight = map(int, input().split())
          array.append((i, area, height, weight))
  
      array.sort(key=lambda data: data[3])
  
      dp = [0] * (n + 1)
  
      for i in range(1, n + 1):
          for j in range(0, i):
              if array[i][1] > array[j][1]:
                  dp[i] = max(dp[i], dp[j] + array[i][2])
  
      max_value = max(dp)
      index = n
      result = []
  
      while index != 0:
          if max_value == dp[index]:
              result.append(array[index][0])
              max_value -= array[index][2]
          index -= 1
  
      result.reverse()
      print(len(result))
      [print(i) for i in result]

Comment and share

백준 9251 : 문제링크

• 문제유형 :

  • 동적 프로그래밍

• 설명

  • 두 수열의 길이가 N 미만일 때, 시간 복잡도 O(N^2)으로 문제를 해결할 수 있습니다.
  • 수열 각각을 X, Y라고 함
  • D[i][j] = X[0..i]와 Y[0..j]의 공통 부분 수열의 최대 길이
  • 두 문자열의 길이를 조금씩 늘려가며 확인, 공통 부분 수열의 최대 길이를 계산
  • 점화식
    

• 풀이

  1 2 3 4 5 6 7 8 9 10 11

  x = input() y = input() dp = [[0] * (len(y) + 1) for _ in range(len(x) + 1)] for i in range(1, len(x) + 1): for j in range(1, len(y) + 1): if x[i - 1] == y[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

Comment and share

백준 11053 : 문제링크

• 문제유형 :

  • 탐색

  • 동적 프로그래밍

• 설명

  • 수열의 크기가 N일 때, 기본적으로 동적 프로그래밍 알고리즘으로 O(N^2)으로 해결

  • D[i]는 array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이

  • 모든 0 <= j < i에 대하여, D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

  • N = 6 일 때

    

• 풀이

  1 2 3 4 5 6 7 8 9 10

  n = int(input()) array = list(map, input().split()) dp = [1] * n for i in range(1, n): for j in range(0, i): if array[j] < array[i]: dp[i] = max(dp[i], dp[j] + 1) print(max(dp))

Comment and share

백준 12865 : 문제링크

• 문제유형 :

  • 탐색

  • 동적 프로그래밍

• 설명

  • 물품의 수 N, 배낭에 담을 수 있는 무게 K

  • 동적 프로그래밍을 이용하여 시간 복잡도(NK)

  • 핵심 아이디어: 모든 무게에 대하여 최대 가치를 저장하기

  • D[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치

  • 각 물품의 번호 i에 따라서 최대 가치 테이블 D[i][j]를 갱신하여 문제를 해결

  • 점화식
    

  • N = 4, K = 7 일 때
    

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12

  n, k = map(int, input().split()) dp = [[0] * (k + 1) for _ in range(n + 1)] for i in range(1, n + 1): weight, value = map(int, input().split()) for j in range(1, k + 1): if j < weight: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value) print(dp[n][k])

Comment and share