1주차 실력진단
두 수의 곱 문제를 풀다가 시간이 종료되어 끝나버렸다. 필요한 자료구조는 떠올랐는데 그 이후에 적용할 아이디어가 떠오르지 않았다. 다음에는 풀 수 있을 것 같다.
그리고 이번 실력진단 결과에 신뢰를 갖게 되었다. 그 이유는 Novice High 문제집은 모두 풀고 Intermediate Low는 풀다가 말았는데 추천 문제집도 IL이었다...
DP
DP는 Dynamic Programming의 약자로 동적계획법이라고 한다.
동적?
큰 문제를 작은 문제들로 나누어서 해결한 다음 큰 문제에 적용하는 알고리즘이다. 따라서 '동적'이라는 단어는 ‘문제의 크기를 바꾼다’로 이해하면 좋을 것 같다.
필수 요소
- 초기조건(작은 문제)
- 점화식(작은 문제로 큰 문제를 푸는 방법)
- DP테이블(Tabulation에서 사용)
Memoization vs. Tabulation
- Memoization: 탑다운 방식(높은 수에서 낮은 수로 내려가면서 해결)
- Tabulation: 바텀업 방식(낮은 수에서 높은 수로 올라가면서 해결)
- 시간복잡도는 동일. But, 탑다운 방식은 함수를 재귀적으로 실행 → 함수 처리에 추가 시간 소요
구현 방법
- DP 테이블 정의(difficult)
- 초기조건 삽입(not easy)
- DP 테이블 채우기: 점화식(hard)
- 문제의 정답 찾기
문제: 계단 오르기
문제의 조건은 매우 간단하다.
- 한 번에
2계단 혹은 3계단오를 수 있음
1. DP 테이블 정의
DP 테이블을 문제가 원하는 답에 맞게 정의해보면 아래와 같다
dp[i] := i층 높이의 계단에 올라가기 위한 서로 다른 수를 10,0007로 나눈 나머지
2. 초기조건 삽입
우선 1층은 올라갈 수 있는 방법이 없다. 따라서 dp[1] = 0이다.
0층에 대해서도 생각해보면 그대로 있는다는 의미에서 dp[0] = 1로 채워넣었다.
이유는 점화식을 세우는 과정에서 알 수 있다.
2층에 올라갈 수 있는 방법은 0층에서 2계단 오르는 한 가지 뿐이므로 dp[2] = 1.
dp[2]가 초기조건에 필요한 이유도 점화식에서 알 수 있다.
3. 점화식
현재 계단이 k층일 때 (k-2)층과 (k-3)층에서만 올라갈 수 있다. 이를 식으로 표현하면 점화식이 만들어 진다.
dp[i] = dp[i - 2] + dp[i - 3]
i = 2를 대입하면 dp[2] = dp[0] + dp[-1]이다. 파이썬에서는 음수 인덱스를 지원해서 오류가 나지는 않겠지만 의미 상 맞지 않으므로 dp[2] = 1을 초기조건에 넣어주었다. 마침 n의 하한도 2이기 때문에 문제되지 않는다.
i = 3에 대해서 생각해보면 dp[3] = dp[1] + dp[0]이다. dp[3]의 값이 1임을 확실하게 알 수 있고, dp[1]=0이므로 dp[0]의 값은 1로 설정하면 됨을 알 수 있다.
코드 구현
MOD = 10007
n = int(input())
dp = [0 for _ in range(n + 1)]
dp[0] = dp[2] = 1
for i in range(3, n + 1):
dp[i] = (dp[i - 3] + dp[i - 2]) % MOD
print(dp[n])
마무리
이번 주는 여행 계획이 있어 복습을 하는 느낌으로 dp를 공부했다. 다음 주에는 내가 개인적으로 가장 약하다고 생각하는 'Simulation'파트를 공부할 예정이다.
