99클럽 TIL (240812)

> [Middler] 멀리 뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914

 

걸린 시간 : 12분

 

문제 풀이 과정

DP는 점화식을 구한다면 빠르게 해결할 수 있는 문제유형이다. 때문에 n번째와 n-1번째 값에 대해서 어떠한 관계성이 있는지 알아내려고 했다. 계산을 해보니 아래와 같은 점화식을 구할 수 있었다.

 

문제 풀이

1. python

위의 점화식을 코드로 나타내면 아래와 같다.

def solution(n):
    d = [0, 1, 2]
    
    for i in range(3, n+1) :
        d.append((d[i-1] + d[i-2]) % 1234567)
        
    return d[n]

 

2. javascript

파이썬과 동일

 

시간복잡도 O(N)

 

오늘의 회고 및 느낀 점

수열의 N번째 항과 다른 항들 간의 관계에 대해서 알아내는 것이 중요!

 

---

 

> [beginner] Pascal's triangle 2

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

 

걸린시간 : 30분

 

문제 풀이 과정

동일하게 DP로 풀었다. rowIndex 까지 for loop로 순회하면서 해당 index보다 -1 만큼 반복하며 temp를 생성해서 배열을 만들어주었다. 점화식을 정확히 어떻게 정의해야할지는 모르겠지만, 첫번째 원소와 마지막 원소인 1을 제외하고 사이에 index -1 만큼 temp 에 d[i-1] + d[i+2]을 반복해주었다.

 

💡알고가면 좋은 지식 : 파스칼의 삼각형

이항계수를 삼각형 모양으로 나열한 것으로 곱셈공식의 계수와 동일한 모습을 띈다. (특징)

문제 풀이

1. python

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        d = [1, 1]

        for i in range(2, rowIndex+1) :
            temp = [1]
            for j in range(i-1) :
                temp.append(d[j]+d[j+1])
            temp.append(1)
            d = temp
        
        if rowIndex < 1 :
            return [d[rowIndex]]
        else :
            return d

 

시간복잡도 O(N)

rowIndex 범위가 최대 33이므로 정상동작한다.

 

오늘의 회고 및 느낀 점

위의 내용보다 효율적인 동작방법을 알게된다면 다시 기록해야겠다.