//톨
논제랑 전혀 상관 없는 얘기지만 재귀로 짜면 가산을 준다는건
재귀를 이해하고 더 나은 풀이를 제공했을때 얘기겠죠?
점화식을 그대로 코드로 옮기는것이 최종 솔루션이 되서는 곤란하다 생각하구요
(대부분에 상황에서 면접자가 언급을 할테고, 그대로 제출 했다면 면접관이 다른 풀이를 유도할 것 같습니다)
그럼에도 재귀를 언급 했다는 것은 더 나은 풀이가 있다는 힌트가 될 것 같습니다
학부에서 분할정복이라는 알고리즘을 배우는데 피보나치도 이것의 한 예시죠
일반적인 반복은 O(N)에 해를 구하지만 분할정복으로 접근하면 O(logN)에 해를 구할 수 있습니다
위에서 많은 분이 이야기하신 실무에 그다지 도움이 되지는 않지만 신입에게 유리한 측면이 이런 것이라 생각합니다
물론 같은 동작을 반복으로도 작성할 수 있지만
분할정복의 성질이 재귀와 관련이 깊다보니 재귀쪽 풀이가 좀 더 직관적인건 어쩔 수 없습니다
function mult2x2(A, B) {
const C = [[0, 0], [0, 0]];
for (let i = 0; i < 2; ++i) {
for (let j = 0; j < 2; ++j) {
let sum = 0;
for (let k = 0; k < 2; ++k) sum += A[i][k] * B[k][j];
C[i][j] = sum;
}
}
return C;
}
function pow2x2(A, n) {
if (n == 0) return [[1, 0], [0, 1]];
if (n == 1) return A;
const m = ~~(n / 2); // int div
const Am = pow2x2(A, m);
const Anfloor = mult2x2(Am, Am);
return n % 2 ? mult2x2(Anfloor, A) : Anfloor;
}
function fib(n) {
const A = [[1, 1], [1, 0]];
const An = pow2x2(A, n);
return An[1][0];
}
코드를 즉석에서 완성하는 것은 기대하지도 않지만
분할정복을 알고 있고 반복하는 방식보다 더 나은 풀이가 될 수 있다는 것을 "언급"만 하더라도
그 면접자에 대해서는 더 이상 알고리즘에 대한 검증이 필요 없고 바로 실무 관련 질문을 해도 충분하다 생각합니다
정리하자면
- 재귀로 풀면 가산점을 주겠다 하신 분에 대한 쉴드
- 실제로 신입에게 유리한 측면이 어느정도 있음
- 잘하면 좋지만 최소한의 풀이로 충분 (바보 거르기)
- 코드보다는 원리가 중요
