3015번: 오아시스 재결합 N개의 수들이 주어질 때, 이 중 두 개의 수(한 개의 쌍)를 고른다.이 때 이 두 수 사이에 이 두 개의 수보다 크지 않은 수들로만 구성되는 쌍의 개수를 묻는 문제이다. N개의 수들이 담겨져 있는 배열을 A라 할 때앞에서부터 차례대로 A[i]를 추가함에 따라 생기는 쌍의 개수를 생각해보자.만약에 A[i-1]이 A[i]보다 작다고 생각하자.그럴 경우에는 앞으로 A[j](i < j)를 확인 할 때 A[i-1]과 A[j]이 쌍을 이룰 일은 절대 없다.이 두 수 사이에 A[i-1]보다 큰 A[i]가 존재하기 때문이다.즉 내가 A[i]를 추가하였을 때 이전의 A[i]보다 작은 수는 앞으로의 결과에 영향을 못끼친다는 것이다.그러므로 매 상황마다 이전의 자신보다 작은 수를 제거하면서 답..
14577번: 일기 예보 - 구간트리 (세그먼트 트리) kks227님 블로그의 오프라인 쿼리를 읽고 인상 깊어 작성하게 되었다.이 문제에서는 4개의 쿼리가 있다.1. 하나의 값에 X를 더한다.2. 하나의 값에 Y를 뺀다.3. 값이 L ~ R 사이인 원소의 개수를 구한다.4. K번째로 큰 값을 구한다.이러한 쿼리들을 10^5개를 처리해주면 되는 문제이다. 1번과 2번은 구간트리에서 많이 접해본 적이 있다.어떤 idx에 대하여 X를 더하는, Y를 더하는 과정은 O(lgN)에 구할 수 있다. 3번 쿼리는 값이 L ~ R 사이인 원소들의 개수를 구하는 쿼리이다.이 쿼리를 어떻게 처리해야할까?나라들의 현재 값이 들어있는 배열을 A라 할 때 A = {1, 2, 10, 2, 4} 가 된다고 하자.구간트리에 이 값이 ..
12995번: 트리나라 - DP kks227님 블로그의 동적 계획법 5를 읽고 인상 깊어 작성하게 되었다.트리에서 DP를 사용하는 문제 유형에 대하여 설명하는데 그 중노드 u를 루트로 하는 서브트리 안에서 모든 자식 노드에 분배를 해야하는 문제를 어떤 식으로 접근할까?에 대한 유형이다. 이 문제는 트리가 주어질 때 크기가 K인 트리를 만들기 위한 경우의 수를 묻는 문제이다.이런 문제를 풀 때 기본적인 아이디어는 u의 자식 노드를 v1, v2, ... vm이라 하면u와 v1을 루트로 하는 서브트리랑만 연결 될 때,u와 v1, v2를 루트로 하는 서브트리랑만 연결 될 때,...u와 v1, v2, ... vm을 루트로 하는 서브트리랑만 연결 될 때 순으로 구하게 된다.약간 플로이드 와샬에서 i 정점에서 j 정..