99클럽 코테 스터디 21일차 TIL + 리트코드 동적계획법(DP)

 

- 오늘의 학습 키워드 : 동적계획법(다이나믹 프로그래밍?)

https://leetcode.com/problems/pascals-triangle/
- 공부한 내용 본인의 언어로 정리하기

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
    	result = []
        for i in range(numRows):
        	row = [1]*[i+1]
            for j in range(1,i):
            	row[j] = result[i-1][j-1] + result[i-1][j]
            result.append(row)
        return result

- 오늘의 회고
  - 오늘은 동적계획법. 그리디 문제 풀때 dp로 푸는방법을 누가 얘기해줬던거같은데 그때는 도대체 dp가 뭐야; 이랬는데 이게 그거였나보다.

DP는 하나의 큰 문제를 작은 문제로 나눠서 해결하는 기법을 의미하는데 보통 겹치는 부분이 많이 존재할때 사용하여 비효율성을 감소 + 메모리도 작게 사용하여 시간복잡도와 공간복잡도 해결가능하다.

- 참고로 이문제는 삼각형을 생각하기 보다는

예시 문제에 나오는 5를 기준으로

행 0: [1]
행 1: [1, 1]
행 2: [1, 2, 1]
행 3: [1, 3, 3, 1]
행 4: [1, 4, 6, 4, 1]

이런식으로 정렬해서 생각하면 더 생각하고 풀기 쉽지 않을까 싶다

 

그리고

 

왠지 내 삘로 내일은 피보나치 수열 문제가 나오지 않을까 싶다