99클럽 코테 스터디 21일차 TIL Pascal's Triangle

# 오늘의 학습 키워드 

동적계획법

 

# 오늘의 문제 

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

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

 

 

Example 1:

Input: numRows = 5

Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1

Output: [[1]]

 

# 나의 풀이방식 

class Solution {
    public List<List<Integer>> generate(int numRows) {

        List<List<Integer>> answer = new ArrayList<>();

        //numRows행만큼 answer반복 
        for(int i =0; i<numRows; i++){
            List<Integer> list = new ArrayList<>();

            //list의 첫번째 또는 마지막 인덱스인 경우 무조건 1, 그 외 answer 직전 값들을 더한 수
            for(int j=0; j<i+1; j++){
            
                if(j == 0 || j == i){
                    list.add(1);
                }else{
                    list.add(answer.get(i-1).get(j-1) + answer.get(i-1).get(j));
                }
            }

            answer.add(list);
        }

        return answer;
        
    }
}

 

 

# 오늘의 공부 

동적계획법(Dynamic Programming, DP)이란 ? 

- 동적계획법은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임

- 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하는 방식으로 '기억하며 풀기'라고 부르기도 한다.

 

DP가 적용되기 위한 2가지 조건은?

- 겹치는 부분 문제 : 동일한 작은 문제들이 반복하여 나타나는 경우 

- 최적 부분 구조 : 부분문제의 최적 결과값을 사용해 문제의 최적 결과를 낼 수 있는 경우

 

# 오늘의 회고 

문제 풀기전에 "동적계획법"이 뭐지? 하면서 풀었는데 문제를 풀고 개념을 공부하다보니 평소에 풀던 방식이 동적계획법 방식으로 어디든 끼워맞추려고 했었구나 라는 생각이 들었다.