구사과

동적 계획법(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” 먼저 몇 가지 사실을 짚고 넘어갑시다. 문제에는 출발지 방향으로 역행해도 된다고 되어 있으니, 굳이 역행을 해서 도움이 되는 경우는 없고, 목적지 방향으로 계속 움직이면 됩니다. 목적지 방향으로 계속 움직일 것이니, 이동에는 무조건 정확히 ..

Motivation 계산기하에서 장애물을 포함하지 않는 가장 큰 도형을 찾는 것은 핵심적인 문제 중 하나이다. 다양한 거리계, 그리고 도형의 모양에 따라서 서로 다른 알고리즘들이 존재한다. 예를 들어서, 다음과 같은 문제들을 생각할 수 있다. A) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으며 넓이가 가장 큰 원은 무엇인가? B) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으며 넓이가 가장 큰 직사각형은 무엇인가? C) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으면서 $x, y$ 축에 평행한 가장 큰 정사각형은 무엇인가? D) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으면서 $x, y$ 축에 평행하고, 한 변이 $x$ 축에 포함되는 가장 큰 직사각형은 무엇인가? E) $..