쉽지 않다 reduce...

Github 1기 과제 제출 저장소의 Pull Request 목록을 둘러보던 중 내가 제출했던 피보나치 수열 생성기 과제가 아직도 merge되지 않은 부분이 눈에 띄었다. (과제 요구사항)

피보나치 수열 생성은 재귀함수 방식으로 풀 경우 숫자가 커질수록 계산 횟수가 급격하게 불어나는 문제점이 있다. 주어진 수보다 2 작은 수, 1 작은 수를 인자로 갖는 자기 자신의 함수를 재호출해서 더하는 과정을 거치는데, 인자가 작아질수록 같은 계산을 반복하는 과정이 늘어나면서 O(2^n)이라는 좋지 않은 시간 복잡도를 갖는다고 한다. 그래서 이전에 계산해놓은 결과 값이 있을 경우 그 값을 참조하는 Memoization 방식을 이용할 경우 계산 횟수를 획기적으로 단축시킬 수 있다.

 

최근 JavaScript의 배열에 사용할 수 있는 함수인 reduce를 이리저리 건드려보고 있었고, reduce 함수를 사용하면 선언형 방식으로도 fibonacciNumber에 결과값이 누적되는 배열을 전달해주는 식으로 Memoization을 적용할 수 있지 않겠나 생각이 들어 reduce 함수를 사용하는 방식으로 리팩터링하는 것을 도전했다.


❗️ 중간에 글을 작성하던 중 확인한 부분이 있다. 문제의 요구사항은 fibonacciNumber의 인자로 정수 하나가 전달되는 것이므로 이 방식으로 풀면 안 된다. 과제 요구사항 만족 측면에서는 헛발질을 했지만... reduce를 분석해본 데 의의를 두고자 한다.


리팩터링한 fibonacciArray 함수는 다음과 같다.

function fibonacciArray(size) {
  if (size <= 0) {
    return [0];
  }

  const array = [...Array(size)].reduce((accumulatedArray, _, index) => (
    [...(accumulatedArray), fibonacciNumber(accumulatedArray, index + 1)]
  ), []);

  return array;
}

reduce가 어떻게 쓰였는지 파헤쳐보면 다음과 같다.

• [...Array(size)]
  Array() 함수로 size 값 크기의 배열을 생성하고, '...' 으로 배열을 풀어서 배열의 각 원소가 '[ ]' 배열의 각 원소가 되게 한다. 즉 size 크기이고, 요소 값은 모두 undefined인 배열을 생성한다. 문제를 풀기 위해서는 각 요소의 index만을 활용할 것이기 때문에 값들이 undefined이더라도 의미는 없다.
  
  
• reduce((accumulatedArray, _, index) => ( )
  • accumulatedArray
    [...Array(size)]의 각 요소에 대하여 연산을 수행할 때, 이전 연산의 결과로 전달되는 값이다. 이전 연산의 결과로 이전 요소의 index에 해당하는 피보나치 수 계산 결과값들이 들어있는 배열이 전달되는 것을 의도했다.
    예를 들어, size로 5가 전달되었고, reduce 내에서 [...Array(5)]의 네 번째 요소를 보고 있다면 accumulatedArray로 이전 요소까지의 피보나치 수 계산 결과를 담은 배열 [0, 1, 1]이 전달된다.
    
    
  • _
    [...Array(size)] 에서 순서대로 참조하는 요소이다. 함수 내에서 사용하지 않을 것이기 때문에 미사용의 의미를 내포하는 네이밍을 했다.
    
    
  • index
    [...Array(size)] 에서 순서대로 참조하는 요소의 index이다.
    
    
• reduce((   ) => (   ), []);
  [...Array(size)]의 각 요소를 순회할 때마다 (   ) 를 인자로 받아 (   ) 의 연산을 수행한 값을 반환한다. []는 accumulatedArray로 주어지는 초기값이다. 빈 배열을 전달하도록 했다.
  
  
• [...(accumulatedArray), fibonacciNumber(accumulatedArray, index + 1)]
  
  • [ ]
    [ ] 내부에서 수행한 연산 결과를 배열의 형태로 만드는 것을 의도했다.
    
    
  • ...(accumulatedArray)
    전달받은 accumulatedArray를 풀어헤쳐 [ ] 에서 앞선 요소로 배치한다.
    
    
  • fibonacciNumber(accumulatedArray, index + 1)
    피보나치 수를 구하는 함수에 기존의 결과값들이 들어있는 배열과, 문제의 요구조건에 맞는 크기로 index를 변환한 수를 인자로 전달하여 결과 피보나치 수를 반환한다. 해당 반환값은 [ ] 에서 마지막 요소로 추가된다.
    
    

다음은 리팩터링한 fibonacciNumber 함수이다.

function fibonacciNumber(accumulatedArray, number) {
  if (number <= 1) {
    return 0;
  }

  if (number === 2) {
    return 1;
  }

  return accumulatedArray[number - 3] + accumulatedArray[number - 2];
}

위와 같이 reduce 함수를 구현하는 과정에서 겪었던 어려움은 (   ) 부분이 무엇을 하는 것인지를 잘 파악하지 못했다는 점이었다. accumulator에 해당하는 인자를 어떻게 전달해야 하나 이해가 되지 않았고, '값'을 나타내는 Arrow Function의 (   ) 부분에서 단일한 식을 쓰고 그 앞에 return을 붙이는 것을 시도했는데 잘 되지 않았다. 예를 들면

reduce((accumulatedArray, _, index) => (
    return [...(accumulatedArray), fibonacciNumber(accumulatedArray, index + 1)];
), [])

이런 비슷한 식의 맞지 않는 구현을 시도했다. [ ] 으로 나타낸 '값'을 반환하는 형태가 콜백 함수로 잘 나타나 있으므로 굳이 return을 앞에 쓰지 않아도 그 자체만으로도 '값'임을 나타낼 수 있었는데 말이다. 이전에 트레이너님께서 Arrow Function과 콜백 함수, 일반적인 형태의 함수를 바꿔 가며 작성하는 것을 보여주셨는데, 이제는 약간은 이해가 될락 말락 한 기분이다. 일반 함수와 Arrow Function, 콜백 함수의 차이점을 기회가 될 때 한번 살펴봐야 할 듯 싶다.

reduce를 다음과 같은 형태로도 쓸 수 있음을 참고할 수 있다.

const array = [...Array(size)].reduce(function(accumulatedArray, _, index) {
  return [...accumulatedArray, fibonacciNumber(accumulatedArray, index + 1)];
}, []);

* reduce 구현과는 논외로 테스트 코드가 계속해서 통과하지 않았던 이슈도 있었다. 구현부에서 fibonacciNumber의 인자로 accumulatedArray를 추가했는데, 테스트 코드에서는 accumulatedArray를 추가해주지 않아서 테스트 코드가 실행될 때 계속해서 값이 들어있지 않은 배열을 임의로 참조하는 과정에서 오류가 발생했던 것 같다.

해당 오류를 찾기 위해 1시간 이상의 적지 않은 시간을 썼었는데, 테스트 코드에서 fibonacciNumber의 인자가 배열을 어떤 형태로 받아야 하는지를 먼저 정의하고 Red를 본 뒤 Green, Refactoring 과정을 거쳐 소스코드를 수정했다면 문제점을 찾는데 시간을 아낄 수 있지 않았을까 하는 생각이 든다.