배경
재귀를 주제로 경기대 배상원 교수님께서 강의를 해주셨다. 목적은 알고리즘 문제나 설계를 어떻게 바라보는지 관점을 배우는것이였다
요약
대략 2시간 정도 진행되었는데, 재귀를 비롯한 함수에 대한 통찰력을 얻을 수 있었다.
주요 내용
- 문제를 함수로 바라보자 (입력값을 정의역)
- 함수는 어떤 문제를 해결하는 코드 덩어리
- reduction과 black box
알고리즘
알고리즘은 문제를 해결하기 위해 필요하다. 그래서 문제를 먼저 잘 파악하고 적절한 알고리즘을 서술해야한다.
재귀함수 구성
- base case
- recursion step (reduction)
아주 간단해서 바로 풀 수 있는 단계를 base case. 그렇지 않다면 문제를 여러개의 작은 문제로 나눈다 (reduction).
동작이 제대로 이루어졌음은 수학적 귀납법(induction)을 통해 증명할 수 있는데, 사실 재귀 코드 자체가 증명과 비슷하다고 말씀하셨다. 왜냐면 base case로부터 하나씩 n을 증가(혹은 감소)시키면서 논리를 전개하면 되기 때문이다.
재귀
재귀는 설계단계에서 문제를 풀 때 좋은 도구다. 구현시 성능을 위해서 반복문으로 변환하곤 한다.
reduction
"문제를 풀기 위해 다른 함수를 호출하는 것"으로 이해했다. 원문제를 여러 단계로 나누고, 각 단계를 다른 문제로 변홚시킬 수 있는데 이게 reduction이다. reduction은 함수 호출을 통해, 할 일이 줄어든다고 설명해주셨다. 여기서 중요한 것은 호출한 함수는 어떤 문제를 해결하는지 명확히 알고있는게 중요하다.
함수는 black box처럼 내용을 볼 필요가 없다. signature와 주석을 통해 함수가 어떤 문제를 해결해준다는 것을 이해하면 되고, 내부는 잘 동작한다고 가정한다. 그래서 호출한 함수가 어떤 문제를 해결하는지만 이해하면 되고, 내부를 들여다보지 않아야 알고리즘 설계가 편해진다.
예를 들면, 배열에서 k번째로 작은 원소를 찾는 문제를 해결한다고 해보자. 그러면 arr.sort() -> arr[k-1]을 반환하는것으로 문제를 나눌 수 있다. sort로 reduction이 일어났고, sort는 iterable을 정렬시켜준다는것만 알면 되고, 내부에서 어떤일이 일어나는지는 알 필요가 없다.
들은 이야기로는 함수의 네이밍 혹은 signatur가 중요하다, 그것만으로도 어떤 일을 하는지를 알 수 있어야한다고 들었다. 아마, 실제 코드를 이해할 때 코드가 어떤 문제를 해결하는지만 알면 되고 그게 제대로 동작하는지 여부는 작성자 책임이다.
재귀함수 시간복잡도
일반 함수의 경우에는 redunction 함수 시간 복잡도를 먼저 계산하고, 함수 전체의 시간 복잡도를 계산하면 된다. 그러나 재귀는 스스로를 호출하기 때문에 시간 복잡도를 다르게 구해야한다.
교수님이 보여주신 방법은 다음과 같다.
1. 재귀함수의 시간복잡도를 T(n)으로 둔다.
2. base case로부터 논리를 전개하여 T(n)에 대한 점화식 구하기
3. 점화식을 통해 시간 복잡도를 구하기 (점화식 계산은 수학적 지식이 필요한데, AI를 통해 구해도 좋다)
질의응답
인상적이였던건 알고리즘을 잘하기 위해서 수학을 잘해야한다는 내용과, 어떤 수학을 공부해야하냐는 질문이였다.
교수님은 특정하기 보다는 아는 모든걸 이용해야한다고 했다. 내 생각엔 난 개발자이지 수학자는 아니니까, 필요할때마다 배우는게 좋은 것 같다.
