단조 큐를 이용한 동적 계획법 최적화 기법
단조 큐를 통한 동적 계획법 최적화 개요
단조 큐는 특정 조건 하에서 무의미한 후보를 빠르게 제거함으로써 상태 전이의 효율을 높이는 강력한 기법이다. 특히, 결정의 범위가 항상 증가하거나 감소하는 경우, 즉 윈도우 크기가 고정되거나 단조롭게 변할 때 효과적이다. 이는 일반적으로 슬라이딩 윈도우 문제로 모델링 가능하며, 대부분의 최적화 패턴은 이 구조에 근 ...
8월 5일 20:39에 게시됨
스택과 큐를 활용한 자료 구조 문제 해결 전략
스택과 큐는 컴퓨터 과학에서 가장 기본적이고 널리 사용되는 선형 자료 구조입니다. 이 두 가지 구조는 데이터를 저장하고 접근하는 방식에 있어 명확한 차이를 가지며, 다양한 알고리즘 문제 해결에 필수적인 도구로 활용됩니다. 스택은 '후입선출(LIFO: Last In, First Out)' 원칙을 따르며, 큐는 '선입선출(FIFO: First In, First Out)' 원칙을 따릅니다. 특히 스택은 ...
7월 25일 13:02에 게시됨
CSP2019 Day2T2 분할 최적화
기본적인 동적계획법 접근은 dp[i][j]를 마지막 분할 지점이 i, 이전 분할 지점이 j일 때의 최소 비용으로 정의한다. 누적합을 sum[i] = Σk=1i a[k]로 두면, 전이식은 다음과 같다:
dp[i][j] = min{ dp[j][k] + (sum[i] - sum[j])² }
( sum[i] - sum[j] ≥ sum[j] - sum[k] )
조건를 정리하면 sum[k] ≥ 2×sum[j] - sum[i]가 되며, 고정된 j에 대해 i가 증가함에 따라 하한 ...
7월 7일 02:24에 게시됨