본문 바로가기

알고리즘19

Usaco Gold) Fair Photography Problem 1부터 10억까지 좌표중에, N개의 값을 넣는다. 해당 값은 1~8사이 이다.이 중 두가지 조건을 만족하는 가장 긴 길이의 범위는?- 서로다른 K개의 이상의 값이 존재해야한다.- 각 값들의 갯수는 같아야 한다. 논리 과정 T(b,p) 를 p보다 왼쪽에있는 b의 갯수라고 하자.- T(b,R) = T(b,L) + c 만약 이 사이에 b 가 존재한다면.- T(b,R) = T(b,L) 이다 만약 b가 존재하지 않는다면. 따라서 집합 A 와 기준점 p 가 주어지면 우리는 signature S(A,p) 를 만들 수 있다.- T(b,p) - T(b0,p) 이 때 b0 는 A 안에 첫번쨰 원소이다.- T(b,p) 는 존재하지 않는것에 대하여. 만약 S(A,L) = S(A,R) 이고 L 2018. 6. 3.
[기하] 다각형의 내부 외부 판별 다각형의 내부 외부 판별이란? 그림1 에는 다각형과 두개의 점 A,B 가 있습니다. 이 그림에서 눈으로 확인했을 때 각 점이 다각형 내부에 있는지, 외부에 있는 지 판별하는 것은 쉽습니다.이렇게 주어진 점이 다각형 내부에 있는 지 외부에 있는 지 판별하는 것을 다각형의 내부 외부 판별이라고 합니다. 아이디어 다각형의 내부에 위치하는 점의 특성 컴퓨터가 특정 점이 다각형 내부에 있는지 어떻게 판별할까요? 오른쪽으로 반 직선을 그었을 때 다각형과 만나는 점의 개수가 홀수 개라면 내부에 있는 점입니다. 그림2를 보고 이 특징이 맞는지 확인해봅시다. 다각형 외부에 있는점 A는 다각형과의 교점 개수가 2개 즉 짝수개 입니다.다각형 내부에 있는점 B는 오른쪽으로 그은 반직선과 다각형과의 교점 개수가 3개 즉 홀수 .. 2018. 5. 13.
BOJ 6171) 땅따먹기 어떤 땅의 i 의 너비 Wi 와 Hi 가 주어진다.이 때 가격은 Wi * Hi 이다. - 한번에 여러개 된다면, (해당 땅 중 Wi의 최댓값 ) * (해당 땅 중 Hi의 최댓값) 으로 가격을 매긴다. 따라서 땅을 최소 비용으로 묶어서 살 경우 최소 비용은 ? 일단 무조건 wi를 기준으로 정렬을 시킨다.이 때 만약 Wi 와 Hi 가 Wj , Hj보다 더 크다면 무조건 묶는게 이득이다. 따라서 O(n) 시간으로 탐색하면서 더 큰 애들을 지워나간다. 그렇게 되면 현재 Wi 는 오름차순, Hi 는 내림차순으로 정렬된다. 그러고 DP를 생각해보자! DP[i] = min (DP[j-1] + b[j] * a[i]) 의 식이 성립한다. ( b 는 내림차순) 그러므로 Convex Hull Trick 을 사용하면 된다. .. 2018. 5. 13.
DP최적화 - Convex Hull Trick * 필요한 상황 dp[i] = min( dp[j] + b[j]*a[i] ) 를 찾는건데 여기서 b[i] > b[i+1] ( b는 내림차순) 을 반드시 만족한다. (j < i 인 정수) 만약 오름차순이라면 굳이 계산할 필요가 없고, 내림차순이라면 binary search 로 찾을 수 있다. 이런 식이 나온다면 바로 CHT 를 쓸 수 있다. 여기서 문제가 되는 것은 바로 조건에 맞지 않는 직선들을 제거해주는 것이다. * 업데이트현재 line1이 새로 추가될 것이라고 생각하자.그렇다면 line3 , line2 를 현재 저장된 라인들 중 가장 뒤에 있는 라인이라고 하자. intersect - x(line3,line1) = x1intersect - x(line3,line2) = x2 라고 해보자. 만약 x1 < .. 2018. 5. 6.