$ax+by+c\geq 0$ 꼴로 표현되는 반평면을 생각해 보자. 이러한 반평면이 여러 개 모이면 아래 진한 부분처럼 볼록 다각형 모양의 교집합이 만들어진다. (편의상 모든 반평면의 경계선 기울기는 서로 다르다고 가정하자.) 반평면들의 교집합을 구하는 알고리즘에 대해 살펴보겠다. 1. $O(n^3)$ 관찰해보면, 교집합의 꼭짓점은 항상 두 경계선의 교점에 해당한다는 것을 알 수 있다. 따라서 모든 경계선 쌍의 교점을 후보로서 탐색한다. $O(n^2)$ 교집합에 포함되려면 모든 반평면 부등식($a_ix^{*}+b_iy^{*}+c_i\geq 0$)을 만족해야 하므로, 각각의 교점에 대해 $n$개의 부등식을 조사한다. $O(n)$ 그러므로 총 시간복잡도는 $O(n^3)$이다. 구현이 매우 직관적이고 쉽기 때문..
가끔 PS에서 $n$개 중 몇 개를 골라 특정 값을 최대 혹은 최소화하는 문제가 나타난다. 대표적으로 냅색 문제가 있는데, 보통 냅색을 풀 때 "$1$ ~ $i$번 물건을 고려한 최대/최솟값"과 같이 DP식을 정의한다. 즉 각각의 물건은 $1$번부터 $n$번까지 "순서"를 매길 수 있고, 어떤 순서로 정하든 최종적인 답에는 영향을 주지 않는다. 직관적으로는 당연할 수 있지만 이게 왜 가능한지 생각해 보자. 먼저 임의의 순서대로 물건에 $1$ ~ $n$번까지 번호를 매겼다고 가정하자. 이제 냅색의 솔루션이 되는 임의의 선택 순서 $a_1, a_2, ..., a_m$을 생각하자($a_i$는 물건의 번호이다). 만약 $a_i > a_{i+1}$인 $i$가 존재한다면, $a_i$와 $a_{i+1}$을 바꾼 순서..
https://www.acmicpc.net/problem/1126 $dp[i][j] = 1 $~ $i$번 토막으로 높이가 $h1, h2$이고 $h1 - h2 = j$인 탑을 만들었을 때 $h1$의 최댓값(단, $h1 >= h2 >= 0$) $i$번째 토막을 포함하는경우 / 포함하지 않는 경우로 나누면 위 점화식을 해결할 수 있다. $dp[i][j]$를 계산하는 상황을 생각해보자. $i$번째 토막을 포함하지 않는다면 $dp[i][j] = dp[i-1][j]$이다. $i$번째 토막을 포함한다면 $h1$에 포함되는 경우와, $h2$에 포함되는 경우로 나눌 수 있다. 먼저 $h2$에 포함되는 경우 $dp[i][j] = dp[i-1][j+h[i]]$이다. $h1$에 포함되는 경우는 다시 두 경우로 나뉜다. $h[..