[다이나믹 프로그래밍] 피보나치 수열, 개미 전사, 1로 만들기, 효율적인 화폐 구성, 금광, 병사 배치하기 python

다이나믹 프로그래밍(Dynamic Programming, 동적 계획법)

• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
• 계산한 결과를 메모리에 저장해(Memoization) 다시 계산하는 일이 없게 함
• 구현 방식은 일반적으로 탑다운방식과 보텀업방식이 있음
  • 탑다운방식-큰 문제를 잘게 쪼개어 푸는 것
  • 보텀업방식-작은 문제들을 해결해 큰 문제를 해결하는 것

 

다이나믹 프로그래밍의 조건

주어진 문제가 다음의 조건들을 만족할 때 다이나믹 프로그래밍을 사용할 수 있음

1. 최적 부분 구조 (Optimal Substructure)
   • 큰 문제를 작은 문제로 나누고 작은 문제의 답을 모아 큰 문제를 해결할 수 있을 때
2. 중복되는 부분 문제 (Overlapping Subproblem)
   • 동일한 작은 문제를 반복적으로 해결해야 할 때

 

점화식

• 인접한 항들 사이의 관계식

 

메모이제이션 (Memoization)

• 다이나믹 프로그래밍을 구현하는 방법 중 하나
• 계산한 결과를 메모리 공간에 메모하는 기법으로 다이나믹 프로그래밍에 국학된 개념은 아님
• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
• 값을 기록해둔다는 점에서 캐싱(Caching)이라고도 함
• 계산한 결과를 담아두기만 하고 사용하지 않을 수도 있음
• 결과를 저장하기 위한 리스트를 DP 테이블이라고 부름

 

탑다운(하향식, 메모이제이션)  VS 보텀업(상향식)

• 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식임
• 탑다운 방식으로 문제를 풀 때 메모이제이션이라는 '하나의 기법'을 사용할 수도 있음

 

---

 

<예제> 피보나치 수열 - 탑다운 방식

d = [0]*100

def fibo(x):
    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))

 

 

<예제> 피보나치 수열 - 보텀업 방식

d = [0]*100

d[1] = 1
d[2] = 1
n = 99

# 반복문을 사용해 작은 문제부터 해결해나감
for i in range(3,n+1):
    d[i] = d[i-1]+d[i-2]

print(d[n])

 

---

 

다이나믹 프로그래밍 VS 분할 정복

• 공통점
  • 두 가지 모두 최적 부분 구조를 가질 때 사용할 수 있음
    • 최적 부분 구조 - 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모두 큰 문제를 해결할 수 있는 상황
• 차이점
  • 부분 문제의 중복 여부
    • 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨
    • 분할 정복 문제에서는 같은 부분 문제가 반복적으로 계산되지 않음

 

다이나믹 프로그래밍 문제에 접근하는 방법

• 주어진 문제가 다이나믹 프로그래밍 유형인지 파악하는 것이 중요함
• 우선 그리디, 구현, 완전 탐색 등의 아이디어로 해결할 수 있는지 검토함
  • 다른 알고리즘 풀이방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해보도록 함
• 일단 재귀 함수를 이용해 비효율적인 완전 탐색 프로그램을 작성한 뒤에(탑다운) 작은 문제에서 구한 답이 큰 문제에 그대로 사용될 수 있으면 코드를 개선시키는 방법을 사용할 수 있음
• 일반적인 코딩 테스트에서는 기본적인 다이나믹 프로그래밍 문제가 출제되는 편임

 

---

 

<문제> 개미 전사

n = int(input())

array = list(map(int, input().split()))
d = [0]*100

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로 만들기

n = int(input())

d = [0]*27

# 당장 5, 3, 2로 나눠떨어진다고 해도
# 다른 연산을 적절히 섞은 경우가 최소비용일 수 있기 때문에
# 모든 상황을 고려함
for i in range(2,n+1):

    d[i] = d[i-1]+1

    if i%5==0:
        d[i] = min(d[i//5]+1,d[i])

    if i%3==0:
        d[i] = min(d[i//3]+1,d[i])

    if i%2==0:
        d[i] = min(d[i//2]+1,d[i])


print(d[n])

 

 

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

n,m = map(int,input().split())
# 화폐의 가치를 입력받을 리스트
coins = []
# 입력되는 화폐의 가치가 최대 10000이므로 INF로 초기화
d = [10001]*(m+1)
d[0] = 0

# 화폐의 가치를 입력받음
for i in range(n):
    coins.append(int(input()))

# 화폐 종류 개수만큼 반복
for i in range(n):
	# 각 화폐의 가치~m까지 반복
    for j in range(coins[i], m+1):
    	# 만약 현재위치-현화폐의값이 10001이 아니라면
        # 만들 수 있는 금액이라는 뜻이므로
        if d[j-coins[i]]!=10001:
        	# 현 화폐를 하나 추가하는 경우와
            # 기존의 화폐개수 중 작은 것을 비교해 저장함
            d[j] = min(d[j-coins[i]]+1, d[j])

# 초기화했던 상태 그대로라면 주어진 화폐로 만들 수 없는 금액이니 -1 출력
if d[n]==10001:
    print(-1)
else:
    print(d[m])

 

 

<문제> 금광

 

왼쪽대각선 위, 왼쪽, 왼쪽대각선 아래에서 오는 경우 중 최대가 되는 값을 찾아야 함

for tc in range(int(input())):
    n,m = map(int(input().split))
    mine = list(map(int,input().split()))
    dp = []
    index = 0
    for i in range(n):
        dp[n].append(mine[index:index+m])
        index += m
    for j in range(1,m):
        for i in range(n):
        	# 0번째 행이라면 왼쪽대각선 '위'에서 오는 경우는 없음
            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]
            # 1번째 열부터 시작하므로 왼쪽에서 오는 경우는 항상 존재함
            left = dp[i][j-1]
            # 세 방향에서 오는 경우+현재 위치의 값이 최대가 되는 경우를 저장함
            dp[i][j] = max(left_up,left_down,left)+dp[i][j]
    result = 0
    for i in range(n):
        result = max(result, dp[i][m-1])
    print(result)

 

<문제> 병사 배치하기

 

최대 길이 감소 수열을 찾고, 그걸 만들기 위해서 열외시켜야 하는 병사의 출력을 하는 문제다.

얼마 전에 이분 탐색으로 최대 길이 증가 수열을 찾는 방법에 대해 공부했었기 때문에

이분탐색으로도 한 번 풀어봤다.

n = int(input())
# 병사들의 정보를 입력받음
soldiers = list(map(int,input().split()))
# 첫 번째 병사의 정보를 LIS 리스트에 저장함
LIS = [soldiers[0]]

# soldiers 리스트에서 정보를 하나씩 꺼내서 최대 길이 감소 수열을 생성해야 함
for i in range(n):
	# LIS에 저장된 마지막 값보다 현재 값이 더 작다면
    # LIS에 이어붙임
    if LIS[-1]>soldiers[i]:
        LIS.append(soldiers[i])
        
    # 그렇지 않다면 LIS에서 이분탐색을 해 soldiers[i]가 들어갈 자리를 찾아야 함
    else:
    	# 시작점과 끝점을 지정함
        start, end = 0, len(LIS)
        # 탐색이 가능할 때까지
        while start<end:
            mid = (start+end)//2
            # LIS[mid]가 더 크다면 더 오른쪽을 탐색해봐야 함
            if LIS[mid]>soldiers[i]:
                start = mid+1
            # 같거나 작을 때는 왼쪽을 탐색해봐야 함
            else:
                end = mid
        # 제자리에 soldiers[i]를 제자리에 넣음
        LIS[end] = soldiers[i]

# 열외할 병사 수 = 병사 수 - 최대길이감소수열의 길이
print(len(soldiers)-len(LIS))

 

n = int(input())
soldiers = list(map(int,input().split()))

# 각 원소까지의 최대길이감소수열의 길이를 저장할 리스트
dp = [1]*n

# 1번째 병사부터 반복문 시작
for i in range(1,n):
	# 자기 앞에 있는 병사들을 탐색함
    for j in range(0,i):
    	# 만약 자기 앞에 전투력이 더 높은 병사가 있다면 == 감소수열을 만족한다면
        if soldiers[i]<soldiers[j]:
        	# 기존에 저장된 감소수열의 길이와, 새로운 감소수열의 길이 중 큰 걸로 갱신
            dp[i] = max(dp[i],dp[j]+1)

# 열외할 병사의 수 = 병사의 수 - 최대길이감소수열의 길이
print(n-max(dp))
print(dp)

 

 

 

참고자료 출처

https://www.youtube.com/watch?v=5Lu34WIx2Us