📑 세부 학습 내용
📅 스케쥴
- 4시간 블로그 정리 및 자료 조사 + 1시간 코딩테스트 및 풀이 리뷰
- 총 5시간
🧷 학습 시간 인증
✍️ 자료조사 및 블로그 정리
1️⃣ 레디스 최악의 사례 7가지
2️⃣ 레디스 마스터-레플리카 레플리케이션
✏️ 코딩 테스트
- 1 SOLVE 및 깃허브 커밋
- 프로그래머스 -
12902 - 문제 유형 :
DP,점화식 사용,시뮬레이션/구현 - https://github.com/oneplast/ProgrammersCT/commit/6acafee7a491786692c8ba70622d8f4fb0f387e4
⭕ 문제 풀이
class Solution {
long[] dp;
static final long MOD = 1_000_000_007;
public int solution(int n) {
if (n % 2 != 0) {
return 0;
}
dp = new long[n + 1];
dp[0] = 1;
dp[2] = 3;
for (int i = 4; i <= n; i += 2) {
dp[i] = (4 * dp[i - 2] - dp[i - 4] + MOD) % MOD;
}
return (int) dp[n];
}
}
- 풀이 실패
- 세로 길이가 2일 때는 피보나치 수열을 사용하면 됐었지만, 지금처럼 3 이상인 경우 해결 방법을 도저히 생각하지 못함
- 정답 풀이 코드를 보고 이해해가며 코드 작성
- 솔직히 아직도 잘 모르겠음..
- 어떤 패턴들이 존재하지는 이해했으나, 실제 풀이 환경에서 점화식을 고안하고 지금처럼 더 사용하기 좋은 2차 점화식으로 변환할 수 있을 것 같지는 않음..
- 최대한 이런 문제의 풀이 패턴(공식)을 암기하는 게 나을 듯
- 세로 길이가 2인 직사각형에서 1x2 타일을 사용하면 마지막 자리 패턴 경우의 수를 생각하여 반영
- 마찬가지로 마지막 자리 패턴의 경우의 수는 가로 2칸을 차지하는 패턴 총 3개
- 점화식 3 * (dp[n - 2]) 생성
- 하지만 겹쳐야만 가능한 패턴 또한 존재
- col이 1 ~ 4 일 때, 2, 3 열이 합쳐지면 가능한 패턴 2개 존재
- 이를 짝 패턴이라고 임시 표현
- 짝 패턴은 n - 2 일 때마다 존재 가능하며, 연속해서는 불가능
- ex) n - 2, n - 4가 동시에 짝일 수는 없음
- 짝 패턴의 경우 열 4개의 패턴이 모두 정해져있음
- 짝 패턴은 이어지는 경계선을 침범하지 않음
- 따라서 2 * (dp[i - 4] + dp[i - 6] ...) 의 점화식 생성
- col이 1 ~ 4 일 때, 2, 3 열이 합쳐지면 가능한 패턴 2개 존재
- 총 점화식 생성 : 3 (dp[n - 2]) + 2 (dp[i - 4] + dp[i - 6] ...)
- dp[n - 2] 를 dp[n] 으로 잡고 점화식 풀이하면 2차 점화식 생성 가능
- 2차 점화식 4 * dp[n - 2] - dp[n - 4]
MOD로 나눌 때 정답 처리가 되지 않아, 해당 점화식에 + MOD를 반영한 후MOD로 나누니 해결- 최종 시간복잡도 : O(N)
- 1차 반복문 : O(N)
- 최종 시간복잡도 : O(N)
기록