데이터과학 유망주의 매일 글쓰기 — 84일차
욕심많은 움직이는 프로그래밍(Greedy Dynamic Programming)
# Greedy, # Dynamic Programming
오늘 한일:
오늘은 그동안 많이 들어봐왔던 Dynamic Programming에 대해 배웠다. 동적인 프로그램이라고 하는데, 한마디로 문제를 나누어 푸는 분할정복(Divide and Conquer)에 중복된 계산값을 저장하고 재활용하는 Memoisation/Tabulation의 개념을 더한 것이었다. 이에 더해서 Greedy 방법론 이라는 것을 배웠는데, “지금 주어진 상황에 가장 최적의 솔루션"을 찾는 방법이다. 이 방법은 전체 숲보다는 나무를 보는 방법이어서, 전체적인 조건을 고려하지 않고 주어진 요구사항을 현재 상황에 한해서만 고려하는 문제해결 방법이다. 그렇다면 이 둘이 어떻게 다를까?
Dynamic Programming
재귀를 이용해 최적화하는 프로그래밍의 방법론을 말한다. 같은 입력값에 반복적으로 재귀를 통해 함수를 호출한다면, Dynamic Programming을 이용해 최적화할 수 있다. 이 개념은 Memoisation의 개념과 상당부문 일맥상통하는데, 문제를 부분 부분으로 나누고, 각 부분의 연산 결과를 저장해 활용하는 것이라 할 수 있다. 이렇게 하면 시간복잡도 면에서도 지수시간(O(n^n))을 조금 더 빠른 다항시간(O(n² + n + c))이나 선형시간(O(n))등 으로 줄일 수 있다.
예를 들어, 피보나치 수열(Fibonacci Numbers)에 대해 단순한 재귀 프로그램을 만든다고 하면, 지수 시간 복잡도를 갖게된다. 이 상황에서 피보나치 수열을 여러 부분으로 나누고, 각 부분의 계산을 저장해 활용하면 시간복잡도는 선형시간(O(n))으로 줄어들 것이다. 아래 프로그램은 Dynamic Programming을 활용하지 않고 재귀만을 사용해 피보나치 수열 문제를 해결한 방법을 보여준다.
# 피보나치 수열 예제
# 시간 측정을 위한 timeit 가져오기
import time
timer_list = []
# 단순 재귀 프로그램
def fib(n):
if n <= 2:
return 1
result = fib(n-1) + fib(n-2)
return result
# 함수 호출
n = int(input("input value: "))
for i in range(5):
print("-"*20)
print("{}th run".format(i+1))
# 프로그램 시간 측정을 위한 타이머 설정
start = time.time()
print("result: ",fib(n))
# 시간 측정
end = time.time()
print("This program took {} seconds".format(end-start))
timer_list.append(end-start)
if i == 4:
print("-"*20)
print("Average time is:", sum(timer_list)/len(timer_list))>>>
input value: 5
--------------------
1th run
result: 5
This program took 0.0001685619354248047 seconds
--------------------
2th run
result: 5
This program took 0.00016546249389648438 seconds
--------------------
3th run
result: 5
This program took 0.00016236305236816406 seconds
--------------------
4th run
result: 5
This program took 0.00015687942504882812 seconds
--------------------
5th run
result: 5
This program took 0.00019288063049316406 seconds
--------------------
Average time is: 0.00016922950744628905
그렇다면 Dynamic Programming을 활용한 예제는 어떨까? 아래는 재귀 대신, Tabulation이라는 Bottom-Up 방식의 저장개념을 활용한 프로그램이다.
# Dynamic Programming을 활용한 프로그램
# 프로그램 시간 측정을 위한 타이머 설정
timer_list = []
# Tabulation을 활용한 프로그램
def memo_fib(n):
memo = [0, 1]
for i in range(2, n+1):
memo.append(memo[i-1] + memo[i-2])
return memo[n]
# 함수 호출
n = int(input("input value: "))
for i in range(5):
print("-"*20)
print("{}th run".format(i+1))
# 프로그램 시간 측정을 위한 타이머 설정
start = time.time()
print("result: ",memo_fib(n))
# 시간 측정
end = time.time()
print("This program took {} seconds".format(end-start))
timer_list.append(end-start)
if i == 4:
print("-"*20)
print("Average time is:", sum(timer_list)/len(timer_list))>>> input value: 5
--------------------
1th run
result: 5
This program took 3.409385681152344e-05 seconds
--------------------
2th run
result: 5
This program took 2.9325485229492188e-05 seconds
--------------------
3th run
result: 5
This program took 3.123283386230469e-05 seconds
--------------------
4th run
result: 5
This program took 3.0040740966796875e-05 seconds
--------------------
5th run
result: 5
This program took 3.2901763916015625e-05 seconds
--------------------
Average time is: 3.151893615722656e-05
위 프로그램의 평균 실행 시간은 0.00003 정도로 0.0002 보다 약 10배 이상 빨라진 것을 볼 수 있다. 물론, 이 실행시간은 실행 할때마다 변동이 있어 항상 반드시 DP를 쓰지 않았을 때보다 빠르다고 할 수 없지만, 평균적으로 좀 더 빠른 것을 확인할 수 있었다. 이렇듯 DP의 개념을 활용하면 좀 더 빠른 프로그램을 만들 수 있다.
Greedy
Greedy란 가까운 곳에서 찾을 수 있는 가장 분명하고 즉각적인 이익을 얻을 수 있는 방법론을 말한다. 즉, 문제의 부분 부분에서 찾은 가장 최적의 값들이 전체 문제에서도 가장 최적의 값일 거라는 전제를 바탕으로한다.
예를 들어, 3가지 재료를 이용해 자루의 50Kg 중량을 맞추어야 하는 문제가 있다고하자. 아래 문제를 보면 바로 알 수 있듯이, 가장 빨리 만들어 낼 수 있는 조합은 B와 C를 더하는 것이다. 부피같은 다른 조건을 고려하지 않고 순수하게 50Kg를 만들어 낼 수 있는 조합중 가장 빠른 것은 B와 C만들 더하는 것이기 때문이다. 자연스럽게 부피는 100+120 = 220이 될 것이다. 만약 문제가 부피를 최소화하기를 요구했다면, 더 나은 해결책이 분명히 있을테지만 주어진 조건하에서 만들어낼 수 있는 가장 직관적이고 빠른 해결책은,단순히 50Kg를 만들어내는 가장 빠른 조합을 찾아내는 것이다.
앞으로 할일:
오늘은 프로그래밍의 꽃인 Dynamic Programming과 Greedy 방법론에 대해 알아보았다. Dynamic Programming은 중복된 하위 문제가 있는 문제를 중복된 계산 결과를 저장하여 효율적으로 해결하는 방법이다. Greedy는 결과를 저장하거나 안 할수 있지만, 주어진 상황에서 당장 가장 좋은 방법을 찾는 해결책으로써, 상황에 따라 프로그래밍이 DP에 비해 많이 달라질 수 있다. 결론은 DP는 중복되는 문제는 먼저 해결해 놓고, 쓸떼없는 반복적인 계산을 줄이는 방법이라면, Greedy는 문제 자체의 규모를 줄이는 방법에 더 가깝다고 볼 수 있다.
이렇게 보면 Greedy는 욕심이 많은 것 같다. 정말 단기적인 목표만 생각하고, 지금 당장 최적의 결과를 찾아야 할 때 사용하기 좋은 방법이라는 생각이 든다. 하지만, 그렇다고 해서 의미가 없는 방법은 아닐 것이다. 내가 당장 무언가를 찾아야 하는데, 가장 먼저 시도해 볼 수 있는 방법론일 수도 있다는 생각이 들었기 때문이다.
Dynamic Programming역시, 더 빠른 프로그래밍이 가능하다는 장점이 있지만, 계산 결과를 저장하기 위해 외부적인 메모리를 더 할당해야 하기 때문에 메모리 면에서 더 비효율적인 방법이다. 그러므로, 현업에서 메모리의 제한이 있을 경우, 조금 더 활용에 고민이 필요할 것 같다고 느꼈다. 하지만, 중복되는 문제를 미리 해결해 놓고 재활용한다는 면에서 전체 문제에서 연산량이 더 줄어드는 것이 사실이다.
결국, 그 어느 방법도 완벽한 것은 없다. 상황에 따라 어떤 것이 가장 적합한 도구인지를 아는 것이 가장 중요하다는 것을 다시 한번 깨달았다. 그러기 위해서는, 정말 많은 연습과 경험이 필요함을 느꼈다. 그래서 앞으로도 프로그래밍을 많이 해봐야겠다는 생각이들었다. 컴퓨터 관련 분야는 특히 머리로 이해하는 것보다도, 손으로 해 보면서 더 많은 연습을 통해 실력을 쌓을 수 있다는 것을 하면 할수록 더 절실히 깨닫게 된다.
오늘 드디어 마지막 수업이 끝났다. 이제 더 이상 정규적인 수업은 없을 것이다. 정말 큰 호기심과 많은 질문으로 괴롭혔음에도 성실히 답변해 주신 선생님께 감사하다. 내일은 마지막 자가 점검 시간이다. 유종의 미를 거둘 수 있도록 마지막까지 최선을 다 하고 싶다. 나를 포함 모든 이들이 그 동안 노력한 만큼, 내일도 큰 문제없이 난관을 넘어갈 수 있다고 믿는다.
Fighting!
참조:
(1) https://www.baeldung.com/cs/greedy-approach-vs-dynamic-programming
