[PS 일지] 2024-01-07

루트삼·2024년 1월 7일

DP 문제 해결
✔ 13976 | Platinum 5 | 타일 채우기 2
ㄴ 타일 채우기에서 구했던 점화식을 분할 정복 거듭제곱으로 활용하기만 하면 되는 문제.
골드 랜덤 디펜스
✔ 10830 | Gold 4 | 행렬 제곱
ㄴ 분할 정복을 이용한 행렬 제곱의 기초 문제.
✔ 11444 | Gold 2 | 피보나치 수 6
ㄴ $\begin{bmatrix}1 & 1 \\ 1 & 0 \end{bmatrix} ^ {N-2}* \begin{bmatrix}F_{2} \\ F_{1} \end{bmatrix}$ 처음에 뒤의 행렬을 1차원으로 잘못 만들어서 조금 헤맸다.
✔ 2749 | Gold 2 | 피보나치 수 3
ㄴ 피보나치 6과 완전히 똑같은 문제길래 의아했는데, 다른 사람들의 풀이를 보고 나서 mod가 $10^{6}$ 으로 충분히 작으므로 피사노 주기라는 걸 이용할 수 있다는 걸 알게 되었다.
✔ 13075 | Gold 2 | Fibonacci Sequence
ㄴ 피보나치 6과 동일한 문제.
새로운 알고리즘 공부
분할 정복을 이용한 거듭제곱을 행렬에 이용한 코드와 DP에서의 응용을 배웠다. 사실 오늘 배운 건 아니고 세특 발표를 준비하면서 개념은 모두 익혀두었는데 구현하기가 귀찮아서 미뤄두고 있었을 뿐이다. 어쨌든 구현했으니 앞으로 벌러캠프랑 같이 요긴하게 써먹어야겠다.

안녕하세요.