CS/알고리즘
[알고리즘] 다이나믹 프로그래밍
삶_
2022. 7. 5. 09:29
다이나믹 프로그래밍(동적계획법)
- 다음 두가지 조건을 만족할 때 사용하기
- 최적부분구조
- 큰 문제를 작은문제로 나눌수있음
- 중복되는 부분 문제
- 동일한 작은 문제를 반복적으로 해결해야함
피보나치 수열
- 1,1,2,3,5,8,13,21,34,55,89 ...
- 점화식 : 인접한 항들 사이의 관계식
- 1,1을 더해 2. /// 2,3을 더해 5 ...
- 문제점 : 재귀함수를 통해 해결하면, 같은 것이 중복적으로 호출되는 문제가 있다
탑다운 VS 보텀업
- 메모이제이션(탑다운, 하향식)
- 이전에 한 번 계산된 결과를 일시적으로 메모리 공간에 메모하는 기법
- 값을 기록해 놓는다는 점에서 캐싱이라고도 함
#메모이제이션 하기 위한 리스트 초기화
d = [0] * 100
#피보나치 함수를 재귀함수로 구현
def fibo(x):
#종료 조건(1,2면 1을 반환. 첫시작은 1,1 이니까! x=3이면 아마 이럴거같다.)
if x == 1 or x == 2:
return 1
#이미 연산된 적 있는 문제라면 그대로 반환
if d[x] != 0:
return d[x]
#아직 계산하지 않은 문제라면 피보나치 결과로 반환해줌
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
print(fibo(99))
- 보텀업(상향식)
- 다이나믹 프로그래밍의 전형적인 형태
- DP 테이블 : 결과저장용 리스트
#DP 테이블 초기화
d = [0] * 100
#첫번째, 두번째 피보나치수 초기화
d[1] = 1
d[2] = 1
n = 99 #99까지를 구하는 것이기 때문에
#피보나치 함수를 반복문으로 구현. (3부터 진행 (d[1]+d[2])값을 아니까)
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
print(d[n])
문제풀이
- 개미전사 -> 메뚜기 식량창고 공격
여러개의 식량창고가 일직선으로 이어짐
서로 인접한 식량창고가 공격받으면 바로 알아챌수있음
최소한 한칸이상 떨어진 식량창고 약탈 - 첫째줄에 식량창고의 개수 n
둘째줄에 공백 기준으로 각 식량창고에 저장된 식량의 개수 k
첫째줄에 개미전사가 얻을수있는 식량의 최댓값 출력하기
import sys
n = int(sys.stdin.readline())
k = list(map(int, sys.stdin.readline()))
#DP테이블
d = [0]*n
#인덱스 1+3과 2를 비교 반복
#순차적으로 비교해서 맨 마지막에 나오는 값을 출력함
#첫, 두번째값을 먼저 비교해준다. 첫,두번째를 대입해야 for문에서 i-1,i-2를 할수있어서
d[0] = k[0] #첫번째값
d[1] = max(k[0], k[1]) #두번째엔 첫번째,두번째를 비교한 값
for i in range(2, n):
#i번째까지의 최대값 구하기
d[i] = max(d[i-1], d[i-2]+k[i])
#마지막값을 출력 = 결과
print(d[n-1])
- 보텀업 문제
- 정수 x가 주어질때 x에 사용가능한 연산은 4가지
1. x가 5로 나누어 떨어지면, 5로 나눔
2. x가 3으로 나누어 떨어지면, 3으로 나눔
3. x가 2로 나누어 떨어지면, 2로 나눔
4. x에서 1을 뺌 - 1 <= x <= 30000
- 연산 4개를 사용해 값을 1로 만들려고 함
연산을 사용하는 최소 횟수값을 출력하기. - 피보나치 수열 문제와 관련있음
#단, 이 식은 n-1빼고 해당수로 나누어 떨어질때만 적용이 가능
import sys
n = int(sys.stdin.readline())
count = 0
while n != 1:
#n이 1이면 n-1이 0이되니까 최소 1이될수있게 +1함
#4가지 과정중 제일 작은수
n = min(n-1, n//2, n//3, n//5)+1
count += 1
print(count)#따라서 아래처럼 풀어야함!
import sys
x = int(sys.stdin.readline())
#DP 테이블 초기화
#0은 안치고 인덱스 1부터 접근할거기 때문에 30001로 설정
#d[n] = n을 1로 만드는 최소 연산의 수
d = [0]*30001
#d[7] = 1 + d[6] 처럼 작은 문제들로 큰문제를 해결할수 있는 구조
for i in range(2, x+1):
#현재의 수에서 1을 빼는 경우 (d[2]=1, d[1]=0)
d[i] = d[i-1]+1
#2,3,5의 공배수는 안되므로 if문으로 적어야함
#1을 뺀 경우 vs 2로 나눈경우
if i%2 == 0:
d[i] = min(d[i], d[i//2]+1)
#2로 나눈경우 vs 3으로 나눈 경우
if i%3 == 0:
d[i] = min(d[i], d[i//3]+1)
#3으로 나눈 경우 vs 5로 나눈 경우
if i%5 == 0:
d[i] = min(d[i], d[i//5]+1)
print(d[x])
- 보텀업 문제
- n가지종류 화폐
화폐 갯수를 최소한으로 이용해서
가치의 합이 m원이 되도록함 - 첫째줄에 n가지 화폐, 가치의 합이 주어짐
불가능할땐 -1출력 - 1<=n<=100
1<=m<=10000
import sys
# DP 테이블 초기화 (INF(무한)값으로 설정) (숫자는 크게 상관없음)
# m이 10000까지이기 때문에 10001 라는 값을 통해 화폐구성이 가능하지 않은 인덱스를 알게해줌
# d[m] = 총 화폐금액이 m 일때, 최소 화폐갯수
array = []
d = [10001]*(m+1)
n, m = map(int, sys.stdin.readline().split())
for _ in range(n):
array.append(int(sys.stdin.readline()))
# 보텀업
d[0] = 0
for i in range(n): # 화폐종류갯수
for j in range(array[i], m+1): # 화폐 단위 ~ 총 화폐금액
if d[j-array[i]] != 10001: # 현재 금액 - 화폐단위금액
# 10001을 다른값으로 변경
# 점화식을 이용해 푼다
d[j] = min(d[j], d[j - array[i]]+1)
if d[m] == 10001:
print(-1)
else:
print(d[m])
- n x m 크기의 금광
- m-1번에 걸쳐서 오른쪽위,오른쪽,오른쪽아래 중 하나의 위치로 이동해야함
채굴자가 얻을 수 있는 금의 최대 크기 - 첫째줄에 테스트케이스 갯수가 입력됨
1<= T <=1000 - 그다음 테스트 케이스갯수만큼 아래가 입력됨
n과(세로) m이(가로) 공백으로 구분되어 입력됨
1 <= n,m <= 20 - nxm 개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됨
1 <= 금의 개수 <=100 - 테스트 케이스마다 채굴자가 얻을수있는 금의 최대 크기 출력
# 테스트 케이스 만들기
for tc in range(int(input())):
# 금광 정보 입력하기
n, m = map(int, input().split()) # 세로, 가로
array = list(map(int, input().split())) # 일단 한줄로 받는다
# 2차원 테이블로 초기화 하기
# dp [i][j] 가는만큼
dp = []
index = 0
# 한줄로 받은 dp 자르기
for i in range(n):
dp.append(array[index:index + m])
index += m
# 다이나믹 프로그래밍 실행
for j in range(1, m): #1부터 시작. 맨왼쪽, 0이기 때문에
for i in range(n):
# 왼쪽 위에서 오는 경우
if i==0: left_up = 0 # 위로 움직일수가 없으니 0
else: left_up = dp[i-1][j-1] # 원래 위치에서 왼쪽 위
# 왼쪽 아래에서 오는 경우
if i == n-1: left_down = 0 #아래로 움직일수 없으니 0
else: left_down = dp[i+1][j-1] # 원래 위치에서 왼쪽 아래
# 왼쪽에서 오는 경우
left = dp[i][j-1] # 가로만 변함
dp[i][j] = dp[i][j] + max(left_up, left_down, left) # 그 값에 제일 많은 금광수+원래값을 원래값에 대입
result = 0
for i in range(n):
result = max(result, dp[i][m-1]) # 이동해서 간 결과값들 중 제일 큰 값 걸러내기
print(result)
- n명의 병사 무작위로 나열됨
각 병사는 특정한 값의 전투력을 보유함.
병사를 배치할 때, 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 합니다
앞쪽에 있는 병사가 뒤쪽에있는 병사보다 높아야함 - 특정한 위치에 있는 병사를 열외시킴.
그러면서도 남아있는 병사의 수를 최대로 하고싶음. - 첫째줄에 병사의 수 n (1<= n <= 2000)
둘째줄에 병사의 전투력, 공백으로 구분되어 주어짐 - 첫째줄에 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력
- 이 문제의 아이디어
- 가장 긴 증가하는 부분 수열
전형적인 다이나믹 프로그래밍 문제의 아이디어 - 어떤 특정한 배열이 있다고 칠때, 인덱스마다 값이 증가하는 폭이 점점 커지는 값들이 모인 아이디어를 말함
- 본 문제는 가장 긴 감소하는 부분 수열을 찾는 문제 (내림차순이므로), 배열 순서를 뒤집거나 부등호를 반대로 해야함.
- 가장 긴 증가하는 부분 수열
n = int(input())
array = list(map(int, input().split()))
#순서를 뒤집어서 '최장 증가 부분 수열' 문제로 변환
array.reverse()
# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
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(n - max(dp))