Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊
[Challenger] 정수 삼각형
[정수 삼각형]
1. 꼭대기 → 바닥 갱신
- 문제의 설명도 그렇고 가장 직관적이지만, 선택의 여지가 한 가지인 칸이 매 행마다 양 끝에 존재하기 때문에 따로 처리해주어야 해서 상대적으로 번거롭다.
dp[i][j]=⎩⎪⎪⎨⎪⎪⎧dp[i][0]+dp[i−1][0]dp[i][j]+max(dp[i−1][j−1],dp[i−1][j])dp[i][i]+dp[i−1][j−1]j=0for 1≤j<ij=i
2. 바닥 → 꼭대기 갱신
- 갱신 순서만 바꿔주면 점화식이 굉장히 깔끔해진다.
dp[i−1][j]=dp[i−1][j]+max(dp[i][j],dp[i][j+1])
Solution 1. 꼭대기 → 바닥 갱신 O(n2)
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)
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)
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[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
로 한 번에 mod 연산을 해 주는 것에 비해 매 반복마다 추가적으로 mod 연산이 수행되어 오히려 더 느릴 것처럼 보이지만, 수가 매우 커질 땐 중간중간 mod 연산을 해주는 것이 수를 작은 범위 안에 유지시켜주기 때문에 훨씬 빨라진다.
- 다음 성질을 이용한다.
(a+b)modm={(amodm)+(bmodm)}modm Proof.
- 임의의 정수 a를 m으로 나눈 몫을 qa, 나머지를 ra라고 하면, a=qa⋅m+ra이다.
- 여기에서 mod 연산의 정의에 따라 ra=amodm이다.
- 임의의 정수 b를 m으로 나눈 몫을 qb, 나머지를 rb라고 하면, b=qb⋅m+rb이다.
- 여기에서 mod 연산의 정의에 따라 rb=bmodm이다.
- 이 둘을 더하면,
a+b=(qa⋅m+ra)+(qb⋅m+rb)=(qa+qb)⋅m+(ra+rb)
- 여기에서 나머지의 범위에 대해 생각해 보면,
- ra+rb<m인 경우
- (a+b)modm=ra+rb 가 성립한다.
- ra+rb≥m인 경우
- 이 값이 나누는 수인 m 이상이기 때문에, 이를 다시 m으로 나눈 나머지는 (ra+rb)−m이므로 (qa+qb−1)⋅m+(ra+rb)이 되어, (a+b)modm=ra+rb 가 여전히 성립한다.