99클럽 코테 스터디 21일차 TIL : 동적계획법

마늘맨·2024년 8월 11일
0

99클럽 3기

목록 보기
21/42

Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊


[Challenger] 정수 삼각형

[정수 삼각형]

  • 두 가지 방법을 생각해볼 수 있다.

1. 꼭대기 → 바닥 갱신

  • 문제의 설명도 그렇고 가장 직관적이지만, 선택의 여지가 한 가지인 칸이 매 행마다 양 끝에 존재하기 때문에 따로 처리해주어야 해서 상대적으로 번거롭다.
dp[i][j]={dp[i][0]+dp[i1][0]j=0dp[i][j]+max(dp[i1][j1],dp[i1][j])for 1j<idp[i][i]+dp[i1][j1]j=idp[i][j] = \begin{cases} dp[i][0] + dp[i-1][0] & j=0 \\ dp[i][j] + \max(dp[i-1][j-1], dp[i-1][j]) & \text{for } 1 \le j < i \\ dp[i][i] + dp[i-1][j-1] & j=i \end{cases}

2. 바닥 → 꼭대기 갱신

  • 갱신 순서만 바꿔주면 점화식이 굉장히 깔끔해진다.
dp[i1][j]=dp[i1][j]+max(dp[i][j],dp[i][j+1])dp[i-1][j] = dp[i-1][j] + \max(dp[i][j], dp[i][j+1])

Solution 1. 꼭대기 → 바닥 갱신 O(n2)O(n^2)

def solution(dp):
    for i in range(1, len(dp)):
        dp[i][0] += dp[i-1][0]
        for j in range(1, i):
            dp[i][j] += max(dp[i-1][j-1], dp[i-1][j])
        dp[i][i] += dp[i-1][i-1]
    
    return max(dp[-1])

Solution 2. 바닥 → 꼭대기 갱신 O(n2)O(n^2)

def solution(dp):
    for i in range(len(dp)-1, 0, -1):
        for j in range(i):
            dp[i-1][j] += max(dp[i][j], dp[i][j+1])
    return dp[0][0]

Solution 2-2. 바닥 → 꼭대기 갱신 O(n2)O(n^2)

def solution(dp):
    for i in range(len(dp)-1, 0, -1):
        for j in range(i):
            dp[i-1][j] += dp[i][j] if dp[i][j]>dp[i][j+1] else dp[i][j+1]
    return dp[0][0]
  • Solution 2. 와 동일하지만, 조건부 표현식(삼항 연산자)이 max()에 비해 더 빠르다는 점을 이용하면 (가독성은 더 안좋아지지만) 더 빠르게 동작한다.

[Middler] 피보나치 수

[피보나치 수]

  • DP 입문 문제이니만큼, dp[i]=dp[i1]+dp[i2]dp[i] = dp[i-1]+dp[i-2]과 같이 dp table을 이용하는 방식 말고, “가장 최근의 두 값만을 이용해 새로운 값을 만든다”는 점에 주목하여 Integer 변수 두 개로 푸는 방법을 작성하였다.

Solution. O(n)O(n)

def solution(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, (a+b)%1234567
    return a
  • return a % 1234567 로 한 번에 mod\text{mod} 연산을 해 주는 것에 비해 매 반복마다 추가적으로 mod\text{mod} 연산이 수행되어 오히려 더 느릴 것처럼 보이지만, 수가 매우 커질 땐 중간중간 mod\text{mod} 연산을 해주는 것이 수를 작은 범위 안에 유지시켜주기 때문에 훨씬 빨라진다.
  • 다음 성질을 이용한다.
    (a+b)modm={(amodm)+(bmodm)}modm(a+b) \mod m = \{(a \mod m) + (b \mod m)\} \mod m
    Proof.
    • 임의의 정수 aamm으로 나눈 몫을 qaq_a, 나머지를 rar_a라고 하면, a=qam+raa = q_a\cdot m+r_a이다.
      • 여기에서 mod\text{mod} 연산의 정의에 따라 ra=amodmr_a = a \mod m이다.
    • 임의의 정수 bbmm으로 나눈 몫을 qbq_b, 나머지를 rbr_b라고 하면, b=qbm+rbb = q_b\cdot m+r_b이다.
      • 여기에서 mod\text{mod} 연산의 정의에 따라 rb=bmodmr_b = b \mod m이다.
    • 이 둘을 더하면,
      a+b=(qam+ra)+(qbm+rb)=(qa+qb)m+(ra+rb)a+b = (q_a\cdot m+r_a)+ ( q_b\cdot m+r_b) \\ = (q_a+q_b)\cdot m + (r_a+r_b)
    • 여기에서 나머지의 범위에 대해 생각해 보면,
      • ra+rb<mr_a+r_b <m인 경우
        • (a+b)modm=ra+rb(a+b) \mod m = r_a+r_b 가 성립한다.
      • ra+rbmr_a+r_b \ge m인 경우
        • 이 값이 나누는 수인 mm 이상이기 때문에, 이를 다시 mm으로 나눈 나머지는 (ra+rb)m(r_a+r_b) - m이므로 (qa+qb1)m+(ra+rb)(q_a+q_b-1)\cdot m + (r_a+r_b)이 되어, (a+b)modm=ra+rb(a+b) \mod m = r_a+r_b 가 여전히 성립한다.
profile
안녕! 😊

0개의 댓글