구사과

4. Knuth's Optimization Recurrence: $DP[i][j] = Min_{i \le k < j}(DP[i][k] + DP[k + 1][j] + C[i][j])$ Condition: $C[i][j]$ is a Monge array, and satisfies $C[a][d] \ge C[b][c]$ for $a \le b \le c \le d$. Naive Complexity: $O(n^3)$ Optimized Complexity: $O(n^2)$ Knuth Optimization은 어떠한 구간을 쪼개는 형태의 동적 계획법을 최적화한다. Optimal Binary Search Tree 라고 알려진 문제를 Knuth가 $O(n^2)$ 동적 계획법으로 해결할 때 사용되었기 때문에 Knuth의..

동적 계획법(DP) 알고리즘의 시간 복잡도를 줄이는 기법에 대해서는 다양한 프로그래밍 대회에서 많이 출제된 바가 있다. 이러한 알고리즘은 굉장히 아름다운 방법으로 시간 복잡도를 줄이기 때문에 다양한 대회에서 인기가 많으나, 실제로 표준적인 알고리즘 교과서나 입문서에서 배우기는 힘든 내용이라 초심자가 시작하기 힘든 것이 단점이다. 현재 동적 계획법 최적화에 대해서 배울 수 있는 인터넷 자료들은 대부분 최신 자료가 아니기 때문에, 내가 알고 있는 동적 계획법 최적화 기법을 모두 소개함으로써 이 분야의 지식 격차를 줄이는 데 도움을 주려 한다. 이 글을 읽을 때는 이 최적화 기법들이 단순히 동적 계획법에만 국한되어 있지 않다는 점을 유의하는 것이 좋다. 예시 문제로 올라와 있는 문제들도 동적 계획법과 상관이 ..

NEERC Northern Subregional 2015 A. Alex Origami Squares 일반성을 잃지 않고 $w \le h$ 라고 합시다. 두 가지 케이스가 있습니다: 세로로 길게 3개의 색종이를 늘어놓는 것. ㄴ자 모양으로 색종이 3개를 늘어놓는 것. 각 케이스에 대한 색종이의 길이는 단순 비교 연산과 나눗셈으로 계산 가능합니다. NEERC Northern Subregional 2015 J. Journey to the “The World’s Start” 먼저 몇 가지 사실을 짚고 넘어갑시다. 문제에는 출발지 방향으로 역행해도 된다고 되어 있으니, 굳이 역행을 해서 도움이 되는 경우는 없고, 목적지 방향으로 계속 움직이면 됩니다. 목적지 방향으로 계속 움직일 것이니, 이동에는 무조건 정확히 ..