set 썸네일형 리스트형 BOJ)2171 직사각형의 개수 문제: icpc.me/21712차원 평면위에 5000개 이하의 점이 있을 때 점들로 만들 수 있는 모든 직사각형의 수를 세는 문제이다,n제한이 5000에 2초이므로 n^2logn 솔루션으로 풀 수 있을 것이라고 생각하였다.n*n으로 모든 두 점에 대하여 직사각형의 대각선에 놓이는 경우를 생각하면, 나머지 대각선에 포함되는 두 점은 set을 이용해 존재여부를 log시간에 찾을 수 있다.123456789101112131415161718192021222324252627#include #include #include #include using namespace std;int n,res;set st;vector vt;int main(){ scanf("%d",&n); for(int i=0;i 더보기 BOJ)2104 부분배열 고르기 문제: icpc.me/2104 주어지는 배열에서 i~j까지의 부분 배열을 선택했을 때 (a[i]+a[i+1]+...+a[j])*(min(a[i],a[i+1]),....,a[j]) 가 최대가 되도록 i j를 선택하는 문제이다. 나이브한 풀이법으로는 i,j를 선택하는데만 O(N^2)으로 시간초과다 .. 따라서 좀 더 그리디하게 생각해보면 만약에 어떤 구간에 대해 정할 때 한 점 X를 기준으로 그 점이 최솟값이 되게 구간을 선택한다면 X를 기준으로 좌우로 최대한 X보다 큰값을 가지는 범위롤 포함하도록 배열을 선택할 수 있다. 이러한 아이디어에서 출발하여 모든 점에 대해서 이 범위를 볼건데 정렬을 해주어 작은 값부터 보면서 set에 업데이트해주어 이동가능한 lower_bound와 upper_bound를 찾아준다.. 더보기 BOJ)2261 가장 가까운 두 점 문제:icpc.me/2261 가장 가까운 두점을 N^2보다 적은 시간에 구해야하는 문제이다. 우선 점들을 x좌표 기준으로 스위핑해보자. 이후 x좌표가 증가하는 순서대로 점들을 볼건데 이미 본 점들은 y좌표 기준으로 정렬이 되도록 set에 삽입해준 후 지금까지의 최단거리가 d라면 현재 볼 점의 x좌표가 d이상 차이나거나 y좌표가 d이상 차이나는 점들을 제외하고 비교해준다. x좌표가 정렬 된 순서로 보기 때문에 포인트를 잡아서 기록해두면 x좌표가 차이나는 점들은 set에서 제거해줄 수 있고 y좌표는 lower_bound와 upper_bound를 통하여 탐색 지점을 정해놓고 비교해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373.. 더보기 이전 1 다음