"본투비 문과, 수학을 배우다"
Intro
저는 한 학년이 13명 남짓한 한 반으로 구성된 외국의 아주 작은 학교를 다녔는데요. 그러다보니 문과/이과 구분도 없었고, 수학을 깊게 배울 일이 없었습니다. 그래서 알고리즘을 공부하면서 점화식이란 말이 나올 때마다 대체 이게 뭔가 싶더라구요.
점화식을 검색하면 위키백과와 나무위키 문서가 나오는데요. 어려운건 매한가지지만 그래도 위키백과의 설명이 조금은 더 쉬운 것 같아서 위키백과를 기준으로 이해한 바를 적어보려 합니다.
점화식이란?
위키백과에 나온 점화식에 대한 설명을 인용하면 다음과 같습니다.
수학에서 점화식(漸化式) 또는 재귀식(再歸式, 영어: recurrence relation)이란 수열에서 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식이다.
수학을 모르는게 자랑거리는 아닙니다만, 프로그래밍을 공부하는 데 있어서 어떤 개념을 단어 하나까지 다 이해하려고 할 필요는 없다고 생각합니다. 대신 위의 설명에서 제 눈에 들어온 건 굵게 처리해 둔 두 내용인데요. 하나는 재귀식이라는 단어고, 다른 하나는 이웃하는 두 개의 항 사이에 성립하는 관계 입니다.
인용한 설명에서는 재귀식을 점화식의 또 다른 이름이라고 하고 있네요. 마침 프로그래밍에서 계속 배우고 있는 재귀라는 단어가 들어가 있으니, 뭔가의 단서가 될 수 있을 것 같습니다.
프로그래밍에서는 어떤 함수 안에서 자기 자신을 다시 호출하는 함수를 재귀함수라고 부르는데요. 이 때 호출하는 함수 그 자체와 재귀적으로 호출되는 함수 사이에는 어떤 상관관계가 있기 마련이죠. 마침 인용한 설명에서도 점화식은 이웃하는 두 개의 항 사이에 성립하는 관계 에 대한 것이라고 말하고 있습니다.
따라서 위의 그림을 이해하면 다음과 같이 됩니다. an 과 an + 1 이 인접한 항이라고 할 때, 어떤 함수를 an 에 씌워 an + 1 이라는 결과를 얻을 수 있다면 함수 f 가 수열 { an } 의 점화식이 되는 것이죠.
위키백과의 점화식 내용 중에서 피보나치 수열과 하노이의 탑을 통해 보다 더 쉽게 이해할 수 있을 것 같습니다. 프로그래밍에서도 자주 다루게 되는 알고리즘 문제이니 말이죠.
피보나치 수열을 만들 때의 재귀식을 간단히 하면 다음과 같은데요.
function fibonacci(n) {
if ( n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}이 때 base case 가 되는 if 의 내용을 제외한 fibonacci(n - 1) + fibonacci(n - 2) 가 바로 피보나치 수열에 대한 점화식이 되는 것입니다.
하노이의 탑 문제도 점화식으로 간단하게 정리해 둔 내용을 확인할 수 있는데요.
n 개의 원판을 이동하는 회수를 수열 an 으로 정의하자. n 개의 원판을 이동시키기 위해서는 그 위쪽 n - 1개의 원판을 다른 막대로 이동한 후, 맨 아래쪽 원판을 이동하고 다시 n - 1개의 원판을 이동해야 하므로 다음과 같은 점화식이 성립함을 알 수 있다.
5 개의 원판을 옮겨야 한다면, 4 개의 원판을 다른 곳으로 옮기는 것을 2 번만큼 반복해야 하고, 그 사이에 제일 아래의 원판을 옮기는 회수 1 이 추가된다는 것입니다. 따라서 이 식은 아주 쉽게 2n - 1 이 된다고 하네요.
물론 이동횟수에 관한 점화식이기 때문에 만약 "최소한의 횟수로 이동할 때 원반을 옮기는 순서"와 같은 문제라면 다른 접근을 추가적으로 고민해보아야 합니다. 관심이 있으신 분들을 위해 링크를 남겨놓도록 하겠습니다.
