Li Chao Tree

0. 개요 Li Chao Tree 는 Segment Tree의 일종이다. 일반적인 segment tree 가 주어진 구간의 수열의 합 등을 저장했다면 Li Chao Tree 는 주어진 구간을 대표하는 직선을 저장한다. 1. Li Chao Tree Li Chao Tree 는 다소 생소한 자료구조일 것이다. 이 자료구조는 Convex Hull Trick 을 사용할 때 간간히 등장한다. Convex Hull Trick 에 대해서는 다른 포스트에 자세히 적어놓았으니 참고 바란다. Li Chao Tree 는 CHT 를 사용할 때 1차 함수들의 기울기에 경향성이 없을 때 유용하게 사용된다. 주어진 직선들의 기울기가 오름차순이나 내림차순처럼 경향성이 있다면 단순히 이전 직선들과의 교점의 $x$좌표를 비교해서 conv..

Queue

기본적인 자료구조 중 하나인 Queue 구현에 대해 서술하고자 한다. Queue 는 선입선출을 구현한 자료구조다. 선입선출이란 먼저 들어온 원소가 먼저 나가는 구조를 말한다. 주로 배열로 큐를 구현하는게 편해서 선호하는 편이다. 기본적인 형태는 아래와 같다. #define MAXN 10000 struct Queue { int data[MAXN]; int front, rear; }; data가 최대 10,000개까지 들어올 수 있다고 가정하겠다. Queue 구조체 안에 10,000개의 data를 담을 수 있는 data 배열을 선언한다. 그리고 큐에 저장된 첫 data와 끝 data를 가리키는 인덱스를 항상 유지해야 한다. front는 저장된 처음 data를 가리키고, rear는 저장된 마지막 data의 위..

Stack

기본적인 자료구조 중 하나인 Stack 구현에 대해 서술하고자 한다. Stack 은 후입선출을 구현한 자료구조다. 후입선출이란 나중에 들어온 원소가 먼저 나가는 구조를 말한다. 주로 배열로 스택을 구현하는게 편해서 선호하는 편이다. 기본적인 형태는 아래와 같다. #define MAXN 10000 struct Stack { int data[MAXN]; int top; }; 원소가 최대 10,000개까지 들어올 수 있다고 가정하겠다. Stack 구조체 안에 10,000개의 원소를 담을 수 있는 data 배열을 선언한다. 그리고 stack의 top을 가리키는 인덱스를 항상 유지해야 한다. 이 top은 가장 마지막에 들어온 원소의 위치 + 1 을 가리킨다. 1. 초기화 함수 모든 자료구조는 초기화 함수가 필요하..