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

---

[Challenger] 정수 삼각형

[정수 삼각형]

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

1. 꼭대기 → 바닥 갱신

• 문제의 설명도 그렇고 가장 직관적이지만, 선택의 여지가 한 가지인 칸이 매 행마다 양 끝에 존재하기 때문에 따로 처리해주어야 해서 상대적으로 번거롭다.

2. 바닥 → 꼭대기 갱신

• 갱신 순서만 바꿔주면 점화식이 굉장히 깔끔해진다.

Solution 1. 꼭대기 → 바닥 갱신 $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(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(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()에 비해 더 빠르다는 점을 이용하면 (가독성은 더 안좋아지지만) 더 빠르게 동작한다.
  • 특히 이 문제에서는, $n(n+1)/2$번의 max() 호출이 일어나므로 그 차이가 두드러진다.
  • 예전에 알아보고 정말 신기해서 남긴 글이 있다! 소요시간 배틀 : 내장함수 vs 조건부 표현식

---

[Middler] 피보나치 수

[피보나치 수]

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

Solution. $O(n)$

def solution(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, (a+b)%1234567
    return a

• return a % 1234567 로 한 번에 $\text{mod}$ 연산을 해 주는 것에 비해 매 반복마다 추가적으로 $\text{mod}$ 연산이 수행되어 오히려 더 느릴 것처럼 보이지만, 수가 매우 커질 땐 중간중간 $\text{mod}$ 연산을 해주는 것이 수를 작은 범위 안에 유지시켜주기 때문에 훨씬 빨라진다.
• 다음 성질을 이용한다.
  $(a+b) \mod m = \{(a \mod m) + (b \mod m)\} \mod m$
  Proof.
  • 임의의 정수 $a$를 $m$으로 나눈 몫을 $q_a$, 나머지를 $r_a$라고 하면, $a = q_a\cdot m+r_a$이다.
    • 여기에서 $\text{mod}$ 연산의 정의에 따라 $r_a = a \mod m$이다.
  • 임의의 정수 $b$를 $m$으로 나눈 몫을 $q_b$, 나머지를 $r_b$라고 하면, $b = q_b\cdot m+r_b$이다.
    • 여기에서 $\text{mod}$ 연산의 정의에 따라 $r_b = b \mod m$이다.
  • 이 둘을 더하면,
    $a+b = (q_a\cdot m+r_a)+ ( q_b\cdot m+r_b) \\ = (q_a+q_b)\cdot m + (r_a+r_b)$
  • 여기에서 나머지의 범위에 대해 생각해 보면,
    • $r_a+r_b <m$인 경우
      • $(a+b) \mod m = r_a+r_b$ 가 성립한다.
    • $r_a+r_b \ge m$인 경우
      • 이 값이 나누는 수인 $m$ 이상이기 때문에, 이를 다시 $m$으로 나눈 나머지는 $(r_a+r_b) - m$이므로 $(q_a+q_b-1)\cdot m + (r_a+r_b)$이 되어, $(a+b) \mod m = r_a+r_b$ 가 여전히 성립한다.