[실전 알고리즘] 0x06강 - 재귀_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x0B강 - 재귀에서 확인할 수 있습니다. 리뉴얼 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

이번 시간에는 재귀를 다뤄보도록 하겠습니다.

 

 

재귀는 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식으로 주어진 문제를 푸는 방법을 의미합니다. 충분히 익숙하지 않으면 남이 재귀로 짠 코드를 이해하는 데에도 정말 오랜 시간이 걸리고, 능숙하게 재귀를 이용할 수도 없습니다.

 

자기 자신을 다시 호출할 때에는 현재 함수에서의 입력값보다 더 작은 값을 인자로 넘겨주어야 합니다. 그렇지 않으면 프로그램이 끝나지를 않겠죠.

 

함수의 입력값이 일정 크기 이하일 때에는 더 이상 자기 자신을 호출하지 말고 값을 바로 반환해야 합니다. 이러한 하위 문제를 base condition이라고 부릅니다.

 

간단한 예시를 들어보겠습니다. $N$을 입력받아 $N$부터 1까지를 차례대로 출력하는 함수를 재귀적으로 짜보았습니다. $func(n)$은 $n$을 출력하고 $func(n-1)$을 실행하면 됩니다. 보면 $n = 1$일 때 더 이상 자기 자신을 호출하지 않는 것을 볼 수 있습니다. 즉 $n = 1$이 base condition입니다.

 

$N$을 입력받아 $N!$을 계산하는 함수도 마찬가지로 재귀적으로 구현할 수 있습니다. 이 때도 마찬가지로 $n = 1$일 때가 base condition입니다.

 

지금은 간단한 예제를 다루어서 각 함수가 어디까지 연산을 수행하고, 어떤 입력값을 재귀적으로 넘겨주어야 할지를 간단하게 정할 수 있었지만 어려운 문제에서는 이런 점들을 미리 잘 정리해두고 코딩에 들어가야합니다. 그렇지 않으면 코드를 짜다가 굉장히 꼬이게 됩니다.

 

모든 재귀 함수는 재귀 구조 없이 반복문만으로 동일한 동작을 하는 함수를 만들어낼 수 있습니다.(역도 성립합니다.) 재귀를 사용할 경우 반복문으로 구현을 했을 떄에 비해 코드를 간결하고 이해하기 쉽게 만들 수 있다는 장점이 있지만 메모리/시간에서는 손해를 봅니다. 그렇기 때문에 경험적으로 어떨 때 재귀를 사용하면 유리하고 어떨 떄에는 굳이 재귀를 사용할 필요가 없는지를 알고 있는 것이 좋습니다.

 

재귀를 쓸 때 한 함수가 자기 자신을 여러 번 호출하게 되면 시간복잡도가 굉장히 커질 수 있다는 점을 주의해야 합니다. 피보나치 수열은 재귀로 해결하면 안되는 대표적인 예시입니다.

 

나중에 다이나믹 프로그래밍을 배우고 나면 $k$번째 항을 $O(k)$에 구할 수 있음을 알게 되지만, 상식적으로 생각해도 앞에서부터 차례로 계산하면 $k$번의 덧셈으로 $k$번째 항을 구할 수 있을 것이라는 것을 쉽게 알 수 있습니다. 이를 재귀함수로는 이와 같이 구현할 수 있습니다.

 

그런데 이 재귀함수에서 생각을 해보면, $f(5)$를 구하기 위해 $f(4)$와 $f(3)$이 호출이 됩니다. 그리고 $f(4)$를 구하는 과정에서 $f(3)$, $f(2)$가 계산됩니다. 이렇게 계산이 이루어지는 상황을 나타내면 이런식으로 나타낼 수 있습니다. 한참 후에 배우겠지만 이러한 그림을 트리라고 부릅니다.

 

아무튼 그림을 보면, 이미 계산한 값을 다시 계산하는 일이 빈번함을 알 수 있습니다. 예를 들어 $f(2)$는 3번 계산하고 $f(3)$은 2번 계산하네요. 이렇게 피보나치 함수를 재귀적으로 계산하면 $k$번째 항을 구하기 위해 $O(1.618^k)$의 시간복잡도를 필요로 합니다. 뜬금없이 1.618 이라는 이상한 값이 나와 당황스럽겠지만, 1.618이 중요한 것은 아니고 $k$에 대한 지수함수 만큼의 시간이 걸린다는 점을 기억하시면 됩니다. 참고로 1.618은 점화식의 일반항을 구하는 과정을 통해서 도출이 가능합니다. 그러나 점화식의 일반항을 구하는 방법을 알아도 굳이 증명해볼 필요는 없고, 몰라도 크게 지장은 없습니다.

 

재귀함수에서 계속 깊이 들어갈 때 스텍 메모리에 계속 누적이 됩니다. 문제 전체의 메모리 제한만 있고 스택 메모리에 다른 제한이 없다면 애초에 재귀로 스택 메모리를 다 채우고 싶어도 그 전에 시간 초과가 먼저 발생하므로 스택 메모리를 신경쓸 필요가 없습니다.(함수 호출은 시간이 꽤 오래 걸리는 명령입니다.)

 

그런데 스택 메모리가 1MB로 제한이 있을 경우에는 분명 정상적인 코드임에도 불구하고 스택 메모리를 넘겨 대략 20000-40000번 정도의 깊이를 가진 재귀 함수가 Runtime Error를 발생시킬 수 있습니다. 재귀 함수 한 번당 스택 메모리를 정확히 얼마나 소비하는지는 그 함수의 인자의 갯수와 함수 내에서 선언한 지역 변수의 갯수에 따라 다르며, 정확하게 알고싶으면 32/64bit 컴퓨터에서의 함수 호출 규약을 알고 있어야 하기 때문에 설명을 하지 않겠습니다.

 

만약 본인의 개발환경에서 오른쪽의 코드가 정상적으로 동작하지 않는다면 3,500,000번의 깊이를 가진 재귀 함수를 정상적으로 처리할 수 없다는 의미이니 구글의 도움을 얻어 스택 메모리 제한을 없애세요. 제가 쓰고 있는 Windows에서의 Visual Studio Code는 --stack=536870912 컴파일 옵션을 통해 스택 메모리 제한을 512MB로 변경했습니다.

 

이상하게 삼성이 역량테스트, 운영하는 저지 사이트인 SW expert academy, SCPC 등에서 스택 메모리를 1MB로 제한합니다. 실제로 앞 장의 코드를 SW expert academy에 제출해보면 Runtime Error가 발생합니다. 3,500,000번까지가 아니라 35,000번만 깊이 들어가게 해도 Runtime Error가 발생합니다.

 

왜 이런 스택 메모리 제한을 두는지 잘 이해가 안가지만, 저희는 슈퍼을이기 때문에 주어진 환경 내에서 충실히 코딩을 할 뿐입니다ㅠ_ㅠ 삼성과 같이 스택 메모리가 굉장히 작게 제한된 곳에서 문제를 풀 때, 본인의 풀이가 재귀 호출을 20000-40000번 이상 해야 한다면 어쩔 수 없이 재귀 호출 말고 반복문으로 풀어야 합니다. 다른 코딩테스트에서도 스택 메모리가 명시되어있지 않으면 꼭 질문을 해서 예기치않은 맞왜틀을 방지하세요!

 

이제 실제로 재귀 함수를 써서 문제를 풀어봅시다. 재귀를 통해 풀 수 있는 첫 번째 문제는 거듭제곱 문제입니다. $a^b mod\, m$을 어떻게 구할 수 있을까요? 제일 쉽게 떠올릴 수 있는 방법은 $a$를 $b$번 곱하는 방법입니다. 시간복잡도 $O(b)$에 해결 가능합니다. 위의 코드가 제대로 동작하지 않는 이유는 알고계시죠? 잘 모르겠으면 한 5분 정도 고민을 해보고 다음 장으로 넘어갑시다.

 

정답은 바로 int overflow입니다. $6^$는 int의 범위를 벗어나기 때문이죠. 그렇기에 중간 연산 과정에서도 계속 $m$으로 나눠주면 정상적인 답을 얻을 수 있습니다. 만약 $m$이 $2^$ 이상일 경우에는 $2^$보다 큰 두 개의 수를 곱하는 연산을 수행해야 하고 이 연산은 long long 범위로도 담을 수 없기 때문에 __int128을 사용하거나 Python 혹은 JAVA를 사용해야 합니다. 정상적인 코딩테스트라면 이런 문제는 안나올테니 코딩테스트를 위해 __int128을 알아둘 필요는 없습니다.

그런데 b가 그다지 작지 않고 최대 20억이면 어떻게 해야할까요? (BOJ 1629번 : 곱셈) 0x01강에서 언급했듯 컴퓨터는 1초에 대략 1-3억개의 연산을 수행할 수 있기 때문에 20억은 힘들 것입니다. $b = 2k$ 혹은 $b = 2k+1$일 때(즉 짝수/홀수일 때)에 따라 $a^b$를 $a^k$에 관한 식으로 바꿀 수가 있습니다. 재귀 함수를 어떤 식으로 만들면 될지 구조가 그려지나요? 일단 직접 한 번 시도한 후에다음 장으로 넘어갑시다.

 

정답 코드를 참고해보세요. 코드에서 $b$는 한 단계를 따라 들어갈 때 마다 절반 이하로 줄어듬이 보장되므로 시간복잡도는 $O(lg b)$입니다. $3^\, mod\, 61$을 구하는 과정을 재귀 함수의 호출로 생각해보면 이렇습니다.

 

직접 짜서 WA(Wrong Answer, 틀렸습니다.)를 받아보셨나요? 과연 어떤 점을 틀린걸까요? 여기에 자주 실수하는 점들을 넣어둔 3개의 함수가 있습니다. 어떤 점이 잘못됐는지 찾아보세요.

 

POW1은 base condition이 없어 무한 루프에 빠지다가 시간 초과 혹은 런타임 에러가 발생합니다.

 

POW2는 중간 결과를 $m$으로 나누어주면서 계산을 한 것 같지만 $b$가 홀수일 때 $val * val * a$를 계산하면서 int overflow가 발생할 수 있습니다. $val$, $a$ 모두 최대 $2^-1$이기 때문입니다. 마지막 return을 $val*val\,\%\,m*a\,\%\,m$으로 수정하면 해결할 수 있습니다.

 

POW3은 POW2에서 본 int overflow와 더불어, 함수를 2번 호출함으로 인해 시간복잡도가 $O(lg b)$가 아닌 $O(b)$가 됩니다. 피보나치 함수를 재귀로 푸는 것과 유사한 상황인거죠. 이미 계산한 것을 중복으로 계산하지 않도록 조심해야합니다.

 

두 번째 문제는 하노이 탑 문제입니다. 어렸을 적에 하노이 탑 교구를 가지고 놀아본 분도 있을텐데요, 하노이 탑 문제는 3개의 기둥이 있을 때 작은 원판 위에 큰 원판을 놓을 수 없다는 규칙을 만족시키면서 원판을 한 번에 한 개씩 옮겨 한 기둥에 있는 $n$개의 원판을 다른 기둥으로 옮기는 문제입니다. $n=3,4,5$일 때 최소 횟수는 얼마인지 직접 시도해보세요.

 

직접 해봤을 때 최소 횟수가 7, 15, 31이 나왔나요? 아니라면 다시 해봅시다. 직접 해보다보면 재귀적인 구조를 더 빨리 파악할 수 있습니다. 이제 다시 일반화된 문제를 풀어봅시다 기둥 1에 $n$개의 원판이 있을 때 기둥 3으로 모두 옮기려면 적어도 몇 번의 이동이 필요하고, 또 어떻게 옮겨야할까요? (BOJ 11729번 : 하노이 탑 이동 순서)

 

어려울 것 같지만 차근차근 생각해보면 쉽습니다. 기둥 1에서 기둥 3으로 모든 원판을 옮기기 위해서는 어떤 절차를 거쳐야하는지 재귀적인 관점에서 충분히 고민해보고 다음 슬라이드로 넘어와주세요.

 

첫 번째로 원판 1부터 $n-1$까지를 기둥 1에서 2로 옮깁니다. 그렇지 않으면 원판 $n$이 움직일 수 없기 때문입니다.

 

두 번째로 원판 $n$을 기둥 1에서 3으로 옮깁니다.

 

마지막으로 원판 1부터 $n-1$까지를 기둥 2에서 기둥 3으로 옮깁니다.

 

정말 간단하지 않나요? 딱 세 단계로 깔끔하게 해결할 수 있습니다. 조금 더 일반화해서 $n$개의 원판이 놓인 기둥을 $a$, 목적지를 $b$, 원판이 놓여있지도 않고 목적지도 아닌 기둥을 $c$라고 하면 $n$개의 원판을 $a$에서 $b$로 옮기는 과정은 3개의 과정으로 나눌 수 있습니다.

1. $n-1$개의 원판을 $a$에서 $c$로 옮깁니다.
2. 마지막 원판을 $a$에서 $b$로 옮깁니다.
3. $n-1$개의 원판을 $c$에서 $b$로 옮깁니다.

예외적으로 $n$이 1일 경우에는 2번 과정만 하면 됩니다.

 

func(a, b, n)을 $n$개의 원판을 $a$에서 $b$로 옮기는 과정이라고 할 때 재귀적으로 코드를 짤 수 있습니다.

 

더 나아가 재귀적으로 생각한 방법으로부터 $n$개의 원판을 옮기는 최소 휫수 = $n-1$개의 원판을 옮기는 최소 횟수 × 2 + 1임을 알 수 있습니다. 이 때 일반항은 $2^n-1$이 됩니다. 점화식의 일반항을 구하는 방법을 알아야 이 식을 유도해낼 수 있지만 코딩테스트에서 이러한 지식이 필요한 일은 없을 것이기 때문에 하노이 탑이 $2^n-1$이라는 것만 기억하면 됩니다. 정답 코드를 확인해보세요.

 

문제를 몇 개 소개해드리겠습니다. 16684는 풀라고 낸 문제는 아니니 하노이 탑을 이런 식으로 더럽게 꼬아서 낼 수도 있구나 하는 것만 보고 바로 끄시면 되겠습니다. 나머지 4문제는 풀어보시는걸 추천드립니다. 안 익숙하면 함수를 어떤 식으로 잡아야할지, 또 구현은 어떤식으로 해야할지 굉장히 막막할 수 있어요. 그렇지만 재귀를 확실하게 익혀두어야 다음 시간에 할 백트래킹을 무난하게 넘어갈 수 있습니다. 그러니 문제를 풀어보세요. 오래 생각했는데도 도저히 헷갈려서 혼자 짤 자신이 없으면 풀이를 참고해서라도 꼭 풀어보세요!