📑 세부 학습 내용

📅 스케쥴

• 3시간 독서 + 궁금한 개념 조사 및 학습 + 1시간 코딩테스트 및 풀이 리뷰
• 총 4시간
  
  

🧷 학습 시간 인증

📖 도서 정독 및 실습

실전 레디스 : 기초, 실전, 고급 단계별로 배우는 레디스 핵심 가이드

• 캐싱 등 RDB 의 보조 역할을 해줄 NoSQL 중 가장 범용적이고 유지보수가 잘 진행 중인 Redis 의 구조부터 기초, 심화 내용, 사용법 등을 확실하게 이해하여, 이후의 프로그래밍에 있어 자신 있고 근거 있게 레디스를 채택하고 사용할 수 있는 개발자를 목표로 독서 시작
• 5.1 데이터 영속성 (p.306) ~ 5.2.2 쓰기 관점 아키텍처 (p.334)
• 도서 내 모든 내용 이해 및 실습 완료
  • 궁금한 부분은 따로 조사 후 학습
    
    

✏️ 코딩 테스트

• 1 SOLVE 및 깃허브 커밋
• 프로그래머스 - 42897
  • https://school.programmers.co.kr/learn/courses/30/lessons/42897
• 문제 유형 : DP , 시뮬레이션/구현
• https://github.com/oneplast/ProgrammersCT/commit/a749750a6cf40af8a23acf7bfbf46abfc00edb21

⭕ 문제 풀이

class Solution {

    int n;

    public int solution(int[] money) {
        n = money.length;

        int[] dp1 = new int[n];
        dp1[0] = money[0];
        dp1[1] = Math.max(money[0], money[1]);
        solve(money, dp1, 2, n - 1);

        int[] dp2 = new int[n];
        dp2[0] = 0;
        dp2[1] = money[1];
        solve(money, dp2, 2, n);

        return Math.max(dp1[n - 2], dp2[n - 1]);
    }

    private void solve(int[] money, int[] dp, int start, int end) {
        for (int i = start; i < end; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + money[i]);
        }
    }
}

• 풀이 실패
  • 효율성 테스트를 통과할만한 아이디어를 떠올리지 못함
    • 생각한 아이디어는 DP 를 각 money 인덱스에서 가져올 수 있는 최대값을 저장하고 꺼내쓰는 용도로 사용하는 것
    • 조건을 딱 끊기 어려워 무한 루프 발생 가능
    • 효율성 면에서도, 최악의 경우 O(n²)의 시간복잡도 발생
  • 아이디어를 도움 받아 구현
• DP 를 인덱스별 최대 보관 가능 값이 아닌, 인덱스까지의 최대 보관 값으로 사용
• 첫 집을 털고 마지막 집을 안 턴 경우와 첫 집을 안 털고 마지막 집을 턴 경우로 분기
  • 두 번째 집부터는 이전 집을 턴 경우(이전 집의 최대값)와 이전 집을 안 턴 경우(전전 집의 최대값 + 현재 집의 값)
  • 첫 집을 턴 경우 -> 마지막 집이 인접하므로 털 수 없음
  • 첫 집을 안 턴 경우 -> 마지막 집도 털 수 있으므로 끝까지 확인
• 최종 시간복잡도 : O(N)
  • DP 기록 위한 반복문 : O(N)
  • 최종 시간복잡도 : O(N)

---

💡 어려웠던 것 || 알게 된 것

• 금일은 없음