Algorithm/J. Optimization (4) 썸네일형 리스트형 197. Convex Hull Trick 이제부터는 여러 가지 DP 최적화(DP Optimization) 방법에 대해서 알아보기로 한다. DP 최적화는 DP 식이 특수한 형태로 존재할 때 그 식의 특성을 이용해서 시간복잡도를 줄이는 기법들을 의미한다. 그중 가장 먼저 살펴볼 내용은 컨벡스 헐 트릭(Convex Hull Trick, CHT)이며, DP 식이 다음과 같은 형태일 때 사용할 수 있다($\min$ 대신 $\max$가 들어갈 수도 있고 이 경우 $a_i$의 부등호 방향이 반대로 변함):$$S_i = \min_{j $$a_1 > a_2 > \ldots > a_{n - 1} > a_n$$이 식에서 $S_n$을 구하는 것이 목표라고 하면, $S_n$을 구하기 위해서는 $S_1$부터 $S_{n - 1}$까지를 모두 알아야 하는데 $S_1$부터 .. 196. Counting Points in Triangle 이번에는 삼각형 안의 점 개수를 빠르게 세는 테크닉(Counting Points in Triangle)에 대해서 다룬다. 이 테크닉에 붙은 이름은 아직까지는 없는 것으로 알고 있다. 따라서 이 글의 제목도 공식적으로 굳어진 명칭이 아니다. 다음과 같은 문제를 생각해 보자.$2$차원 좌표평면에 속한 점 $n$개가 주어진다. 어떤 세 점도 일직선상에 있지 않다. 이제 여기서 세 개의 점을 골라서 삼각형을 만들면 그 삼각형은 다른 점들을 포함할 수도 있다. 이때 점을 $0, 1, \ldots, n - 3$개 포함하는 삼각형의 개수를 모두 구하여라.점 $n$개로 만들 수 있는 서로 다른 삼각형의 수는 $\frac{n(n - 1)(n - 2)}{6} = \frac{1}{6}n^3 - \frac{1}{2}n^2 +.. 195. Small to Large Technique 첫 번째로 알아볼 최적화 기법은 작은 집합에서 큰 집합으로 합치는 테크닉(Small to Large Technique)으로, 분리 집합을 조금 더 발전시킨 것으로 이해할 수 있다. 즉, 기존의 분리 집합이 '원소 $x$가 속한 집합은 무엇인가?'라는 질문에 대한 답을 제공할 수 있다면 이 스몰 투 라지 기법은 '집합 $S$에 속한 원소들은 무엇인가?'라는 질문에 대한 답을 제공할 수 있다고 보면 된다. 물론 두 개를 같이 쓰면 양방향 질의 처리가 가능하다. 어떤 집합에 속한 원소들이 무엇인지를 알아야 하기 때문에 집합이 합쳐질 때마다 집합 내의 원소들도 하나로 합쳐야 하는데, 여기서 항상 원소의 수가 더 적은 집합을 원소의 수가 많은 집합에 합치면 어느 정도의 속도를 보장한다는 것이 작은 집합에서 큰 집.. 194. Optimization Intro 카테고리 J에서는 다양한 최적화(Optimization) 기법을 통한 문제 해결 방법과 이의 대표적 예시인 동적 계획법 최적화(DP Optimization)에 대해서 다룬다. 다루는 내용은 다음과 같다.개선된 분리 집합(Small to Large Technique)삼각형 안의 점 개수 세기(Counting Points in Triangle)동적 계획법 최적화(DP Optimization)오프라인 동적 연결성 판별(Offline Dynamic Connectivity)커넥션 프로파일 DP(Connection Profile DP)회전 스위핑(Rotating Sweep Line)개선된 최장 공통 부분수열(Hirschburg's Algorithm, Bitset LCS)대부분이 상당히 복잡한 내용을 포함하고 있으며.. 이전 1 다음
