[알고리즘분석] 2. 동적계획법

출처 : https://www.codeproject.com/Articles/5282400/Dynamic-Programming-What-How-When

이번 포스팅에서는 동적계획법에 대해서 알아보도록 하겠습니다.

동적계획법은 앞서 배운 분할정복 방법과 반대인 상향식 해결방법(bottom up)입니다.

분할정복식처럼 문제를 나눈 후에 나누어진 부분들을 먼저 풀고, 인덱스를 이용해 작은 문제들의 중복해결을 배제합니다. 그리고 작은 문제의 해결들을 점차 큰 문제의 해결로 확산하는 것이죠. 특히 이전에 풀었던 정보를 저장한다는 것이 가장 중요한 동적계획법의 핵심 내용입니다!

그렇다면 여러 예를 살펴보면서 동적 계획법에 대해서 더 자세히 알아봅시다!

0. 동적계획법 - 이항계수

고등학교때 배운 이항계수를 구하는 방법입니다. nCk라는 공식을 가지고 있는데, 이걸 파이썬으로 구현하면 아래와 같습니다.

# 재귀적 방법, 시간복잡도 2*nCk-1
def bin(n,k):
    if k == 0 or n == k:
        return 1
    else:
        return bin(n-1,k-1) + bin(n-1,k)

print(bin(10,5))

# 배열 , 시간복잡도 O(nk)

def bin2(n,k):
    B = [[0 for i in range(k+1)] for j in range(n+1)]
    for i in range(n+1):
        for j in range(min(n,k)+1):
            if j == 0 or j == i:
                B[i][j] = 1
            else:
                B[i][j] = B[i-1][j-1] + B[i-1][j]
    return B[n][k]
            
print(bin2(10,5))

1. 동적계획법 - 최단경로문제

최단경로문제는 모든 도시에 대해 한 도시에서 다른 도시로 갈 수 잇는 가장 짧은 길이를 찾는 문제입니다.

하나 이상의 많은 해답이 존재할 때 최적 해답을 찾는 최적화문제의 일종입니다.

이 문제를 푸는 방법은 여러 가지가 있는데, 가장 처음으로는 Brute-force 알고리즘(무작정 알고리즘)을 사용해보도록 하겠습니다.

이 알고리즘은 정점 vi에서 다른 정점 vj로의 가능한 모든 경로들의 길이를 구한 뒤 그들 중에서 최소 길이의 경로를 찾는 알고리즘입니다.

이 알고리즘은 다른 정점으로 갈 때마다 그 정점의 모든 경로를 다 거치기 때문에 (n-2)!번의 경로를 찾아야 합니다. 이전 차수 관련 포스팅(맨 첫번째!!)에서 팩토리얼이 들어간 시간복잡도는 지수보다도 나쁜 시간복잡도라고 말씀드린걸 기억해내면 되겠습니다! ~~네 정말 비효율적이에요!~~

위와 같이 D를 구해야 하는데, 모든 경우를 전부 고려한 분석을 생각해봅시다.

for문을 세 번 돌려서 min값들을 매번 추출하면 구할 수 있습니다. 하지만 시간 복잡도는 암울한 수준으로 떨어지죠.

그래도 아래와 같은 이유로 공간복잡도에서 손해를 최소화합니다.

(코드는 아래 한번에 올리겠습니다!)

추가로 최단 경로의 길이가 포함된 배열을 출력하기 위해서 새로운 P라는 행렬을 출력해봅시다.

이제 Floyd의 알고리즘 1, 2를 합친 코드를 공개합니다!

(Floyd의 알고리즘 2 부분은 p와 관련된 부분이고, 나머지 부분이 Floyd의 알고리즘 1 부분입니다!)

# Floyd 알고리즘 1! 시간복잡도는 O(n^3) .... 암울하다!

import copy

def allShortestPath(g, n):
    # node number는 1부터 n
    
    # d 행렬 g로 초기화
    d = copy.deepcopy(g)

    # p 행렬을 영행렬로 초기화
    p = [[0 for i in range (n)] for j in range (n)]
    
    for k in range (n): # 첨자를 맨 앞에 적어야 순서대로 계산됨 - 추가공간 필요 없이 D만으로 데이터 저장 가능
        for i in range(n):
            for j in range(n):
                if d[i][k]+d[k][j] < d[i][j]:
                    p[i][j] = k+1 # v는 1부터 시작하므로
                    d[i][j] = d[i][k] + d[k][j]
    
    return d, p

# Floyd 알고리즘 2! 이친구의 시간복잡도는 O(n)!!
def path(p,q,r):
    if (p[q-1][r-1] != 0): # v가 1부터 시작하기 때문에 -1을 빼줘야함
        path(p,q,p[q-1][r-1])
        print("v" + str(p[q-1][r-1]), end=" ") # int형을 string형과 더할 수 없기 때문에 int형을 str로 바꿔줌
        path(p,p[q-1][r-1],r)
    
def printMatrix(d):
    n=len(d[0])
    for i in range(0,n):
        for j in range(0,n):
            print(d[i][j], end=" ")
        print()
        
inf=1000
g=[[0,1,inf,1,5],
  [9,0,3,2,inf],
  [inf,inf,0,4,inf],
  [inf,inf,2,0,3],
  [3,inf,inf,inf,0]]
d, p= allShortestPath(g,5)

printMatrix(g)
print()
printMatrix(d)
print()
printMatrix(p)

path(p, 5, 3)

추가로, 어떤 문제 사례에 대한 최적 해가 그 사례를 분할한 부분 사례에 대한 최적해를 항상 포함하고 있으면 그 문제는 최적의 원칙이 적용된다고 할 수 있습니다.

그리고 이런 최적의 원칙이 적용되어야지만 동적계획법을 사용할 수 있습니다.

동적계획법의 핵심은 이전에 풀었던 자료를 저장해놨다가 빠르게 처리하는 것이죠!

여기서 최적의 원칙이 적용되지 않는 대표적인 예는 최장경로 문제입니다.

2. 동적계획법 - 연쇄행렬곱셈

행렬 여러개를 동시에 곱셈할 때, 잘 선택해야 가장 빠르게 연산을 할 수 있습니다. 잘못하면 괜히 곱셈 횟수만 늘어나죠.

만약, Brute-force(무작정 알고리즘)으로 이 문제를 푸려고 하면, 행렬의 수가 늘어난다면 당연히 기하급수적으로 계산의 수가 늘 것입니다.

그렇기 때문에 우리는 최적의 원칙이 적용되는지를 확인하고, 적용된다면 동적계획법으로 문제를 풀어야 합니다.

본 문제는 당연히! 적용이 되니까 제가 여기다 적었겠죠?!

아래 그림을 보면 보다 이해가 쉬울텐데, 대각선으로 계산을 하고, 오른쪽 위로 올라가면서 이전의 계산 내용을 바탕으로 추가적인 계산 없이 빠르게 M을 채울 수 있습니다.

또한 방금 했던 것처럼 경로를 담고 있는 행렬인 P를 만들어줍시다.

필요한 내용을 모두 숙지했다면, 실제로 파이썬으로 알고리즘을 만들어봅시다!

import utility

# 최적해 순서 출력 : 시간복잡도는 O(n)입니다!
def order(p, i, j):
    if i == j:
        print("A" + str(i), end='')
    else:
        k = p[i][j]
        print("(", end='')
        order(p, i, k)
        order(p, k+1, j)
        print(")", end='')


d = [5,2,3,4,6,7,8]
n = len(d) - 1

m = [[0 for j in range(1, n + 2)] for i in range(1, n + 2)]
p = [[0 for j in range(1, n + 2)] for i in range(1, n + 2)]

# 최소곱셈 알고리즘 : 시간복잡도는 for문 3번으로 O(n^3)입니다!
for diagonal in range(1, n):
    for i in range(1, n-diagonal+1):
        j = i + diagonal
        min_val = 1000
        min_k = i
        for k in range(i, j):
            num = m[i][k] + m[k+1][j] + d[i-1]*d[k]*d[j]
            if num < min_val:
                min_val = num
                min_k = k
        m[i][j] = min_val
        p[i][j] = min_k

utility.printMatrix(m)
print()
utility.printMatrix(p)
order(p, 1, 6)

아래 코드는 import utility를 사용하기 위한 utility.py 파일입니다.

이 파일이 디렉토리 내에 있어야 정상적으로 import를 해서 printMatrix, printMatrixF, print_inOrder, print_preOrder 함수를 사용하실 수 있습니다!!

# utility.py

def printMatrix(d):
    m = len(d)
    n=len(d[0])
    
    for i in range(0,m):
        for j in range(0,n):
            print("%4d" % d[i][j],end=" ")
        print()

def printMatrixF(d):
    n=len(d[0])
    for i in range(0,n):
        for j in range(0,n):
            print("%5.2f" % d[i][j],end=" ")
        print()

def print_inOrder(root):
    if not root:
        return
    print_inOrder(root.l_child)
    print(root.data)
    print_inOrder(root.r_child)

def print_preOrder(root):
    if not root:
        return
    print(root.data)
    print_preOrder(root.l_child)
    print_preOrder(root.r_child)

def print_postOrder(root):
    if not root:
        return

    print_postOrder(root.l_child)
    print_postOrder(root.r_child)
    print(root.data)

추가로 시간복잡도를 구하는 슬라이드를 올립니다!

3. 동적계획법 - 최적이진검색트리

이번에는 이진검색트리입니다!

양쪽으로 나누어서 찾는 방식은 같지만, 각 키를 찾을 확률이 주어져 있다면(같지 않은 상태!!) 키를 찾는데 걸리는 평균 시간이 최소가 되도록 이진트리를 구축하는 문제입니다.

여기서 확률이 모두 다르기 때문에, 전부 뒤져가면서 찾는 것은 굉장히 비현실적입니다. 따라서 동적 계획법을 이용한 효과적인 방법이 필요합니다.

하나를 기준으로 양 옆으로 쪼개가면서 방법을 찾는 것으로, 동적계획법으로 최적이진검색트리를 구할 수 있습니다.

아래 수도코드를 제공합니다!

# 시간복잡도는 for문 2개와 시그마 1개로, O(n^3)입니다!

import utility
class Node:
    def __init__(self,data):
        self.l_child = None
        self.r_child = None
        self.data = data
        
def tree(key, r, i, j):
    k = r[i][j]
    if(k==0):
        return
    else:
        p=Node(key[k])
        p.l_child=tree(key,r,i,k-1)
        p.r_child=tree(key,r,k+1,j)
        return p

key = [" ","A","B","C","D","E"]
p=[0,4/15,5/15,1/15,3/15,2/15]
n = len(p)-1

a = [[0 for j in range(0,n+2)] for i in range(0,n+2)] # 2차원 배열 0으로 초기화
r = [[0 for j in range(0,n+2)] for i in range(0,n+2)]

def optsearchtree(n, p, a, r):
    for i in range(1,n+1):
        a[i][i-1]=0
        a[i][i]=p[i]
        r[i][i]=i
        r[i][i-1]=0
    a[n+1][n] = 0
    r[n+1][n] = 0
    for diagonal in range(1,n):
        for i in range(1,n-diagonal+1): # 대각선 위쪽만 채우기
            j = i+diagonal
            # min값 구하는 과정
            minvalue = float('inf')
            for k in range(i,j+1):
                if a[i][k-1]+a[k+1][j] < minvalue:
                    minvalue = a[i][k-1]+a[k+1][j]
                    mink = k
            # 시그마값 구하는 과정
            sigma = 0
            for l in range(i, j+1):
                sigma += p[l]
            # a값 설정
            a[i][j] = minvalue + sigma
            # r값 설정
            r[i][j] = mink
    return a,r
    
a,r = optsearchtree(n, p, a, r)
    
utility.printMatrixF(a)
print()
utility.printMatrix(r)
print()

root=tree(key,r,1,n)
utility.print_inOrder(root)
print()
utility.print_preOrder(root)

4. 동적계획법 - DNA 서열 맞춤

DNA는 이중 나선구조를 이루는데, 핵염기의 조합은 각각 2*2로 4개의 알파벳이 서로 조합된 형태입니다.

우리는 이 조합이 어떻게 되어있는지, 잘못 연결된 부분은 없는지 확인하고 싶습니다.

잘못 연결된 쌍을 찾아서, 점수를 부여한다면 보다 보기 좋게 만들 수 있지 않을까요?

이번 알고리즘은 불일치, 혹은 비어있는 DNA 쌍에 점수(비용)를 부여하는 알고리즘입니다.

먼저 알고리즘을 돌리기 전에, 최적 맞춤인지를 확인해야합니다.

확인이 되었다면, 알고리즘을 실제로 생각해봅시다!

이 알고리즘은, 분할정복방법으로도 만들 수 있고 동적계획법으로도 만들 수 있습니다.

하지만 분할정복방법의 경우 같은 함수를 여러번 불러내므로, 비효율적입니다.

따라서 동적계획법으로 푸는 것이 보다 효율적인 방법입니다.

아래는 동적계획법으로 푸는 방법입니다!

그리고 최종적으로 맞춤 서열을 출력하는 방법도 알아봅시다.

import utility
a=['A','A','C','A','G','T','A','C','C']
b=['T','A','C','G','T','T','C','A']

m=len(a)
n=len(b)
table=[[0 for j in range(0,n+1)] for i in range(0,m+1)]
minindex = [[ (0,0) for j in range(0,n+1)] for i in range(0,m+1)]

for j in range(n-1,-1,-1):
    table[m][j] =table[m][j+1]+2

for i in range(m-1,-1,-1):
    table[i][n] =table[i+1][n]+2

# 테이블 생성 구현
def opt(i,j):
    if i == m: # 오른쪽 끝, 아래쪽 끝에 값 넣기
        opt_val = 2*(n-j)
    elif j == n:
        opt_val = 2*(m-i)
    else: # 그 외의 경우 비용 구하기
        if a[i] == b[j]:
            penalty = 0
        else:
            penalty = 1
        opt_val = min(opt(i+1,j+1)+penalty, opt(i+1,j)+2, opt(i,j+1)+2)
    return opt_val

# 맨 아래 오른쪽부터 순서대로 채워나감
# 강의에서는 대각선으로 올라가라고 하셨지만, 오른쪽 아래부터 순서대로 올라가도 문제없음
for j in range(n-1,-1,-1):
    for i in range(m-1,-1,-1):
        table[i][j] = opt(i,j)


# minindex 테이블 구현 (m=10, n=8)
def minidx(i,j):
    if table[i][j] == table[i][j+1] + 2: # 오른쪽이랑 비교해서 2만큼 작아졌으면 
        minindex[i][j] = (i,j+1) # minindex는 자신의 오른쪽 좌표
        if j+1<n: # 만약 j+1이 n보다 작다면
            minidx(i,j+1) # 다음으로 진행
    elif table[i][j] == table[i+1][j] + 2: # 아래쪽이랑 비교해서 2만큼 작아졌으면 
        minindex[i][j] = (i+1,j) # minindex는 자신의 아래쪽 좌표
        if i+1<m: # 만약 i+1이 m보다 작다면
            minidx(i+1,j) # 다음으로 진행
    else: # 그게 아니라면 (틈이 아닌 0 혹은 1의 페널티 발생)
        minindex[i][j] = (i+1,j+1) # minindex는 자신의 오른쪽 아래 좌표
        if i+1<m and j+1<n: # i+1이 m보다 작고, j+1이 n보다 작다면
            minidx(i+1,j+1) # 다음으로 진행

minidx(0,0) # 0,0에서 시작


utility.printMatrix(table)
print()
x=0
y=0


while (x < m and y < n):
    tx, ty = x, y # x와 y는 0부터 시작
    print(minindex[x][y])
    (x,y)= minindex[x][y]
    if x == tx + 1 and y == ty+1:
        print(a[tx]," ",  b[ty])
    elif x == tx and y == ty+1:
        print(" - ", " ", b[ty])
    else:
        print(a[tx], " " , " -")