파이썬 알고리즘 | 섹션 8. Dynamic programming(동적계획법)

0. 동적계획법이란?

개념 출처 : 링크텍스트

동적계획법
:입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
:상향식 접근법으로, 가장 최하위 해답을 구한 후 이를 저장하고 해당 결과값 이용해서 상위 문제를 출어가는 방식

• Memoization
  :프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
  
• 문제를 잘게 쪼갤 때 부분 문제는 중복되어 재활용
  (ex)피보나치 수열

분할 정복
: 문제를 나눌 수 없을 때까지 나눠서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘

• 하향식 접근법으로 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식
• 일반적으로 재귀함수로 구현
• 문제 잘게 쪼갤 때 부분문제는 서로 중복되지 않음
  (ex) 병합정렬, 퀵정렬 등

동적 계획법과 분할 정복의 공통점과 차이점

(1) 공통점
문제를 잘게 쪼개서 가장 작은 단위로 분할

(2) 차이점

• 동적 계획법 :
  부분문제는 중복되어 상위 문제 해결 시 사용
  메모이제이션 기법 사용(부분 문제의 해답을 저장해서 재활용하는 최적화 기법)
• 분할 정복
  부분 문제는 서로 중복되지 않음
  메모이제이션 사용이 안됨

1. 네트워크 선 자르기(Bottom-Up)

• f(n) = f(n-2) + f(n-1)

n=int(input())
dy=[0]*(n+1)
dy[1] =1
dy[2]=2
for i in range(3,n~~텍스트~~+1) :
    dy[i]=dy[i-1]+dy[i-2]
print(dy[n])

2. 네트워크 선 자르기(Top-Down : 재귀, 메모이제이션)

(1) 메모이제이션만 하고 가지컷은 하지 않은 것

def dfs(len): #각 길이의 선마다 나올 수 있는 종류의 수
    if len==1 or len==2: #얘네를 기억ㅎ두고 저장해두기
        return len
    else :
        dy[len] = dfs(len-1)+dfs(len-2) # dfs(7)=dfs(6)+dfs(5)
        return dy[len]

if __name__=='__main__':
    n=int(input())
    dy=[0]*(n+1)
    print(dfs(n))

(2) 이미 값이 정해진 애를 만나면 가지 cut해주기
(dy[k] >0이면 이미 앞에서 지정된거니깐 따로 뭐 하지 말고 return dy[k]해주면 됨

def dfs(len):
    if dy[len]>0: #이미 입력돼있을 때! 밑으로 가지 뻗지 말고 원래 있던 값 return해라
        return dy[len]
    if len==1 or len==2: #종착점
        return len
    else :
        dy[len] = dfs(len-1)+dfs(len-2) # dfs(7)=dfs(6)+dfs(5)
        return dy[len]

if __name__=='__main__':
    n=int(input())
    dy=[0]*(n+1) #기록할 테이블
    print(dfs(n))

3-1. 도전과제 : 계단오르기(Top-Down : 메모이제이션)

• 앞에 전선 자르기 문제와 동일한 맥락
• dfs(x) x경우에 나올 수 있는 모든 경우의 수를 나타내는 것

def dfs(x) :
    if dy[x]>0:
        return dy[x]
    if x==1 or x==2:
        return x
    else : 
        dy[x]=dfs(x-1) + dfs(x-2)
        return dy[x]

if __name__=='__main__':
    n=int(input())

    dy=[0]*(n+1)
    print(dfs(n))
    

3-2. 도전과제 : 돌다리 건너기(Bottom-Up)

• 돌다리를 다 건넌다는 건 육지까지 도달해야한다는 뜻, 따라서 주어진 돌의 갯수 +1 까지
  가야지 비로소 땅에 도달한 것이라고 볼 수 있음

def dfs(x) :
    if dy[x]>0:
        return dy[x]
    if x==1 or x==2:
        return x
    else : 
        dy[x]=dfs(x-1) + dfs(x-2)
        return dy[x]

if __name__=='__main__':
    n=int(input())
    dy=[0]*(n+2)
    print(dfs(n+1)) #주어진 돌의 갯수보다 하나 더 큰 데까지 도달하는 경우 구하는 것

4. 최대 부분 증가수열(LIS : Longest Increasing Subsequence ) ** 복습

n=int(input())
a=list(map(int,input().split()))
a.insert(0,0)
dy=[0]*(n+1)
dy[1]=1
for i in range(2,n+1) :
    maxi=-1
    for j in range(i) :
        #print(dy[j])
        if a[j]<a[i] and maxi<dy[j] :
            maxi=dy[j]
    dy[i]=maxi+1
print(max(dy))

5. 최대 선 연결하기(LIS 응용)

: 이것도 최대 부분 증가수열과 똑같은 맥락임

• 응용해서 다 연결해놓고, 최소 몇개의 선을 제거해야 교차하지 않는 선을 최대로 구할 수 있는가 ?할 수도 있음 => 그렇다면 최대 증가수열을 구해서 증가수열의 길이를 총 길이에서 빼주면 됨

• 혹은 다리 만들 때 같은 번호로 연결되어야 한다 할 때 만들 수 있는 최대다리개수를 물어볼 수도 있음 (이것은 아예 이 최대 선 연결하기랑 똑같은 문제)

n=int(input())
arr=list(map(int, input().split()))
arr.insert(0,0)
dy=[0]*(n+1)
dy[1]=1
res=0
for i in range(2, n+1):
    max=0
    for j in range(i-1, 0, -1):
        if arr[j]<arr[i] and dy[j]>max:
            max=dy[j]
    dy[i]=max+1
    if dy[i]>res:
        res=dy[i]
print(res)

6. 가장 높은 탑 쌓기(LIS응용)

• 우선 밑면의 넓이가 큰 순대로 정렬해준다
• 순서대로 제시될 때마다 이것이 탑의 가장 위에 있을 때, 밑에 올 수 있는 애들의 갯수를 세어서 dy에 넣어주는 방법으로 접근,
  => 이때 밑에 올 수 있는 애들은 나보다 앞 순서에 있는 애들 중에서 나보다 무게가 무거운 애들, 나보다 앞에 있는 애들은 밑넓이는 나보다 큰 애들이니깐 무게만 더 나가면 내 밑에 올 수 있음

ar=[0] #넓이
h=[0] #높이
w=[0] #무게
n=int(input())
k=[]
for i in range(n) :
    (a,b,c)=map(int,input().split())
    k.append((a,b,c))
    k.sort(reverse=True)
for i in range(len(k)) :
    ar.append(k[i][0])
    h.append(k[i][1])
    w.append(k[i][2])
dy=[0]*(n+1)
dy[1]=h[1]
for i in range(1,n+1) :
    maxx=0
    for j in range(i) :
        if w[i]<w[j] and dy[j]>maxx : #만약 밑에 여러개의 벽돌이 올 수 있으면 dy중에서 맥스인것으로..
            maxx=dy[j]
    dy[i]=h[i]+maxx
print(max(dy))
    

7. 알리바바와 40인의 도둑(Bottom-Up)

• 나에게로 오는 애들은 위에서 오거나 왼쪽에서 오거나 둘중에서 하나다
  그래서 이 둘중에서 더 작은애를 나랑 더하면 되는데, 왼쪽이나 위가 없는 경우가 있을 수도 있다. (이미 내가 가장자리기 때문에),
  따라서 가장자리인 애들 중에 맨 왼쪽인 애들은 위쪽 애를 필연적으로 더하게 하고
  맨 위에 있는 애들은 필연적으로 왼쪽에서 더하게 한다

n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
dy=[[0]*(n+1) for _ in range(n)]
dy[0][0]=a[0][0]

for i in range(n) :
    for j in range(n) :
        if i-1<0 :
            dy[i][j]=dy[i][j-1]+a[i][j]
        elif j-1<0:
            dy[i][j]=dy[i-1][j]+a[i][j]
        else:
            dy[i][j]=min(dy[i][j-1],dy[i-1][j]) + a[i][j]

print(dy[n-1][n-1])

8. 알리바바와 40인의 도둑(Top-Down)

(2) Top - Down dfs 활용 - 메모이제이션 아직 안해서 Time Limit 걸리는 것

def dfs(x,y) :
    if x==0 and y==0:
        return arr[0][0]
    else : 
        if y==0 :
            return dfs(x-1,y)+arr[x][y] #y는 0이니깐 건들지말고 x만 move
        elif x==0:
            return dfs(x,y-1) + arr[x][y]
        else :
            return min(dfs(x-1,y), dfs(x,y-1))+arr[x][y]
if __name__=='__main__':
    n=int(input())
    arr=[list(map(int,input().split())) for _ in range(n)]
    dy=[[0]*n for _ in range(n)]
    print(dfs(n-1,n-1))

(3) Top - Down dfs 활용 - 메모이제이션 한 것

def dfs(x,y) :
    if dy[x][y]>0: #dy[x][y]가 이미 있으면 그냥 넘어가기
        return dy[x][y]
    if x==0 and y==0:
        return arr[0][0]
    else : 
        if y==0 :
            dy[x][y]= dfs(x-1,y)+arr[x][y] 
        elif x==0:
            dy[x][y]= dfs(x,y-1) + arr[x][y]
        else :
            dy[x][y]= min(dfs(x-1,y), dfs(x,y-1))+arr[x][y]
        return dy[x][y] #dy[x][y]를 어찌됐건 출력해준다
if __name__=='__main__':
    n=int(input())
    arr=[list(map(int,input().split())) for _ in range(n)]
    dy=[[0]*n for _ in range(n)]
    print(dfs(n-1,n-1))
    

최솟값 구할 때는 dy=[5000]x(n+1) .. 이런식으로 적용
최댓값 구할 때는 dy=[0]x(n+1)

9. 가방문제(냅색 알고리즘 : Knapsack algorithm)

: 중복을 허용하는 냅색문제

• dy는 m길이로 해준다 (가방에 담을 수 있는 무게의 값)
• dy[j]는 가방에 j라는 무게 까지 담는다 가정 시에 보석의 최대가치
• 우선 동적계획법은 작은 것에 집중해서 차근차근 보는 거니깐 5(w),12(v) 하나의 값만 있다고 가정하면
  dy[j-w] + v
  (j의 무게에서 보석의 무게 빼고 남은 공간 자리에서의 최댓값 + 가치)

n, m= map(int, input().split())
dy=[0]*(m+1)
for i in range(n) :
    w,v=map(int,input().split())
    for j in range(w,m+1) :#자신이 해당하는 무게에서부터 가방의 무게까지
        dy[j]=max(dy[j], dy[j-w]+v) #기존의 값 , j무게 가방에서 w만큼 뺀것에 가치를 더한 것
print(dy[m])

10. 동전교환(냅색알고리즘)

: 중복 허용하는 냅색 알고리즘

if __name__=="__main__":
    n=int(input())
    coin=list(map(int, input().split()))
    m=int(input())
    dy=[1000]*(m+1); #dy를 0이 아니라 크게 설정해놓고
    dy[0]=0 # 꼭 첫번째 애는 0으로 초기화 해주고,, 0을 대체할 수 있는 동전은 없으니!!!!!!!!!!!!!
    for i in range(n):
        for j in range(coin[i], m+1):
            dy[j]=min(dy[j], dy[j-coin[i]]+1)
    print(dy[m])

11. 최대점수 구하기(냅색 알고리즘)

: 중복 허용하지 않는 냅색 알고리즘,
이건 거꾸로 검열하다 보면 중복 안되면서 진행 가능

n,m=map(int,input().split())
k=[]
for i in range(n) :
    s,t=map(int,input().split())
    k.append((s,t))
dy=[0]*(m+1)
for i in range(n) :
    for j in range(m,k[i][1]-1,-1) : #여기서 거꾸로 보면서 dy 갱신
        dy[j]=max(dy[j],dy[j-k[i][1]]+k[i][0])
print(max(dy))

12. 플로이드-와샬(그래프 최단거리) *복습필수*

• dis=[[5000]x(n+1) for _ in range(n+1)]
  #최솟값 구해야하니깐 [0]아니고 [5000]으로

• 최단거리를 구할 때 쓰이는 것, 3중 for문 도는 것 중요

 for k in range(1,n+1) :
        for i in range(1,n+1) :
            for j in range(1,n+1) :
                dis[i][j]=min(dis[i][j], dis[i][k]+dis[k][j])#i->k->j 거치는 비용

- 오지 않은 곳, 도달하지 못하는 데는 초기값으로 유지되는 곳

if dis[i][j]==5000: #오지 않았다는 뜻, 처음 값 그대로니깐
                print('M', end=' ')

if __name__=='__main__' :
    n,m=map(int,input().split())
    dis=[[5000]*(n+1) for _ in range(n+1)] #최솟값 구해야하니깐 [0]아니고 [5000]으로
    for i in range(1,n+1) :
        dis[i][i]=0 #자기 자신에서 자기 자신한테로 가는 애들은 0이라고 표시
    for i in range(m) :
        a,b,c= map(int,input().split())
        dis[a][b]=c #i에서 j로 직행하는 것
    for k in range(1,n+1) :
        for i in range(1,n+1) :
            for j in range(1,n+1) :
                dis[i][j]=min(dis[i][j], dis[i])[k]+dis[k][j])#i->k->j 거치는 비용
    for i in range(1,n+1) :
        for j in range(1,n+1) :
            if dis[i][j]==5000: #오지 않았다는 뜻, 처음 값 그대로니깐
                print('M', end=' ')
            else:
                print(dis[i][j], end=' ')
        print()
        

13. 회장뽑기(플로이드-와샬 응용)

• 방향이 양방향인지, 단방향인지 드러나있지 않을때도 多
  스스로 잘 판단해서 입력해 줘야 함
• 여기서 a,b가 친구라면 b랑a도 친구니깐 양방향이다
• 자기한테서 자기갈 때는 미리 dis에 0,0 입력해두기
• 바로 2-3 이 친구면 2->3 방향이 1인 동시에 3->2 방향도 1이라는 사실을 누락하였음. 문제에 방향이 정확히 표기되지 않은 경우에도 내가 잘 추측해서 해야함

if __name__=="__main__":
    n=int(input())
    dis=[[100]*(n+1) for _ in range(n+1)]
    for i in range(1, n+1):
        dis[i][i]=0
    while True:
        a, b=map(int, input().split())
        if a==-1 and b==-1:
            break
        dis[a][b]=1
        dis[b][a]=1

    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                dis[i][j]=min(dis[i][j], dis[i][k]+dis[k][j])

    res=[0]*(n+1)
    score=100
    for i in range(1, n+1):
        for j in range(1, n+1):
            res[i]=max(res[i], dis[i][j])
        score=min(score, res[i])
    out=[]
    for i in range(1, n+1):
        if res[i]==score:
            out.append(i)
    print("%d %d" %(score, len(out)))
    for x in out:
        print(x, end=' ')
        

14. 위상정렬(그래프) **복습꼬옥

• 데큐를 활용하는 것
• 진입 차수가 중요하다 **
• 여기서 진입 차수를 다 수행해주고나서야 내 일을 하는 것이 가능
• 진입차수의 갯수 : 사전에 선행해서 수행되어야 할 임무
• 진입차수 입력해주는 값 만들고 유연하게 넣어줬다가 빼주면서
  그에 상응하는 동작 하기
  ===> 진입차수 없는 애들을 q에 넣어주는 것

(1) 준비 시켜 놓을 값

from collections import deque

n,m=map(int,input().split())
g=[[0]*(n+1) for _ in range(n)]
degree=[0]*(n+1)
q=deque()

(2)

from collections import deque
sys.stdin=open("input.txt", "r")
n, m=map(int, input().split())
graph=[[0]*(n+1) for _ in range(n+1)]
degree=[0]*(n+1)
dQ=deque()
for i in range(m):
    a, b=map(int, input().split())
    graph[a][b]=1
    degree[b]+=1 #진입차수 수를 갱신해주는 것
for i in range(1, n+1):
    if degree[i]==0: #차수가 0이라서 선행해야 할 작업이 없는 애는 바로 q에 넣어버리면 됨
        dQ.append(i)
while dQ:
    x=dQ.popleft()
    print(x, end=' ') #q에 들어오는 순서대로 처리된 것
    for i in range(1, n+1):
        if graph[x][i]==1: #얘가 진입차수 였던 애들한테서 진입차수의 갯수 하나씩 빼주기
            degree[i]-=1
            if degree[i]==0: #진입차수가 0이 되면 앞에서 더이상 처리해줄 값이 없으니깐 q에 넣어주기
                dQ.append(i)