(알고리즘) Convex hull Trick

*일차 함수들이 주어졌을 때, f(x)최솟값 등을 구할 수 있는 자료구조

참고: http://wcipeg.com/wiki/Convex_hull_trick
참고: http://codedoc.tistory.com/11




댓글

댓글 쓰기

이 블로그의 인기 게시물

(Garbage Collection) Old Area의 Concurrent Mark-sweep 알고리즘

Initial Mark Phase : 싱글 쓰레드에서만 사용한다. 애플리케이션이 중지되고 애플리케이션에서 직접 Reference(Root set에서 한 단계의 Reference관계)되는 Live Object 만 구별한다. Suspend 상태지만 빠르다. Concurrent Mark Phase 단계 : 싱글 쓰레드에서만 사용한다. 애플리케이션은 수행되고, GC Thread외 Working Thread는 애플리케이션 수행이 가능하다. Initial Mark Phase에서 선별된 Live Object가 Reference하고 있는 object를 추적해 Live여부를 구별한다. Remark Phase 단계: 멀티 쓰레드가 사용되며 애플리케이션이 중지된다. 이미 Marking된 오브젝트를 다시 추적, Live 여부 확정, 모든  Resource를 투입한다. Concurrent Sweep Phase 단계 : 싱글쓰레드만 사용한다. 애플리케이션은 수행되고 최종 Live로 판명된 오브젝트를 제외한 Dead Object를 지운다. 단, sweep 작업만하고 Compaction작업은 수행 안한다.항상 Compaction은 Heap의 Suspend를 전제로 하는데 반복된 Sweep은 단편화를 유발한다. 때문에 Free List를 사용하여 단편화를 줄이는 노력을 한다.
자세한 내용 보기

(데이터베이스) HAVING절과 WHERE 절의 차이

이미지
 GROUP BY 절과 HAVING 절의 특징    - GROUP BY 절을 통해 소그룹별 기준을 정한 후, SELECT 절에 집계 함수를 사용    - 집계 함수의 통계 정보는 NULL 값을 가진 행을 제외하고 수행한다.    - GROUP BY 절에서는 SELECT 절과는 달리 ALIAS 명을 사용불가    - 집계 함수는 WHERE 절에는 올 수 없다. (집계 함수를 사용할 수 있는 GROUP BY 절보다 WHERE 절이 먼저 수행)    - WHERE 절은 전체 데이터를 GROUP으로 나누기 전에 행들을 미리 제거시킨다.   - HAVING 절은 GROUP BY 절의 기준 항목이나 소그룹의 집계 함수를 이용한 조건을 표시할 수 있다.   - GROUP BY 절에 의한 소그룹별로 만들어진 집계 데이터 중, HAVING 절에서 제한 조건을 두어 조건을 만족하는 내용만 출력한다.   - HAVING 절은 일반적으로 GROUP BY 절 뒤에 위치한다.  일부 데이터베이스의 과거 버전에서 GROUP BY 절에 명시된 칼럼의 순서대로 오름차순 정렬을 자동으로 정렬(비공식적인 지원이었음)하는 경우가 있었으나, 원칙적으로 관계형 데이터베이스 환경에서는 ORDER BY 절을 명시해야 데이터 정렬이 수행된다.  ANSI/ISO 기준에서도 데이터 정렬에 대한 내용은 ORDER BY 절에서만 언급되어있지,  GROUP BY 절에는 언급되어 있지 않다. 예) 잘못된 쿼리-수정전 SELECT POSITION                           포지션    ...
자세한 내용 보기

(Pytorch) DataLoder 클래스

DataLoader클래스란? 데이터를 배치로 만드는 작업을 돕는 유틸 클래스로, 배치 데이터를 만드는 여러한 복잡한 작업을 추상화 한다. 해당 클래스는 파이토치의 utils 모듈에 위치한다. 또한 tochvision과 torchtext를 제공한다. 이 두 클래스는 이미지 분석과 자연어 처리를 다룰 때 사용한다.
자세한 내용 보기