99클럽 코테 스터디 18일차 TIL(6월 7일) + 알고리즘 DP(Dynamic Programing,동적계획법)

[문제 링크]

https://leetcode.com/problems/pascals-triangle/

 

[문제 사고]

주어진 규칙에 맞게 반복하며 이중 배열을 생성한다.

 

[문제 해결]

1. 정답으로 반환할 빈 배열을 선언한다.
2. 주어진 numRows만큼 반복문을 돌며 각 인덱스 별로 빈 배열을 부여해준다.
3. 인덱스 별 빈 배열의 첫번째 요소와 마지막 요소는 1을 넣어준다.
4. 이중 반복문을 돌며 인덱스 별 배열의 각 인덱스에 전 배열에서의 현재 인덱스와 이전 인덱스 값을 더하여 현재 배열의 현재 인덱스 값을 구해낸다.(파스칼법칙)
5. 이중 반복문을 1부터 돌며 정답에 해당하는 배열을 반환한다.

 

[작성 코드]

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    const answer = [];
    for(let i = 0; i < numRows; i++){
        answer[i] = [];
        answer[i][0] = 1;
        answer[i][i] = 1;
        for(let j = 1; j < i; j++){
            answer[i][j] = answer[i-1][j-1] + answer[i-1][j]
        }
    }
    return answer
}

 

[문제 회고]

파스칼 법칙에 대해 이해를 하고 있었기에 문제를 풀어내는 방식을 떠올리는데에 오랜 시간이 걸리지는 않았다. 하지만 구현에 있어서 이중 반복문을 사용하지 않고 정답을 이끌어 내는 방식을 고민하다가 실패하고 이중 반복문을 사용했다. 이중 반복문 없이 구현하는 방법을 생각해 내어 시간 복잡도를 낮출 수 있는 방식을 고민해보아야겠다.