티스토리 뷰

공부

Convex Hull Trick

구사과 2014.08.10 19:24

일부 dp문제에서 시간복잡도를 획기적으로 줄여주는 걸로 유명한 테크닉입니다. 이번에 koi 2014 전국본선 3번으로 나왔으니 인지도가 더 올라갈 거 같네요.


개략적으로 설명하자면

문제를 풀다가 이런 형태의 점화식이 나올 때는 보통 n^2 말고는 희망이 없는데

이걸 이런 식으로 해석하면 기울기와 절편이 j에 따라 결정되는 형태의 일차함수들로 해석할수 있게 됩니다.

이러면 저러한 dp식을 구할때

(dp[0] = 0)

1. 0번 선분을 넣는다 (기울기 = b[0]. 절편 = dp[0])

2. 현재 들어간 선분 중 최솟값을 찾는다 (dp[1])

3. 1번 선분을 넣는다 (기울기 = b[1]. 절편 = dp[1])

4. 현재 들어간 선분 중 최솟값을 찾는다 (dp[2])

......

즉,

 * dp[i]를 구하고

 * 선분을 넣어주는

연산을 O(1)이나 O(lgn)에 할 수 있는 자료구조가 있으면 시간복잡도 향상을 꾀할 수 있습니다.


이 때 convex hull trick은 저 작업들을 모조리 O(lgn)만에 할 수 있습니다.

뿐만 아니라 a[i] < a[i+1]일 경우에는 O(1)만에 해버릴 수도 있습니다. (사실 스위핑이라서 정확히 O(1)은 아닙니다. 그냥 O(n/n)..)


달리 할말이 없네요... 나머지는 코드포스 어셉먹인 소스코드로 대체하겠습니다.

source code 

(저 문제의 점화식은 맨 위에 적어놓은 것과 똑같습니다. 상대적으로 쉬운 문제라서 그렇고 보통 약간의 변형을 거쳐야 저러한 점화식이 나오는 경우가 많습니다)


그 외에 연습할 수 있는 문제가 여럿 있으니 참고하세요

http://koistudy.net/?mid=prob_page&NO=355 (IOI 02 Batch Scheduling)

http://koistudy.net/?mid=prob_page&NO=2046 (USACO Gold Mar 08 Land Acquisition)

APIO'10 Commando

APIO'14 Sequence


댓글
  • 프로필사진 지나가던곰 오 뭔가 신기하네요 ㅋㅋㅋㅋㅋㅋ 2015.09.30 21:06 신고
  • 프로필사진 kalmiaa 쿠사가님, KOI 몇번 문제였는지 알 수 있을까요?
    2014년 백준에서 다 풀었는데, 고등부 3, 4번 문제가 삭제돼서 없네요.
    혹시 3~4번중 하나일까요?
    2016.07.23 11:30 신고
  • 프로필사진 구사과 답변이 아주 많이 늦었네요 ㅠㅠ

    KOI 2014 고등부 3번이며 백준엔 없고 이 사이트에서 채점 가능합니다.

    http://koistudy.net/?mid=prob_title&WORD=%ED%8C%8C%EB%B0%9C%EB%A7%88&SUBMIT=GO
    2016.08.10 12:11 신고
  • 프로필사진 kalmiaa 답변 감사합니다~^^ 2016.08.13 18:19 신고
댓글쓰기 폼
공지사항
Total
138,806
Today
68
Yesterday
150