[sw정글 4주차] DP개념이랑 코드까지 완벽정리 해버림(클릭)
카테고리: swjungle survive
📚SW정글 4.1주차
카이스트에 놀러가서 전산학부 건물을 보고왔다.School of Computing 건물을 들락날락거리는 (시험기간의초췌한)학생들을 보며, 나는 저들보다 컴퓨터 관련 어떤 부분을 더 잘할 수 있을까? 라고 생각해보게 되는 계기가 되었다. 카이스트 전공생들보다 CS를 더 잘 이해한다(?)는 단기간에 이루기 힘든 목표이겠지만, 컴퓨터의 어느 특정 부분을 더 잘할 수 있는건 꽤 빠른시간에 가능한 문제이지 않을까 싶다.
⁉️DP란 무엇인가
DP란 무엇인가? 대학교 4학년 때, 문준(a.k.a 논문기계) 교수님의 최적화 수업을 청강으로 들었던 적 있다. 그곳에서는 Linear programming이라는 용어를 사용하였다. 그리고 Dynamic programming또한 같은 뜻으로 사용된다. 최적화도 같은 뜻이다. 따라서…
DP = LP = 최적화 인 것이다.
그러면 왜 Dynamic Programming이라고 지었는가? 벨만아저씨가 연구비 따낼려고 이름 멋있게 지으려고 Dynamic이라는 말을 붙였다고 한다. 이런한 연유로 우리가 다이나믹-프로그래밍 이라는 용어에 속아 문제를 너무 어렵게 생각하거나, 귀중한 시간을 내어 구글링에 이러한 역사를 검색해 보게 되는 것이다.
앞으로 설명할 DP는, 그냥, 알고리즘을 좀 더 최적화 시킨다 라고 생각하면 될 것이다. 아울러, 어려운 용어를 줄이기 위하여 “최적화 했다” 라고 표현할 것이다.
🧐DP의 사용
그렇다면 이러한 최적화 문제는 어디에 사용될까? 바로
가방채우기 (Knapsack problem)
외판원순환문제 (Traveling Sales man(TSP-problem))
위와 같은 문제들이다. 찾아보면 알겠지만, 그냥 가방에 이것저것 물품을 담아내거나, 여행경로를 찾아다니는 문제이다. 간단해 보이지만, 위의 문제들은 NP-hard problem이라고 불리운다. 가방에 넣어야 하는 물건들의 개수가 많아지거나, 여행할 수 있는 도시들이 조금만 많아져도 확인해야 하는 가지수가 너무너무너무 많아서 일일히 확인할 수 없는 것이다. 슈퍼컴퓨터를 돌려도 연산량이 너무 많아 확인할 수 없다.
따라서, 컴퓨터로도 정확한 답을 낼 수 없다.(최소값을 찾을 수 없다) 그럼에도 불구하고 조금 더 최적에 가까운 답을 빠르게 찾아내는 방법에 관한 연구들이 진행되고 있고, 그것이 바로 최적화분야에서 연구되고 있는 문제들인것이다. 그렇다면 우리가 코딩테스트 및 최적화(DP)라는 이름으로 불리는 CS의 기초는 도대체 무엇일까?
N이 꽤나 작은 문제들에 대해, 메모리에 자주계산되는 부분들을 저장해 두는 것이다. 따라서 우리는 아주 작은 N들에 대해서, 컴퓨터의 계산성능이 빨라지는 부분에 대한 최적화를 배우는 것이고, 이와같은 방법에 Memoization과 같은 해의 일정 부분을 메모리에 저장해 두는 방식들을 사용하는 것이다
(청강할 땐 몰랐다, 기말고사 과제가 TSP관련논문 써오기 일줄은…)
👋DP의 세가지 대표문제
그렇다면 CS의 기초공부를 하며 만나게 되는 최적화의 대표적인 3가지 문제를 알아보도록 하겠다. 백준, 프로그래머스와 같은 문제들 역시, 이러한 최적화문제들의 일부 변형된 형식들이기 때문에 이러한 대표유형들을 알아두면 좋을 것 같다. 알고리즘공부의 근-본서적 CLRS에서도 고르고 골라서 소개한 3가지 유형들이니 3가지 모두 설명하고 넘어가도록 하겠다.
- 통나무자르기🪵
- 통나무 길이에 대한 가격표가 있을 때, 다양한 방법으로 통나무를 자르고, 그 이윤을 최대화 시키는 문제이다.
- 행렬의 곱❌
- 행렬들이 연속으로 이루어져 있을 때, 행렬 순서대로 계산하는 것 보다, 괄호로 묶어 연산순서르 바꾸어 주면 성능이 훠~~얼씬 좋아질 수 있다. 이에대해 어떻게 괄호로 묶을지에 대한 문제이다.
- 조립공장 와리가리🏭
- 공장에서 A라인에서 조립을 하다가, B라인으로 넘어갔다가, A라인으로 와리가리 하면서 공정 과정을 거치는 것이다. 생산라인을 넘어갈 때에도 비용이 들고, 한 라인에서 조립을 해도 비용이 든다. 최소비용으로 공정라인을 와리가리 하면서 빠르게 물건을 만드는 방법을 구하는 문제이다.
🚀DP를 풀어내는 방법
위의 세문제를 풀어내며, 최적화 문제를 풀어내는 방법들을 코드와 함께 설명 해 나가도록 하겠다.
🚀Bottom-up 방식
상향식 접근방식이다. 상향(위쪽으로향함)이므로 Bottom-up방식으로 불리운다.
def pibo(n):
if n >= 2:
return pibo(n-2) + pibo(n-1)
else:
return n누구나 아는 피보나치 문제이다. Bottom-up approach, 즉 상향식으로 풀면 어떻게 될까?
def fib_Tab(n):
dp_Tab = [0]*(n+1)
dp_Tab[0], dp_Tab[1] = 1, 1
for i in range(2, n+1):
dp_Tab[i] = dp_Tab[i-1] + dp_Tab[i-2]
return dp_Tab[n]위와 같은 코드가 나오게 된다. 기존과는 다르게 중간 값들이 다 저장이 되어있기 떄문에, 끝도없는 재귀를 타고내려가지 않아도 된다. 그렇다. 우리가 하게될 최적화 문제들은 재귀의 구조를 띄고있다. 하지만 다른점이 있다. 반복되는 부분은 계산하지 않도록 하는 것이다. 그렇다면 재귀함수를 사용하는 문제들은 필요없는 존재들인가? 분할정복은 어디에 쓰게되는 것인가!
그렇다.
분할정복 및 기타 재귀를 이용한 문제풀이들은 재귀적으로 풀어내는 각 문제들이 새로운 경우 사용된다.
이와 반대로, 재귀적으로 풀어내는 각 부분문제들이 새롭지 않은경우 최적화를 시킬 수 있는 것이고, 이에 피보나치의 fib(2), fib(1)처럼 수십 수백번 호출되는 친구들 및 중간 과정들을 새롭지 않은 부분문제로 고려하고 최적화를 시켜서 풀어내는 것이다.
🚀Top-Down 방식
def fib_Memo(n):
dp_Memo = [0]*(n+1)
dp_Memo[0] = 1
dp_Memo[1] = 1
def fibM(n):
if dp_Memo[n] == 0:
dp_Memo[n] = fib_Memo(n-1) + fib_Memo(n-2)
return dp_Memo[n]
return fibM(n)위의 코드는 Top-down approach, 즉, 하향식 방법으로 풀어낸 코드이다. 뭔가 많이 복잡해보이지 않는가? 필자가 코드를 못짰지 않을까 하는 의심도 있겠지만 CLRS에서 추천하는 sudocode를 파이썬으로 바꾼 것이다.
참고로,
Top-Down 방식은 모든 면에서 좋지 않다
일단 함수를 여러번 호출해야한다. Bottom-up 으로 풀리는 문제가 Top-down으로는 (시간초과로)풀리지 않을때도 있다. Bottom-up 방식과는 다르게, 함수를 여러번 호출해야 하므로 메모리와 시간 측면에서 좋지 않다. 그럼에도 불구하고 Top-down 방식이 좋은점이 있지 않을까? 굳이 찾아본 내용으로는 함수의 밑바닥의 모양을 알지 않아도 되므로 조금 더 쉽게 코드를 짤 수 있다정도인 것 같다. 실제로, 재귀의 구조를 알아낸 다음 바로 적용시키기에는 하향식 방식풀이가 코드적용이 좀 더 쉽다. (하지만 디버깅도 어렵고… 속도도… call-stack도 엄청나게…)
(나의 뿌리는 EE에 있음을 기억하기 위해 한컷 더😁)
🚀최적화문제들과 각 유형
🚀1번유형: 🪵나무자르기(Rod-cutting)
아래와 같은 방식이다. 값이 들어갈 행렬 전체를 만들어 준 이후, 최대값을 비교해 주는 방식이다.
r = [0] * (n+1)
q = max(q, price[i] + r[j-i])
r[j] = q
answer = r[n]나무자르기 상향식 풀이(전체코드)
INT_MIN = -32767
def bottom_up_rod(price, n):
r = [0] * (n+1)
for j in range(1,n+1):
q = INT_MIN
for i in range(1, j+1):
q = max(q, price[i] + r[j-i])
r[j] = q
return r[n]
price = [0,2,4,7,8]
print(bottom_up_rod(price, 4))나무자르기 하향식 풀이(전체코드)
INT_MIN = -32767
def memo_cut_rod(price, n):
def memo_cut_rod_aux(p,n,r):
if r[n] >= 0:
return r[n]
if n == 0:
q = 0
else:
q = INT_MIN
for i in range(1,n+1):
q = max(q,p[i] + memo_cut_rod_aux(p,n-i,r))
r[n] = q
return q
#end of the functino here
#start from here
r = [0 for x in range(n+1)]
for i in range(0, n+1):
r[i] = INT_MIN
return memo_cut_rod_aux(price,n,r)
price = [0,2,4,7,8]
print(memo_cut_rod(price, 4))🚀2번유형: ❌행렬의 곱셈(Matrix-multiplication-chain)
아래와 같은 방식이다. ABCDEFG까지 있을 때, 일정 범위의 최솟값은 다른 최솟값의 곱으로 표현될 수 있는 성질을 이용한 것이다. min(DEF)를 구할땐, min(DE)와 min(EF)를 이용하는 것이고, min(CDEF)를 구할 땐, min(DEF)를 다시 이용할 수 있는 방식이다.
dp[j][x] = min(dp[j][x], dp[j][k] + dp[k + 1][x] + s[j][0] * s[k][1] * s[x][1])그렇다면 해가 어떻게 될까?
min(CDEF)를 구할 때, min(DEF)를 이용하면 마법처럼 해결될까? 아니다. O(n)의 시간이 걸리는 for루프를 한번 더 돌면서, C*DEF, CD*EF, CDE*F모두를 검사해야한다. 따라서 3번을 빙글빙글 도니까, 총 소요시간은 Ω(n3)이 걸린다. 아울러, 메모리 사용량은 Θ(n2)이나 걸린다.
으악 n세제곱!!! 전혀줄어들지 않았는데요?
아니다. 원래는 모든 n에 대하여 P(K)P(N-K)n에 해당하는 경우의 수를 세어주어야 하며, 무려 Ω(2n)의 시간이 걸린다. 메모리를 사용하여 상당한 시간을 아꼈다고 볼 수 있다.
백준11049번-행렬의곱셈문제와 아래의 상향식, 하향식 풀이를 살펴보자
행렬체인곱셈 상향식 풀이(전체코드)
import sys
input = sys.stdin.readline
n = int(input())
s = [list(map(int, input().split())) for i in range(n)]
dp = [[0] * n for i in range(n)]
for i in range(1, n):
for j in range(n - i):
x = j + i
dp[j][x] = 2 ** 32
for k in range(j, x):
dp[j][x] = min(dp[j][x], dp[j][k] + dp[k + 1][x] + s[j][0] * s[k][1] * s[x][1])
print(dp[0][n - 1])행렬체인곱셈 하향식 풀이(전체코드)
import sys
input = sys.stdin.readline
N = int(input())
input_matrix = []
temp = list(map(int, input().split()))
input_matrix.append([1, temp[0]])
input_matrix.append(temp)
DP = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(N-1):
input_matrix.append(list(map(int, input().split())))
def matrix_min(a: int, b: int) -> int:
"""Matmul_min calculatior"""
if a == b:
return 0
elif DP[a][b] != 0:
return DP[a][b]
else:
min_val = sys.maxsize
for i in range(a, b):
min_candidate = matrix_min(
a, i) + matrix_min(i+1, b) + input_matrix[a-1][1]*input_matrix[i][1]*input_matrix[b][1]
min_val = min(min_val, min_candidate)
DP[a][b] = min_val
return min_val
print(matrix_min(1, N))🚀3번유형: 🏭공장 와리가리 문제(Assembly line Scheduling)
f1[i] = min(f1[i-1], f2[i-1] + t2[i-1]) + a[i]
f2[i] = min(f2[i-1], f1[i-1] + t1[i-1]) + b[i]이번에는 서로 다른 두 테이블을 만드는 방식이다. 나무자르기에서는 1차원 테이블을 만들었고, 행렬곱셈 문제에서는 2차원 테이블을 만듬으로써 문제를 해결하였다. 그렇다 감이 오는가?
공장와리가리문제
def f(a, b, n, e1, e2, x1, x2, t1, t2):
f1 = [0 for x in range(n)]
f2 = [0 for x in range(n)]
f1[0] = e1 + a[0]
f2[0] = e2 + b[0]
for i in range(1, n):
f1[i] = min(f1[i-1], f2[i-1] + t2[i-1]) + a[i]
f2[i] = min(f2[i-1], f1[i-1] + t1[i-1]) + b[i]
return min(f1[n-1]+x1, f2[n-1]+x2)최적화문제(DP)의 핵심 요소는, 테이블을 만드는 것이다
배열이나 테이블에 저장하여, 했던 계산을 다시하지 않도록, 다시 참조할 수 있도록 테이블에 저장하는것이 최적화 문제의 핵심이다. 문제를 Brute-force방식으로 풀어야 할 때, O(n2), O(n3)을 넘어서… O(2n), O(4n)과 같이 지수적으로 증가한다면, 최적화문제일 가능성을 강력히 의심 해 보고, 테이블을 그려서 풀 수 있는 문제인지 보면 될 것이다.
최적화문제인지 확인하기 위해서는 다음과 같은 조건들을 확인해야 한다.
- 최적해 구조의 특징을 가지고 있는지 확인하기
- 최적해 구조를 가지고 있기위한 독립성을 가지고 있는지
위와같은 조건들을 만족한다면, 최적화 시킬수 있는 문제임을 떠올리고 테이블을 그린다. 그 후, 어떤 값들을 테이블에 어떻게 넣을지를 떠올리며 문제를 푸는것이 좋을 것 같다.
코드와 함께알아보는 백준DP문제(왜 그렇게 짜면 안되는가!)
백준12865번문제(knapsack problem)과 같은 경우 2차원 배열을 만들어서 푼다.
백준9084번문제(동전문제)와 같은 경우에도 2차원 배열을 사용해서 푼다. 하지만 이 문제는 1차원배열로 바꾸어서 풀 수 도 있다.
어떤 차이이일까? 동전문제와 같은 경우 동전의 중복사용이 가능하다. 즉 동전을 반복해서 사용할 수 있기 때문에, 자기 자신이 만들었던 배열과 비교를 해도 괜찮지만, 배낭문제와같은경우 1차원배열로 풀 경우, 같은 물건을 여러개 넣는것과 같은 효과가 생긴다.
따라서, 다음은 배낭문제를 1차원으로 풀어보고, 디버깅을 해보면서 알게된 간단한 사실이다.
중복을 허용하지 않는 문제들에 대해서, n차원배열을 만들어서 참조하여야 한다.
배열의 형태가 행렬곱셈순서 문제처럼 n2/2 의 형태일 수도 있고,
백준9084번 동전문제,백준11053번 LIS문제처럼 1차원 테이블로 저장 해줄 수도 있고,
피보나치 문제의 경우,
arr = deque([1, 1], maxlen=3)
for _ in range(n - 2):
arr.append(arr[1] + arr.popleft())(0.2차원…?) 단 2칸의 배열로만 표현할수도 있으며,
백준12865번_배낭문제, 백준9251번_LCS문제처럼 일반적인 2차원 배열로 풀 수도 있으며,
Assembly Line Scheduling(a.k.a 공장라인 와리가리 문제)에서는 서로 다른 두 배열을 참조해가며 문제를 풀어나갔다.
🤔결론
DP, LP등 다양한 이름으로 불리우는 최적화문제는 최적부분구조(Optimal substructure)를 가지고 있는지의 여부가 중요하다. 이는 결국, 풀고자하는 문제가 반복되며, 독립성을 가져야 한다는 것이다. 일단 이와같은 사실을 통해 최적화문제임을 알았다면, 결국 최적부분구조를 잘 표현 해 줄 수있는 테이블을 만들어서 문제를 풀어나가는 것이다.
DP문제! 테이블!
일단 테이블을 그렸는가? 나무자르기문제처럼 1차원 테이블일수도, 행렬체인곱셈문제처럼 2차원 테이블일수도, 공장와리가리문제처럼 서로다른 두 배열을 참조해 나가며 풀 수도 있다. 해당되는 대표유형의 문제들을 풀어나가며 최적화문제에 대해 감을 잡아나가면 좋을 것 같다.
수십년전의 어느 교수가 연구비를 따내기 위해 만든 Dynamic Programming 이라는 있어블한 용어에 현혹되어 괜시리 어려움을 느끼지 않았으면 좋겠다.
(image: 대전의 맑은 하늘)
😵배우면서 깨달은 내용을 정리해 보았습니다. 틀린 것 같은 개념을 아래 댓글에 달아주시면 감사합니다😵
🌜 Thank you for reading it. Please leave your comments below😄
댓글 남기기