열쇠를 누가 가졌는지 추적하는 문제가 집합의 교집합 조건 한 줄로 내려앉습니다. 초기 조건 한 줄이 선언하는 "가상의 -1열"을 짚고, 예제를 전탐색으로 전수 검증하며, 배낭과 달리 세는 DP에서 답을 왜 합으로 읽는지 정리합니다. 부원이 K명으로 늘면 어디가 터...
각 글자의 등장 횟수를 곱하면 8, 정답은 4입니다. 그 차이가 어디서 나는지 진짜 예제로 끝까지 따라가며, 부분수열을 세는 DP가 순서 조건을 어떻게 자동으로 처리하는지 봅니다. 본편이 강조한 역순 갱신이 이 문제에서는 왜 없어도 통과하는지, 언제부터 진짜 필요...
배낭 문제에서 시간을 잡아먹는 것은 점화식이 아니라 그 주변의 판단들입니다. 답을 마지막 행 전체에서 읽는 이유, 1차원 롤링의 루프 방향이 0-1과 무한 개수 배낭을 가르는 지점, 고른 품목의 복원, EDPC E의 첨자 맞바꾸기를 예제 표로 확인합니다.
배낭 문제로 "앞에서 i개" 부분 문제를 복습하고, 부족한 정보를 첨자로 부가해 나가는 동적 계획법의 뼈대를 세 개의 예제로 확인합니다.
이분 탐색 + DP를 활용한 '평균값 최대화 · 중앙값 최대화' 문제(Average and Median, ABC236 · E문제)의 풀이를 9단계로 나누어 코드를 점진적으로 완성합니다.
이분 탐색 및 いもす法을 활용한 '최솟값의 최대화' 문제(棒の出荷, 제5회 PAST · M문제)의 풀이를 9단계로 나누어 코드를 점진적으로 완성합니다.
이분 탐색 적용 문제(おまかせ, 제1회 PAST · M문제)의 풀이를 총 7단계로 나누어 코드를 점진적으로 완성합니다.
판정 문제와 단조성을 활용한 최솟값 최대화, 평균값 및 중앙값 최대화 등 고급 이분 탐색 테크닉에 대하여 이야기합니다.
Kamil Lee의 개발 일기
![[PAST] Part 2 보충 — 部活のスケジュール表 문제 풀이](https://kamillee0918.blog/rails/active_storage/representations/proxy/eyJfcmFpbHMiOnsiZGF0YSI6Nzk5LCJwdXIiOiJibG9iX2lkIn19--d2cb14b5ff23b8973c15041d43c41ebe12284b15/eyJfcmFpbHMiOnsiZGF0YSI6eyJmb3JtYXQiOiJ3ZWJwIiwicmVzaXplX3RvX2xpbWl0IjpbMTAyNCxudWxsXSwic2F2ZXIiOnsicXVhbGl0eSI6ODB9fSwicHVyIjoidmFyaWF0aW9uIn19--b3988f5225cb132d14f3c064663acfc916ff5ee6/part2.png)
![[PAST] Part 1.3 — Average and Median 풀이](https://kamillee0918.blog/rails/active_storage/representations/proxy/eyJfcmFpbHMiOnsiZGF0YSI6NTk3LCJwdXIiOiJibG9iX2lkIn19--d02444217d96fef0a0cdc908eeb99bc460c5243b/eyJfcmFpbHMiOnsiZGF0YSI6eyJmb3JtYXQiOiJ3ZWJwIiwicmVzaXplX3RvX2xpbWl0IjpbMTAyNCxudWxsXSwic2F2ZXIiOnsicXVhbGl0eSI6ODB9fSwicHVyIjoidmFyaWF0aW9uIn19--b3988f5225cb132d14f3c064663acfc916ff5ee6/part1.png)