파스칼의 삼각형 계산하기

최근에 코딩테스트를 몇개 봤는데 그 중에서 기억나는 문제 그당시에는 해결하지 못한 개선점 하나 써보고자 한다.

문제는 간단하다! 파스칼의 삼각형 array를 구현하는 것이다.

문제

row 값을 입력했을 때, 파스칼의 삼각형을 구성하는 수들을 배열로 만들기

getPascalArray(1);  // [[1]]
getPascalArray(4); //  [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]

파스칼의 삼각형이란

파스칼의 삼각형이라 함은 서로 옆에 있는 수 두개를 더해서 아래의 수를 만들어 나가는 삼각형이다.

구현 과정

• 파스칼의 삼각형은 서로 옆에 있는 수 두개를 더해서 아래의 수를 만들어 나가는 삼각형 이기 때문에
• 우선, 서로 옆에 있는 수 두개를 더해서 아래의 수를 만들어 내는 함수를 만들었다.

getPascalNum 함수

const getPascalNum = (row, col) => {
  if (col === 1 || col === row) return 1;
  return getPascalNum(row - 1, col - 1) + getPascalNum(row - 1, col);
};

getPascalArray 함수

const getPascalArray = (row) => {
  const result = [];
  for (let i = 1; i <= row; i++) {
    const temp = [];
    for (let j = 1; j <= i; j++) {
      temp.push(getPascalNum(i, j));
    }
    result.push(temp);
  }
  return result;
};

내가 제출한 함수는 위와 같다.

문제발생

• 하지만, 제출한 함수에 대해서 불필요한 계산이 계속 되고 있지 않냐는 피드백을 받았다.
• 확인해보니, 3행의 pascal Num 들을 계산한다고 생각했을 때, 기존 2행의 array가 구해져있음에도 이를 활용하지 않고, 새로 pascal Num 을 구하기 위한 재귀함수가 실행되는 것이다.
• 행 수가 적으면 괜찮을지 모르나, 늘어날 수록 계산 시간은 엄청나게 들 것이다..

개선방법

• 집에와서 다시 개선해본 함수는 아래와 같다.
• prevRow가 있을 경우에는 prevRow를 사용해서 덧셈 계산만 하기.

const getPascalArray2 = (row) => {
  const result = [];
  for (let i = 0; i < row; i++) {
    const temp = [];
    for (let j = 0; j <= i; j++) {
      if (j === 0 || j === i) {
        temp.push(1);
      } else {
        const prevRow = result[i - 1];
        const sum = prevRow[j - 1] + prevRow[j];
        temp.push(sum);
      }
    }
    result.push(temp);
  }
  return result;
};

시간 비교

• 각각의 함수가 실행되는 시간을 비교해보니 아래와 같다.
  
• 개선식은 행 수에 영향을 받지 않는 반면, 기존식은 기하급수적으로 늘어나고 있었음..

느낀 점

이게 내가 만든 웹사이트에 필요한 계산이었다면 어떻게 됐을까? 조금만 값이 커져도 성능이 급격히 떨어지며 사용자들이 우수수 이탈했을 것이다 ㅠㅠ 불필요한 계산의 무서움을 알 수 있었던 경험이었다 ~! 단순히 기능이 어찌저찌 돌아가면 끝. 이 아니라 계속해서 문제점을 찾아서 개선해 나가야겠다고 다짐