증가하는 삼각형이란?
이 문제에서 다루는 '증가하는 삼각형'은 아래와 같은 형태입니다.
1
2 3
4 5 6
7 8 9 10
삼각형은 위에서부터 아래로 행(row)이 하나씩 늘어나며, 각 행에는 자연수가 왼쪽부터 오른쪽으로 순서대로 채워집니다. 첫 번째 행에는 1개, 두 번째 행에는 2개, 세 번째 행에는 3개의 숫자가 들어가는 식입니다.
문제 정의
숫자 n을 입력받아 증가하는 삼각형의 n번째 행에 있는 모든 숫자의 합을 반환하는 JavaScript 함수를 작성해야 합니다.
접근 방법
가장 직관적인 방법은 삼각형 전체를 2차원 배열로 만든 뒤, 원하는 행을 꺼내 합계를 구하는 것입니다. 바깥 반복문으로 각 행을 생성하고, 안쪽 반복문으로 해당 행에 들어갈 숫자들을 차례대로 채워 넣습니다.
예제 코드
다음은 이를 구현한 코드입니다.
const num = 15;
const rowSum = (num = 1) => {
const arr = [];
const fillarray = () => {
let num = 0;
for(let i = 1; i <= 10000; i++){
const tempArr = [];
for(let j = 0; j < i; j++){
num++;
tempArr.push(num);
};
arr.push(tempArr);
};
};
fillarray();
return arr[num-1].reduce((a, b)=>a + b, 0);
};
console.log(rowSum(num));
출력 결과
1695
동작 원리 설명
코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.
1단계: fillarray() 함수가 호출되어 1행부터 10,000행까지의 삼각형 데이터를 미리 생성합니다. 변수 num은 0에서 시작하며, 각 숫자를 채울 때마다 1씩 증가합니다.
2단계: 바깥 반복문(i)은 행 번호를 결정하고, 안쪽 반복문(j)은 그 행에 들어갈 숫자의 개수만큼 값을 채웁니다. 예를 들어 4번째 행에는 7, 8, 9, 10이 순서대로 저장됩니다.
3단계: 삼각형이 완성되면 arr[num-1]로 n번째 행(배열 인덱스는 0부터 시작하므로 n-1)을 가져온 뒤, reduce() 메서드를 사용해 해당 행의 모든 숫자를 더해 반환합니다.
입력값이 15일 경우, 15번째 행은 106부터 120까지의 15개 숫자로 이루어져 있으며, 이들의 합은 1695가 됩니다.
더 효율적인 방법: 수학 공식 활용
위 방법은 삼각형 전체를 미리 만들어야 하므로 메모리와 시간이 많이 소요됩니다. 사실 수학적 규칙을 이용하면 반복 없이 한 번의 계산으로 답을 구할 수 있습니다.
n번째 행의 마지막 숫자는 삼각형의 처음부터 n번째 행까지의 숫자 개수인 n(n+1)/2입니다. n번째 행은 연속된 n개의 숫자로 이루어지므로, 등차수열의 합 공식을 적용하면 다음과 같습니다.
const rowSum = (n = 1) => {
const lastNum = n * (n + 1) / 2; // n번째 행의 마지막 숫자
const firstNum = lastNum - n + 1; // n번째 행의 첫 번째 숫자
return ((firstNum + lastNum) * n) / 2;
};
console.log(rowSum(15)); // 1695이 방식은 O(n²)의 시간 복잡도를 가진 배열 생성 방식과 달리 O(1)의 상수 시간에 결과를 얻을 수 있어, 매우 큰 n 값에 대해서도 즉시 계산이 가능합니다.
마무리
증가하는 삼각형의 n번째 행 합을 구하는 문제는 배열을 직접 생성하는 방법과 수학 공식을 활용하는 방법 두 가지로 해결할 수 있습니다. 작은 입력값이라면 배열 방식도 충분하지만, 성능이 중요한 환경에서는 공식 기반 접근이 훨씬 유리합니다. 상황에 맞는 방법을 선택해 활용해 보시기 바랍니다.