$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}$을 바꾼 순서..
7월 말까지 알고리즘 문제를 열심히 풀다가 8월부터 슬럼프가 찾아왔다. 잠깐 손을 놓은 것 뿐인데 실력이 눈에 띄게 확 줄었다. 그동안 외부 대회도 몇 번 있었고 코드포스도 꽤 자주 했는데 만족스러운 결과는 하나도 없었다. ㅠㅠ.. 1. SCPC입상을 못했다. 1, 2를 풀고 3번 부분점수를 받았는데 커트라인 근처인 것 같다. 당시엔 3번을 풀지 못한 자괴감이 무척이나 컸는데 지금 생각해보면 그냥 못 풀 문제였던 것 같다. 코딩 실수도 지랄같이 해대는데 그냥 실력이 x밥인거지 뭐. 2. 카카오입상을 못했다. A, B, D번을 풀었고 C번을 잡다가 끝났다. C번을 못 푼게 좀 어이가 없었지만 풀었어도 입상 못했을거다. 카카오는 사실 입상 못한 건 상관이 없는데 인형을 못받아서 아쉬움이 크다. 내년에는 좀 ..
저번주 토요일(15일)에 SCPC 2차 예선이 있었는데 733점으로 본선에 가게 되었다. 개인적으로 2번 문제가 빡셌던 것 같다. 삼성전자 수학 경진대회인줄;; 1. Hanoi 제일 큰 원판부터 올바른 위치에 있는지 판단한다. 탑을 옮기는 시작 위치와 도착 위치에 따라 경우를 나눠서 판단했다. 1->2, 2->3, 3->1처럼 바로 오른쪽으로 옮기는 경우와 1->3, 2->1, 3->2처럼 한 칸 건너뛰는 경우로 나눠서 생각해보면 재귀적으로 해결할 수 있다. 2. 오래달리기 연립 합동식을 푸는 문제로 생각할 수 있다. 바로 중국인의 나머지 정리를 적용하고 싶었지만 mod가 쌍마다 서로소가 아니어서 애를 먹었다. 각각의 mod를 소인수로 분해함으로써 중국인의 나머지 정리를 적용할 수 있었다. 또한 계수의 ..
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[..