[Algorithm] 29강 : 다이나믹 프로그래밍의 기초 문제 풀이

<문제> 개미 전사 : 문제설명

 

문제 해결 아이디어

큰 문제를 위해 작은 문제를 통해 해결 

 

즉 이 문제의 점화식은

이렇게 된다.

 

문제 풀이

#정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int,input().split()))

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2,n):
	d[i] = max(d[i-1],d[i-2] + array[i])
    
계산된 결과 출력
print(d[n-1])

 

 

---

<문제> 1로 만들기 

 

 

문제 해결 아이디어

이렇게 각각의 경우의 수에서 가장 적은 값을 찾으면 된다.

이 해당하는 문제에 대한 점화식은 

이 값이 된다.

 

문제 풀이

#정수 x를 입력 받기
x = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001

# 다이나믹 프로그래밍(Dynamic Programming) 진행
for i in range(2,x+1):
	# 현재의 수에서 1을 뺴는 경우
    d[i] = d[i-1]+1
    #현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
    	d[i] == min(d[i],d[i//2] +1)
    #현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 ==0:
    	d[i] == min(d[i],d[i//3]+1)
    #현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 ==0:
    	d[i] == min(d[i],d[i//5]+1)

print(d[x]
    

 

---

<문제> 효율적인 화페구성

 

 

문제 해결 아이디어

해당 점화식을 가진다. 이 경우에는 각 화폐의 단위를 확인한다. 

2, 3, 5 를 모두 돌아가면서 해당하는 부분을 확인한다.

이런 식으로 모든 단위에다가 진행한다.

 

 

문제 풀이

# 정수 N,M을 입력 받기
n,m = map(int,input().split())

#N개의 화폐 단위 정보를 입력 받기

array = []
for i in range(n):
	array.append(int(input())
    
# 한 번 계산된 결과를 저장히가 위한 DP 테이블 초기화
d = [10001] * (m+1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)

d[0] = 0
for i in range(n):
	for j in range(array[i],m+1):
    	if d[j-array[i]] != 10001:# (i-k)원을 만드는 방법이 존재하는 경우
        	d[j] = min(d[j],d[j-array[i]]+1)
 
 #계산된 결과 출력
 if d[m] == 10001: #최종적으로 M원을 만드는 방법이 없는 경우
 	print(-1)
else:
	print(d[m])

 

 

---

<문제> 금광 문제 설명

 

 

문제 해결 아이디어

금광의 모든 위치에 대하여 다음의 세 가지만 고려하면 된다.

1. 왼쪽 위에서 오는 경우

2. 왼쪽 아래에서 오는 경우

3. 왼쪽에서 오는 경우

세 가지 경우중에서 가장 많은 금을 가지고 있는 경우를 테이블에 갱신해주어 문제를 해결

해당 문제의 점화식은 

이렇게 구성된다.

이 과정을 계속 해서 진행한다.

 

문제 풀이

# 테스트 케이스(Test case) 입력
for tc in range(int(input())):
	#금광 정보입력
    n,m = map(int(input().split())
    array = list(map(int,input().split()))
    # 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
    dp = []
    index = 0
    for i in range(n):
    	dp.append(array[index:index +m])
        index += m
    # 다이나믹 프로그래밍 진행
    for j in range(1,m):
    	for i in range(n):
        	# 왼쪽 위에서 오는 경우
            if i ==0:
            	left_up =0
            else:
            	left_up = dp[i-1][j-1]
                #왼쪽 아래에서 오는 경우
            if i == n-1 :
            	left_down = 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 ragne(n):
        	result = manx(result, dp[i][m-1])
        print(result)

 

 

---

<문제> 병사 배치하기

 

문제 해결 아이디어

이 문제의 기본 아이디어는 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)로 알려진 전형적인 다이나믹 프로그래밍 문제이다.

해당 식의 점화식은

이렇게 구성 된다.

 

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 ragne(0,i):
    	if array[j] < array[i]:
        	dp[i] = max(dp[i],dp[j]+1)

# 열외해야 하는 병사의 최소 수를 출력
print(n - max(dp))

---

이 자료는 동빈 나 님의 이코 테 유튜브 영상을 보고 정리한 자료입니다.

www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC