동적계획법
자 그러면은 우리가 이제 벨만 최적성 방정식을 봤는데 그럼 이제 문제가 뭐냐면 우리가 정책을 찾아야 되거든요.
무슨 행동이 그래서 최적이냐
이걸 찾아야죠.
결국 정책이라는 거는 내가 어떤 상황에 어떤 행동을 하느냐니까 그걸 찾아야 되는데 그럼 어떻게 찾느냐.
결국에는 우리 벨만 최적성 방정식 안에 답이 있습니다.
내가 지금 어떤 행동이 최적인지를 알려면 지금 현재 상태는 주어져 있는 거니까 여러 가지 A들 중에 내가 최적인 걸 찾아야 되고 그걸 찾으려면 내가 그 다음 상황에 최적 행동을 하는 거를 전제돼 있으니까 다음 상황에 내가 무슨 행동을 할지를 찾아야겠죠.
그러면 다음 상황이 되면 똑같습니다.
다음 상황에서 최적 행동을 하려면 그 다음 상황에 최적 행동이 뭔지 알아야겠죠.
예를 들어서 여러분이 인생 계획을 완벽하게 세우시려면 내가 죽기 전에 뭘 해야 최적일지를 계산을 하고 그 다음 죽기 전에 이걸 하는 게 최적이니까 그 전에는 이걸 하는 게 최적이군.
그 전에는 이걸 최적하는 거.
근데 그걸 그렇게 해야 최적화가 된단 말이에요.
여러분 그게 가능합니까?
그래서 인생이 최적화가 안 되는 거죠.
우리가 그 문제가 해결이 안 되니까.
근데 이제 우리가 이제 다른 좀 간단한 문제들은 그렇게 최적화를 할 수 있습니다.
그래서 보통 강화학습에서 많이 사용하는 방법이 동적 계획법이라는 건데요.
동적 계획법은 앞에 우리가 계속 벨만 방정식을 봤는데 벨만 방정식을 만든 벨만이 만든 알고리즘입니다.
근데 이름이 왜 동적 계획법이냐면 별 뜻은 없고 벨만이 정부의 연구비를 따야 되는데 벨만 방정식 푸는 방법 이따위로 이름을 지어서야 연구비를 따기가 너무 힘들어요.
그래서 멋있는 이름이 필요했습니다.
그래서 이렇게 잘 생각을 하다가 뭔가 다이나믹도 멋있고 프로그래밍도 멋있으니까 다이나믹 프로그래밍 하면 뭔가 멋있어서 어차피 뭐 여러분 이거 심사하는 사람이 이거 보고 이해했겠습니까?
뭔가 좋은 건가 보다
이러고 주는데.
요즘 또 약간 그런 거 있잖아요.
우리가 블록체인이라든가 멘타버스 이런 거 한참 유행했었는데 솔직히 약간 높으신 분들이 뭔지 아시겠어요?
뭔가 좋은 건가 보다 이름도 멋있고.
그냥 가상현실이라도 되는데 메타버스라고 꼭 하잖아요.
왜냐하면 가상현실이라면 좀 별로 없어 보이는데 멘타버스 이런 거 멋있어 보인단 말이에요.
이름을 멋있게 짓는 것도 중요합니다.
사실 실체는 별거 아닌데 다이나믹 프로그래밍은 뭐냐면 되게 우리 다 아는 거예요.
큰 문제를 작은 문제로 쪼갭니다.
그래서 큰 문제를 작은 문제로 쪼개서 작은 문제들을 풀어요.
작은 문제를 푼 다음에 이거를 다시 합치면 이게 전체 문제의 프리가 된다라는 겁니다.
그게 뭐 대단한 거야 라고 생각하실 수 있는데 사실 원래 대가들의 해결책은 그렇게 복잡하지 않습니다.
그래서 벨만이 생각하기에 어차피 이 문제를 풀려면 이거가 더 작은 문제죠.
근데 내가 어떤 행동을 하면 반드시 다음 상태가 고정이 된 게 아니라 내가 최적 행동을 했어요.
그런데 S'이 여러 가지가 있을 수 있다면 1, 2, 3. 이때 최적 행동이 있을 거고, 이때도 다른 최적 행동이 있을 거고, 이때도 다른 최적 행동이 있을 텐데 1, 2, 3가 있겠죠.
그럼 이걸 풀고 이걸 풀고 이걸 푼 다음에 그걸 다 썸이니까 합쳐주면 된다.
그래서 그런 생각입니다.
그래서 동적계획법은 굉장히 간단한 문제.
동적계획법은 벨만 방정식을 풀 때뿐만 아니라 다른 문제도 적용할 수 있습니다.
그래서 굉장히 약간 보편적인 해결책인데 이 두 가지 다음에 두 가지 속성을 만족을 하면은 이 다음에 두 가지 속성을 만족을 하면은 동적계획법을 다 적용할 수 있습니다.
형태를 좀 바꾸고 있지만.
두 가지 속성이 뭐냐?
먼저 최적의 부분 구조를 가지고 있어야 된다. 라는 건데 최적 부분 구조라는 건 뭐냐면 우리가 큰 문제가 있고 작은 문제가 있어요.
그러면 큰 문제에서 최적인 거는 작은 문제의 최적을 다 더하면 된다.
이런 얘기입니다.
그래서 예를 들면 이런 문제에 얘가 우리가 길찾기 같은 경우를 생각을 해보실 수가 있는데요.
우리가 예를 들면 고현터미널에서 여기 강의장까지 와야 돼요.
여기 이름 뭐죠?
DT강의장.
그러면 예를 들면 중간에 어디를 거쳐야 되잖아요.
어디를 거친다고 할까요?
제가 거제도 지리를 잘 모르는데 어디 사거리를 지나야 된다고 합시다.
A사거리.
여기는 반드시 지나야 돼요.
그러면 여기 고현터미널에서 A사거리까지 가는 최단거리하고 A사거리에서 DT강의장까지 가는 최단거리를 합치면 전체의 최단거리가 되겠죠.
길찾기 문제에서도 우리가 여기를 거쳐서 여기까지 오는 거는 반드시 해야 된다고 하면 전체가 최단이 되려면 여기도 최단이어야 되고 여기도 최단이어야 됩니다.
최단거리의 항상 부분은 최단이어야 돼요.
그렇겠죠.
왜냐하면 여기서 돌면 당연히 거리가 늘어나죠.
그래서 이런 특성을 가지는 문제를 최적 부분 구조를 가진다.
이렇게 합니다.
안 그런 문제도 있습니까?
이렇게 생각하실 수도 있는데 안 그런 문제도 가끔 있어요.
예를 들면 우리가 살다 보면 가끔 손해를 봐야 될 때도 있거든요.
그래서 그런 얘기 있잖아요.
줄 건 줘.
이런 말 있잖아요.
줄 건 줘.
이건 뭐야?
내가 좀 손해를 보는 부분도 있어야 이만큼 손해를 보고 이만큼 이익을 봐서 정체적으로 보면 다 이익이다
이런 거죠.
여기서도 손해 안 보고 여기서 이익만 보는 그런 건 없다는 얘기죠.
그런 것은 최적 부분 구조가 아니죠.
내가 안 주는 거는 없습니다.
그런 문제는 동첩계획법이 적용이 안 된다.
그래서 그 다음에 최적 부분 구조만 가지고 있으면 그러면 이 경우에는 분할 정복이라고 하는데 DIVIDE AND CONCORE 라고 합니다.
만약에 어떤 문제가 최적 부분 구조만 가지고 있으면 그때는 동첩계획법이 아니라 분할 정복이라고 하는데 그냥 문제를 쪼개서 풀기만 하면 돼요.
그런데 동첩계획법의 특별한 점은 뭐냐면 한 가지가 더 필요해요.
뭐냐면 중복되는 부분 문제라는 게 더 필요합니다.
그래서 그냥 분할 정복하고 달라요.
문제를 쪼개서 풀기만 하는 거랑 차이가 생깁니다.
그래야 동첩계획법이라고 하는데 중복되는 부분 문제는 뭐냐면 우리가 부분 문제를 푸는데 비슷한 부분 문제가 자꾸 나와요.
한번 푸는 과정에서 계속 나옵니다.
여러 번 반복되는 것을 특성 이 있어야 그때 동첩계획법이 있습니다.
그래서 그냥 쪼개서 풀면 끝나는 게 아니고 쪼개서 푸는데 이 문제 아까 풀었는데 또 나오네
이런 경우가 생겨야 돼요.
그래서 우리가 왜 벨만 방능식을 동첩계획법으로 풀어야 되느냐
그러면은 이제 앞에서 보셨듯이 우리가 어떤 S가 있고 예를 들면 S1, S2, S3, 상태가 세 가지가 있다고 합시다.
그래서 S1에서는 S2, S3로 가고 S3에서도 서로 왔다 갔다 할 수 있다고 생각해 보죠.
그러면은 S3에서 최선의 행동을 하고 S2에서 최선의 행동을 하는 게 뭔지를 알아야 S1에서 최선의 행동을 찾겠죠.
그래서 최적 부분 구조를 가집니다.
이게 S1에서 최적 행동은 S3가 부분이고 S2도 부분이잖아요.
그래서 S1에서 최적 행동을 찾으려면 얘네 부분에 최적을 찾아야 되니까 최적 부분 구조에 특성을 가져요.
근데 문제가 그러면 S1을 풀려면 S3를 알아야 돼요.
S3에서 최적 행동을 알아야 되는데 이번에는 S3가 전체입니다.
이게 전체라고 하면은 S3에서 최적 행동은 각각 어떤 부분을 가지냐면 S1에서 최적 행동과 S2에서 최적 행동을 알아야 S2에서 최적 행동을 알 수 있어요.
그러면 S2의 해법이 S1을 풀 때도 필요한데 S3에 대해서 풀 때도 필요하단 말이에요.
그러면 S2 먼저 풀자 라고 하면은 S2를 푸는데 또 S1하고 S3의 해법이 필요합니다.
서로서로 해법이 필요해요.
그래서 중복되는 부분 문제의 특성을 가지게 됩니다.
만약에 우리가 어떤 S'로 S1에서도 이리로 가고 S2에서도 이리로 가고 S3에서도 이리로 간다.
그럼 이 해법은 얘를 풀 때도 필요하고 얘를 풀 때도 필요하고 얘를 풀 때도 필요하고 계속 반복해서 나온다는 거에요.
그래서 동적계획법이 분할정복하고 다른게 분할정복은 그냥 이렇게 쪼개서 풀고 끝나면 되거든요.
근데 이렇게 되지 않고 얘를 풀려고 하니 얘가 필요하고 얘가 풀으려고 하니까 얘가 필요하고 계속 필요하네
이런 상황이 생겨요.
그래서 좀 특이한 부분이 생기는 거죠.
그래서 동적계획법에서는 이거를 어떻게 하냐.
쪼개서 푸는 것까지는 분할정복이랑 똑같은데 쪼갠 것을 합치는 데서 동적계획법만의 특이한 방법이 나오게 됩니다.
그래서 여기가 약간 어려워요.
동적계획법을 이해할 때 이게 어려운데 왜냐하면 분할정복은 푸는 순서가 중요하지 않습니다.
그냥 막 아무거나 풀면 돼요.
왜냐하면 쪼개 놓고 각각 따로 따로 풀어버리면 되니까 뭘 먼저 풀든지 이런 거는 중요하지 않고 그냥 풀기만 하면 됩니다.
동적계획법은 이게 자꾸 재활용이 되기 때문에 푸는 순서가 굉장히 중요해요.
푸는 순서가 두 가지가 있는데 하나는 바텀업 방식이 있고 탑 다운 방식이 있습니다.
바텀업이라는 거는 우리가 큰 문제가 있으면 큰 문제를 쪼개요.
근데 동적계획법이 적용되는 문제는 그냥 이렇게 쪼개지는 게 아니고 예를 들면 이 해법이 여기에도 쓰이지만 여기에도 쓰이는 거예요.
예를 들면 이렇게 중첩이 생겨요.
그래서 여기 중복되는 부분 문제라는 게 이런 겁니다.
얘가 중복이 되는 거죠.
바텀업이라는 건 바닥에서 위로 올라간다는 얘기인데 뭘 먼저 풀어야 되겠습니까?
항상 얘를 먼저 풀어야 됩니다.
그러니까 우리가 만약에 중복이 안 된다, 중복이 안 되면 어떻습니까?
이런 구조다, 그러면은 이거, 이거를 먼저 풀고 그다음에 이걸 풀긴 해야겠지만 얘를 먼저 풀지
얘를 먼저 풀지는 내 마음이란 말이에요.
사실 아무리 해도 상관없습니다.
어차피 순서 상관없잖아요.
그러니까 밑에 있는 걸 다 먼저 푼다고 치면 얘네 둘은 뭘 먼저 풀든지 상관없어요.
근데 우리가 이렇게 중복이 되면은 이거랑 이거를 풀기 전에 반드시 얘를 먼저 풀어야 됩니다.
그러니까 순서가 생기는데 그래서 이 바텀업 방식으로 할 때는 바텀업이라고 하고 태뷸레이션이라고 하는데 순서를 정할 때 얘네끼리는 순서가 상관없죠.
1, 2, 3, 4 이렇게 했다 치면 반드시 얘를 먼저 풀고 나서 그다음에 5, 6 이렇게 풀어야 됩니다.
얘네끼리는 6, 5 이렇게 해도 되지만 얘보다 얘를 먼저 풀거나 얘를 먼저 풀거나 그거는 안 된다.
그래서 작은 문제부터 풀어나가는데 먼저 풀어야 되는 애들을 먼저 풀고 그다음에 나중에 풀어야 되는 걸 나중에 푼다.
이런 방법이 됩니다.
순서를 잘 생각을 해야 돼요.
그다음에 이제 반대로 하는 방법도 있습니다.
탑다운 방식인데 탑다운은 어떻게 하냐면 문제를 잘 쪼개요.
근데 여기 중복이 하나 되어 있습니다.
중복이 되어 있고 그러면은 위에서 부터 아래로 풀어 나갑니다.
탑다운 아래로 나가는데 이렇게 내려가면 얘를 풀려고 하니까 얘랑 얘가 필요해요.
그래서 얘를 풀려고 하니까 얘랑 얘가 필요합니다.
그러면 얘랑 얘를 풀어 갖고 얘 답을 구하면 되죠.
근데 그때 풀고 그 결과를 저장을 어디다 해놓습니다.
잘 저장을 해놔요.
그래서 얘를 풀고 나서 다시 이리로 올라와요.
그럼 이제 얘가 필요하죠.
얘를 풀어야 되는데 얘를 또 푸는 게 아니라 저장해 놨던 거를 그대로 씁니다.
그러면 또 안 풀어도 되겠죠.
그다음에 얘를 풀어야 되네.
풀어서 가져와 가지고.
그래서 위에서 밑으로 내려가면서 필요한 게 있으면 그때 그때 필요할 때마다 푸는데 푼 결과를 저장을 해두면 다음번에 또 안 풀어도 되니까 또 써먹을 수 있겠죠.
그래서 기억을 해놨다가 다시 써먹는다고 해서 메모이제이션 방식이라고 합니다.
약간 말로만 들으면 어차피 내려갔다 올라오니까 똑같은 거 아니야?
이렇게 생각해드릴 수 있는데 실제로 구현을 해보면 구현이 좀 달라요.
풀어서 이걸 맞췄는데 2를 풀려면 2의 제약 조건 때문에 3같이 변동할 때도 있어요.
아 변동하면 안 되죠.
다시 바뀌어야 돼요.
바뀌면 안 되죠.
그래서 바뀌면 그러면 이제 동적개법의 특성을 이게 안 됩니다.
최적 부분 구조를 위배합니다.
작은 문제의 최적이 합치면 큰 문제의 최적이 되어야 돼요.
큰 문제 때문에 작은 문제의 답이 바뀐다 그러면 최적 부분 구조가 아닌 거죠.
아까 얘기하셨죠.
줄 건 줘 이런 거는 큰 목표가 있기 때문에 내가 작은 거는 버리겠다
이런 거잖아요.
그러면 최적 부분 구조가 아니에요.
모든 싸움에서 내가 다 이겨야겠다.
그러면 내가 전체도 이긴다.
이러면 최적 부분 구조인데 우리가 전쟁 같은 생각 보면 져야 되는 싸움도 있잖아요
가끔.
이건 저주는데 내가 결과적으로 전쟁을 이기는 게 중요하지.
개별 전투는 가끔 저주는 전투도 있어요.
이러면 최적 부분 구조가 아닌 거죠.
모든 전투에서 다 이겨야 내가 전쟁에서 이길 수 있어요.
피보나치 수열
그래서 우리가 이제 강학습의 동적개법을 적용하려면 좀 어렵기 때문에 피보나치 수혈을 일단 한번 적용을 해볼 건데요.
피보나치 수혈이 지금 보시면 딱 두 가지 특성을 만족합니다.
피보나치 수혈이 뭐냐 하면 아시겠지만 1, 2, 3, 5, 8, 13 이렇게 나가는 수혈인데 이 앞에 두 개를 더하면 고담게 되고 그 다음에 두 개를 더하면 고담게 되고 그 다음 두 개를 더하면 고담게 되고 이런 식이에요.
그래서 우리가 이제 그 순서대로 번호를 1번, 2번, 3번, 4번, 5번, 6번, 7번 이렇게 붙이게 되는데요.
그럼 피보나치 7번을 구하려면 뭐가 필요았냐면 피보나치 5번이랑 피보나치 6번이 필요합니다.
피보나치 6번을 구하려면 뭐가 필요하냐면 피보나치 5번이랑 피보나치 4번이 필요하죠.
근데 피보나치 5번을 구하려면 피보나치 4번이랑 피보나치 3번이 필요합니다.
피보나치 4번을 구하려면 피보나치 3번이랑 피보나치 2번이 필요하죠.
피보나치 3번은 2번이랑 1번이 필요하고 이런 식의 구조를 띄워.
그러면 일단 최적 부분 구조를 만족을 하죠.
약간 최적이라고 하니까 말이 이상하긴 한데 어쨌든 7번을 구하려면 얘네 둘을 구하면 되고 얘네 둘을 그냥 더하면 7번이 됩니다.
6번도 마찬가지인데 6번을 구하려면 5번, 4번을 구해서 그냥 더하면 됩니다.
부분 구조 부분의 답을 더하면 전체의 답이 돼요.
일단 최적 부분 구조는 만족하고 그 다음에 반복되는 부분 문제라는 건 보면 계속 반복되죠.
5번의 답이 7번을 풀 때도 필 요한데 6번을 풀 때도 필요하고 그 다음에 4번의 답은 5번을 풀 때도 필요하고 6번을 풀 때도 계속 반복이 돼요.
그래서 우리가 7번을 그냥 이거를 생자로 계산을 하려면 계산이 굉장히 많이 필요한데요.
재귀호출
def fib(n):
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)
%%time
fib(35)
CPU times: total: 1.97 s
Wall time: 2.24 s
9227465
그러니까 이게 숫자 하나 더 늘어날 때마다 계산량이 배로 늘어납니다.
중복되는 계산이 있는데 그걸 매번 다시 하니까 계산을 엄청나게 많이 하는 거예요.
그럼 이거를 효율적으로 풀려면 두 가지 방법이 있습니다.
하향식 동적계획법
재귀호출을 이용한 하향식(top-down), memoization 사용
def fib(n, memo=None):
if memo is None:
memo = {}
if n not in memo:
if n <= 1 :
memo[n] = n
else:
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
%%time
fib(35)
CPU times: total: 0 ns
Wall time: 0 ns
9227465
그래서 이제 동적계획법에 보시면 여기 메모라는 걸 만들어서 여기 메모는 none 이렇게 했는데 메모는 none 하면 메모가 없다
이런 얘기입니다.
메모의 기본 값은 없어요.
그래서 만약에 메모가 없으면 이런 뜻이에요.
영어로 해석하면 되죠.
만약에 메모가 없으면 메모는 중가로 이렇게 했는데 중가로는 뭐냐면 파이선의 사전이라는 구조가 있거든요.
우리가 영어 단어 같은 걸 찾을 때 빨리 찾으려면 사전을 보잖아요.
그래서 사전은 약간 빨리 찾기에 특화된 구조입니다.
빨리 찾기 특화 우리가 어제 리스트를 배웠는데 리스트는 뭔가 순서대로 저장하는 데 특화 순서대로 저장하는 데 특화되어 있고 우리가 뭘 순서대로 저장하면 찾을 때도 순서대로 찾아야 되거든요.
저장된 게 많으면 찾는데 시간이 많이 걸립니다.
사전은 빨리 찾기에 특화되어 있어서 순서는 모르겠고 빨리 찾을 수 있겠네.
이런 거예요.
그래서 우리가 메모라는 사전을 하나 만들어놔요.
전화번호를 만들어서 만약에 n not in 메모에 없으면 영어로 해석하면 되겠죠.
만약에 n이 메모에 없으면 메모에 없으면 메모에 없다는 얘기는 뭐예요?
우리가 계산한 적이 없다는 거죠.
메모에 없으면 계산을 해주시면 됩니다.
계산을 해서 메모에다가 n이 결과는 이거야 라고 써줘요.
그다음에 써주고 그다음에 우리가 메모를 해놨잖아요.
메모를 해놨잖아요.
메모해놓은 n번째 피보나 치수를 돌려준 이렇게 구현을 하면 이게 하양식 구현입니다.
보시면 풀어가는 순서는 위에서 아래로 가요.
큰 게 n번째를 구하려면 n-1번째랑 n-2번째를 구합니다.
그런데 우리가 메모를 해서 한 번 메모해놓은 거는 다시 풀지 않아.
functools의 cache를 사용하면 더 쉽게 구현
from functools import cache
@cache
def fib(n):
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)
%%time
fib(35)
CPU times: total: 0 ns
Wall time: 0 ns
9227465
근데 약간 우리가 메모이제이션을 직접 구현하면 되게 구질구질합니다, 코드가.
왜냐면 내가 이거를 일일이 이게 저장되어 있나 없나 찾아가지고 저장을 해야 되니까 좀 구질구질하거든요.
그래서 파이선에서 functools라는 거를 기본으로 제공을 합니다.
이거를 어떻게 쓰냐면 여기 원래 우리가 만들었던 이 함수잖아요.
앞에랑 똑같습니다.
여기 앞에 제기호출을 이용한 구현인데 앞에다가 골뱅이하고 캐시 이렇게 써주면 이제 이 함수는 자동으로 메모이제이션이 적용이 돼요.
그래서 한 번 실행한 결과는 다시 실행하지 않습니다.
그래서 이거는 파이선 좀 하신 분들도 모르시는 분들이 많은데 약간 꼭 동적계획법에서만 쓰는 건 아니고 비슷한 계산을 여러 번 해야 되는 경우가 있으면 이렇게 하시면 속도를 굉장히 빨리 올릴 수 있습니다.
단점은 뭘까요?
했던 결과를 저장을 해놓으니까 메모리를 많이 잡아먹겠죠.
그다음에 만약에 실행할 때마다 결과가 달라지는 함수에다가 캐시를 붙여놓으시면 큰일 납니다.
상향식 동적계획법
상향식(bottom-down), tabulation 사용
그 다음에 우리가 이제 상향식으로도 풀 수 있는데요.
상향식으로 풀려면 좀 어렵습니다.
왜냐하면 하향식은 그냥 우리가 좀 직관적인 순서대로 풀면 되는데 그 중간중간에 풀이가 중복이 되면 저장을 해 놓으면 되거든요.
상향식은 올바른 순서대로 풀어야 되기 때문에 이건 좀 사람이 생각을 해야 됩니다.
올바른 순서대로 풀려 면 어떻게 되나.
근데 피고나치 수혈 같은 경우는 사실 올바른 순서가 뻔해요.
별 거 없잖아요.
그냥 0, 1, 2, 3. 이 순서대로 풀면 됩니다.
그래서 생각을 하셔야 되는데 상향식 방법은 태뷸레이션이라고 하는데 왜 태뷸레이션이라고 하냐면 보통 테이블이라고 해서 약간 메모니제이션이랑 비슷하긴 한데 메모니제이션은 내가 찾아야 돼요.
이거 내가 언제 풀었더라 하고 찾아야 되는데 태뷸레이션은 순서대로 풀기 때문에 찾는 거는 별로 중요하지 않습니다.
태뷸레이션은 순서대로 풀기 때문에 찾는 거는 별로 중요하지 않습니다.
def fib(n):
table = [0] * (n+1)
table[1] = 1
for i in range(2, n+1):
table[i] = table[i-1] + table[i-2]
return table[n]
%%time
fib(35)
CPU times: total: 0 ns
Wall time: 0 ns
9227465
이 상향식 방법의 장점이 있는데 뭐냐면은 프로그래밍을 배우신 분들은 아시겠지만 이렇게 재기적으로 정의하는 구조를 재귀호출이라고 하는데 보통 프로그램 배우시는 분들은 배울 때 아시겠지만 이거 보통 하지 말라고 배우거든요.
그죠?
재귀호출은 하지 말라고 배웁니다.
왜냐하면은 이렇게 함수호출을 함수호출 안에 함수호출이 있고 이런 구조가 되면은 이거를 어디다 저장을 해놔야 돼요.
왜냐하면 그래야 내가 이걸 저장을 시행을 했을 때 여기로 되돌아갈 수 있거든요.
그래서 재귀호출을 하면은 호출 기록을 어디다 저장을 해놓는데 문제가 뭐냐면 파이선은 이 호출을 많이 하는 거에 한계가 있습니다.
기록을 하다가 그 기록할 수 있는 공간을 STACK이라고 하는데 STACK이 꽉 찹니다.
보통 STACK을 그렇게 많이 확보를 해두지 않거든요.
그러면은 STACK이 꽉 차서 넘치는 에러가 발생을 해요.
그래서 그거를 컴퓨터 용어로 STACK OVERFLOW라고 하는데 STACK이 넘친다
이런 겁니다.
STACK은 뭐냐면 함수 호출을 저장해 놓는 공간인데 함수 호출을 너무 많이 하니까 그냥 많이 하면 상관없는데 이 함수를 하려면 점수를 해야 하고 점수를 하려면 점수를 해야 하고 다 기록해 놓아야 된단 말이에요.
그래서 재기 호출을 하면은 함수 호출이 쌓여서 STACK OVERFLOW가 발생할 수가 있습니다.
bottom up 방식으로 짜는 게 훨씬 안전한 구조이긴 한데 이거는 여러분이 생각을 하셔야 하기 때문에 순서를 생각하셔야 하기 때문에 약간 골치가 품다.