정화 코딩

https://www.acmicpc.net/problem/6549 히스토그램에서 가장 넓이가 큰 직사각형은 다음의 셋 중 하나이다. 1. 최솟값을 포함하면서 전체 구간의 직사각형 2. 최솟값 기준 왼쪽 구간에서의 가장 큰 직사각형 3. 최솟값 기준 오른쪽 구간에서의 가장 큰 직사각형 그 이유는 다음과 같다.최대 직사각형은 최댓값을 포함할 수도 있고 포함하지 않을 수도 있다. 만약 최솟값을 포함한다면 구간을 최대로 잡아도 좌우로는 잘리지 않기 때문에, 양쪽 끝까지 구간을 잡는 것이 최대이다. 만약 최솟값을 포함하지 않는다면 해당 최솟값을 기준으로 구간이 이미 잘렸다고 생각하면 된다. 그렇기 때문에 그 값 기준 왼쪽에서의 최대와 오른쪽에서의 최대를 구한다. 따라서 세그먼트 트리로 저장해야 하는 정보는 구간..

https://www.acmicpc.net/problem/2042세그먼트 트리란?세그먼트 트리는 구간에 대한 정보를 트리 구조로 저장하여, 구간의 갱신과 조회를 효율적으로 처리할 수 있도록 설계된 자료구조이다.세그먼트 트리의 원리1번 노드는 1~8 구간의 정보를 담고 있고2번 노드는 1~4 구간의 정보를, 3번 노드는 5~8 구간의 정보를 담고 있고...이런 구조로 되어 있다. 3~7 구간의 정보를 알고 싶다고 생각해보자. 우선 루트 노드에서 시작해서 쭉 내려간다. - 내 구간이 목표 구간에 완벽히 포함되지 않으면 절반으로 쪼개서 자식 노드로 전달한다.- 만약 완벽히 포함된다면 내가 가지고 있는 정보를 그대로 위로 다시 올리면 되고, 만약 전혀 겹치지 않는다면 항등원을 반환한다. 세그먼트 트리 구현아래 ..