230128 다이나믹 프로그래밍의 개념

# 잡소리

 

이놈의 굼뱅이같은 언어 파이썬은 작성하기는 편한데 속도가 느려터졌다.

뭐 백준 실버문제가지고 뭔 속도타령이냐 할 수도 있겠지만

실행속도를 빠르게 만들고 싶다는 욕구가 충만해진다.

 

그런의미에서 지금 타이밍에 배우는 

다이나믹 프로그램은 이런 욕망을 해갈해보라고 던져준 좋은 개념일 것이다.

백준의 기초 알고리즘 1/2을 듣고나서부터 본격적으로 뭔가 알고리즘스러운 것을 배우기 시작한 기분이 든다.

 

[1] 동적 계획법의 고안자인 벨만(Richard E. Bellman)은(벨만-포드 알고리즘의 그 벨만 맞다.) dynamic이라는 단어가 멋있어서(...) 선택했다고 한다. Programming이란 단어는 최적화 연구 분야에서 최적의 프로그램을 찾아낸다는 의미로 사용된다. - 프로그래밍 대회에서 배우는 알고리즘 문제해결전략(구종만 저) 1권 p.207
[2] 벨만이 다이나믹 프로그래밍에 대해 쓴 저서의 서문을 보면 연구소에서 펀딩을 받기에 좋은(...) 단어라서 선택했다고 나온다. 그는 당시 벨 연구소에 재직중이었다. 여기나 저기나 돈 받으려면 ㅠㅠ

출처 : http://https://namu.wiki/w/동적%20계획법, 종만북 1권

 

처음에 이 단어를 들으면서 든 생각은

이 양반이 얼마나 다이나믹하게 프로그래밍을 했길래 저런 이름을 붙였을까 하는 생각이 들었다.

내가 이걸 배우는 시점에서 이 개념은 확실히 시대의 한획을 그은 훌륭한 기술임에는 틀림없으나

확실히 간지나는 네이밍을 통해 연구비를 받으려는 의도가 다분하다는 것을 눈치챌 수있다.

 

돈이 몰려야 그 분야가 연구가 된다. 그래서 일론머스크가 대단한 샘이다.

헛소리는 이쯤에서 그만하고 본론으로 들어가자.

 

 

# Divide & Conquer (분할정복)

 

자료구조입문 수업에서 배운 퀵소트와 머지소트에서 배운

분할 정복(Divide and Conquer)라는 개념이 생각난다.

복잡하고 거대한 문제를, 작은 서브문제로 나눠서 문제를 해결하는 방식이다.

 

특정한 Pivot 원소를 정해서, 그보다 같거나 작은 서브어레이, 그보다 큰 서브어레이를 만든 후

다시 재귀적으로 그 어레이들을 다시 Quick Sort하며 쪼갠 뒤, 원소가 0~2개가 되는 밑바닥까지 Divide한 후

다시 합쳐나가며 Conquer해서 Divide and Conquer, 분할 정복이 된다.

 

Divide and Conquer는 문제를 분할해서 처리해도

그 분할된 문제들이 서로에게 영향을 끼치지 않는다.

가령 quicksort( [3,1,5,2,4] )를 분할 정복을 하기 위해

Pivot Element를 3을 기준으로 [1,2], [5,4]의 subarray를 만들었더라도

우리는 다시 quicksort( [1,2] ), quicksort( [5,4] )를 subproblem으로서 소팅해준 뒤 

[1,2] + [3] + [4,5]로 붙여주면 된다.

 

이 과정에서 quicksort( [1,2] ), quicksort( [5,4] )는 별개의 독립적인 문제이며 서로에게 영향을 끼치지 않는다.

즉 Subproblem의 중복, 겹치기, Overlapping이 발생하지 않는 것이 핵심이다.

 

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

 

하지만 다이나믹 프로그래밍은 그 궤가 조금 다르다.

아래의 글을 보자.

동적 계획법이 적용되기 위해서 문제가 가져야 하는 두 가지 핵심 속성이 있는데, 바로 최적의 하부 구조와 중복되는 하위 문제이다. 오버랩되지 않는 서브 문제에 최적의 솔루션을 결합해 문제를 해결할 수 있다면 그 전략을 대신 '분할과 정복'이라고 한다. 병합 분류와 빠른 분류가 동적 프로그래밍 문제로 분류되지 않는 이유이다. 최적 하위 구조란 주어진 최적화 문제에 대한 해결책을 하위 문제에 대한 최적 해결책의 조합에 의해 얻을 수 있다는 것을 의미한다. 그러한 최적의 하부 구조는 대개 재귀의 수단으로 설명된다. 예를 들어, 그래프 G=(V,E)를 보면, 꼭지점 u에서 꼭지점 v까지의 최단 경로 p는 최적의 하부 구조를 나타낸다. 즉, 이 최단 경로 p에서 중간 정점 w를 취한다. p가 정말로 최단 경로인 경우, 이는 실제로 해당 정점 사이의 최단 경로(알고리즘 소개에서 설명한 단순 절단 및 붙여넣기 인수에 의해)가 되도록 u에서 w까지, p2로 하위 경로 p1로 분할될 수 있다. 따라서 벨만-포드(Bellman–Ford) 알고리즘이나 플로이드-워셸(Floyd–Warshall) 알고리즘이 하는 재귀적인 방법으로 최단 경로를 찾기 위한 솔루션을 쉽게 공식화할 수 있다. 하위 문제가 중복되는 것은 하위 문제의 공간이 작아야 한다는 것을 의미하며, 즉 문제를 해결하는 모든 재귀 알고리즘은 새로운 하위 문제를 생성하는 것이 아니라 동일한 하위 문제를 반복해서 해결해야 한다.

출처 : http://wiki.hash.kr/index.php/동적_계획법

 

반면에 다이나믹 프로그램은 

Overlapping Subproblem, 풀어야 하는 작은 문제들을 해결하는 과정이 중복 될 때 사용하는 기법이다.

 

가령 피보나치 수열의 원소를 재귀적으로 구현하는 함수가 있고, 피보나치 수열의 100번째 항목을 구하고 싶을 때,

def fibo(n):
	if n==0 or n==1 :
    	return 1
    return fibo(n-2) + fibo(n-1)

fibo(100)을 구하기 위해서는 fibo(98) + fibo(99)를 구해야 한다.

그러므로 프로그램은 (1).첫번째 subproblem인 fibo(98)를 노가다를 하면서 구한 뒤,

(2).두번째 subproblem인 fibo(99)을 구하러 간다.

 

근데 fibo(99)를 구하기 위해 fibo(98) + fibo(97)을 구하는 과정에서

앞에서 구한 fibo(98)를 메모해두고 그냥 가져다 쓰면 될 것을

다시 고통스럽게 값을 찾기 위해 fibo(97), fibo(96)을 더 구하러 가는 참으로 찐빠스러운 상황이 발생한다.

 

그렇다. 앞에서 해놓은 것을 메모해 놨더라면..

사람의 머리통도 비슷하다.

어릴적에 뇌에 스며들듯이 배우거나 고통이나 쾌락으로 각인이 되어있지 않는한

뭐 배워봤자 이 방대한 정보쓰레기의 급류 속에서는 기껏해야 세 달이면 잊혀진다.

 

그러므로 메모하는 습관을 들이자.

지식을 습득할 당시의 상황.. 느낌... 감각...등을 나의 언어로 메모해놓으면

1년 2년 뒤에 까먹고 다시 맨땅에서 새로 출발을 하지 않아도 된다.

 

컴퓨터에게 앞에서 계산과정을 기록해놓고 차 후에 다시 사용하는

이 메모의 기법, Memoization이 사실 동적계획법의 본명이 되었어야 하는 그런 기법이다.

 

캐시메모리와 DRAM의 기술도 이러한 메모이제이션의 철학이 담긴 기술이다.

Tabulation도 이러한 메모이제이션의 바리에이션이다.

 

 

# 백준 9095번

 

 

마치 우리가 수능특강을 펴면, 개념을 배운 후 제일 먼저 나올만한 그런 문제이다.

정말 쉽다.

 

메모를 해둘 어레이를 할당해주고, 

굳이 계산이 필요없을 정도의 초기값을 설정한 후,

입력받은 문자까지 점화식스럽게 계산해나가면 된다.

 

중고등학교때 배운 점화식의 개념을

그냥 그대로 파이썬어로 번역 해버리면 된다.

 

iteration = int(input())

dp = [-1]*12
dp[0]=1
dp[1]=1
dp[2]=2
dp[3]=4

for i in range(4,12):
	dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

for i in range(iteration):
	num = int(input())
	print(dp[num])

 

 

# 백준 10844번

 

 

 

몇 번 절었던 문제이다.

근데 괜히 코드를 짧게 쓰려는 것보다

그냥, 문제에서 요구하는 상황에 맞춰서

경우를 다 적어주는 편이 더 오답률이 적다는 생각이 들었다.

 

가령, 처음의 시도에서, 나는 n단계에서  0으로 끝나는 수들. 9로 끝나는 수들, 그리고 나머지 

이렇게 세개의 그룹으로 나눈 후, 0,9로 끝나는 수가 나올 수 있는 경우인 n-1단계의 경우를 빼주는게

최적화된, 빠른 그런 코드이기에 그런식으로 짜는게 맞다고 생각이 들었지만,

 

그냥 뒷자리가 0으로 끝나는거, 1로 끝나는거, .... , 9로 끝나는거 다 만들어주고

나의 직관에 맞게, 아래와 같이 그냥 적당히 분할된 경우를 처리하는게

코드의 효율은 떨어질 지언정 이해하기 편리했다.

 

 

#  10844


num = int(input())
if num==1:
	print(9)
	exit()

counter = [0]+[1]*9

# 최초의 뒷자리 카운터는 1,2,3,4,5,6,7,8,9를 반영해
#[0,1,1,1,1,1,1,1,1,1]이 된다. 또한 이들은 sum이 곧바로 dp[1]이 된다.

#수의 뒤에 새 수를 붙여나가며 2부터 num까지 찾아준다.
for i in range(2,num+1):
	next_counter=[0]*10
	next_counter[0] = counter[1]
	next_counter[9] = counter[8]
	for j in range(1,8+1):
		next_counter[j] = counter[j-1] + counter[j+1]
	counter = next_counter[:]

print(sum(counter)%1000000000)

 

괜시리 짧게, 한줄로 코딩하는 게 절대 멋진게 아니다.

시스템의 최적화를 수행하는 극소수의 고인물 프로그래머들이 아닌 이상..

 

오히려 천천히 가도 모두가 이해할 수 있고 직관적으로 이해가 되는 코드를 짜야한다.

컴공과를 나온 학생들은 소프트웨어 공학같은 수업을 들으면서

이런식으로 장기적으로 유지보수하기 좋은 코드를 짜는 방법을 배우지 않았을까 싶다.

 

다른나라의 프랑스에서 온 하급 영어스킬 보유자의 외국인에게 영어로 작업을 시키는 것이나

컴퓨터에게 파이썬어로 작업을 시키는 것이나 비슷비슷하다

영어 스킬이 부족하면 괜히 비유적 표현이나 숙어를 사용하는 것보다 

기초적인 단어들로 말해주는게 훨씬 전달력이 높다.

 

언어는 사용자의 수가 언어의 생존을 결정한다.

사용자의 수가 적을 수록 언어는 죽어간다.

대중적이지 않고, 효율적이지 않고, 불편하다면 사용자 수가 적어지고 언어는 사라지게 된다.

 

언리얼 엔진을 사용하지 않고 자체적인 엔진을 사용하는 개발사나

솔리디티를 사용하지 않는 다른 블록체인 프로젝트를 보면서 느낀 생각이다.

기술력이 아무리 뛰어나도. 압도적인 성능이나 커뮤니티를 가지지 않은 이상

업계 표준의 헤게모니를 무너뜨릴 수는 없다.

 

# 잡설

 

(1)이런식으로 문제를 풀 수 있다니.

컴퓨터는 진짜 겁나게 빠르다.

컴퓨터구조론을 배울 때, 배운 기억과 내 생각을 섞어서 이야기 해보자면

요즘 나오는 CPU는 1GHz 이상의 클럭을 가진다.

즉 1ns마다 0V와 5V, 혹은 0V와 3V사이의 전압을 오가면서

Falling Edge, 혹은 Rising Edge를 만들며,

상태머신은 이 엣지를 기준으로 하여 상태를 계속해서 바꿔 나간다.

 

대개 ALU에서 연산이 이루어지는 과정은 5~10클락이 소모된다. 대충 10ns라고 하자.

그리고 이정도의 연산은 하나의 레지스터 안에서 처리가 가능하므로 뭐 메모리 참조같은 것도 없을 것이고.

얼버무려서 1초동안 천만번의 덧셈연산이 가능하다.

 

 

한 때, 나는 수능시험을 보면서 수포자들을 조롱하는 시대를 겪은 적이 있다.

이런식으로 노가다를 하면서 일일히 수많은 노가다를 하는 방식은 비효율적이라고 가스라이팅을 당해왔지만..

 

이제는 시대가 조금 달라졌다.

컴퓨터가 1초에 천만번정도는 후다닥 계산해주는데 걍 컴퓨터한테 시키면 안됨?하고

노가다를 시킬 수도 있는 법이다.

 

문과들 중에서도 소프트복전을 통해 날개를 펼친 양반들이 꽤 많다고 들었다.

수포자들 중에서도 시대를 잘못 만나서 이러한 노가다 해결능력이 빛을 보지 못한 경우도 많겠지.. 아마?

 

 

(2)

 

 

어렸을적에 보았던 머선 어린이용 과학잡지에..

여러개의 3kg과 5kg의 무슨 동상으로 10kg이상 10000kg이하의 모든 무게를 만들 수 있다면서

일본에서 보던 고양이 동상이 그려진 문제가 있었다.

초등학생 시절이라 너무 오래되어서 가물가물한데.. 고양이 그림이 섬뜩하게 생겨서 

일부 수학자들이 이런식의 증명이 과연 증명인가 하는 그런 내용이었던 것으로 기억난다. 

이제보니 다이나믹 프로그래밍 이야기더라. 기십년이 지나서도 기억이 나는게 신기하다.

 

 

(3) 에브리타임에 올라온 글에서도 이런 문제 해결에 대해

그냥 컴퓨터와 확률의 힘으로 접근하는 사람들도 종종보았다.

 

가위바위보를 10번 연속으로 이길 수 있는 방법은 1/1024라는 명제를 증명하기 위해

이기고, 지고, 비기고의 확률이 각각 1/3일 때

'지면 끝내고, 이기거나 비기면 계속 진행하시오'를 10만번 수행해서

성공횟수/실패횟수로 계산하는 것이다.

 

물론 비긴다는 요소를 무시하고 (1/2)^10으로 해버리면 간단히 풀리는 문제이기에

사람들이 한심하다는 듯이 반응했지만..

오히려 이러한 문제해결 방식이 더 직관적이고 간단할 수도 있다.

비록 코드의 효율은 훨씬 떨어겠지만

 

언젠가 완벽하게 확률을 계산하기 힘든 상황이 왔을 때

진가를 발휘할 그런 접근법인 셈이다.