전체 글 썸네일형 리스트형 BOJ)3653 영화 수집 문제: icpc.me/3653 순서대로 쌓여있는 DVD가 있을 때 영화를 볼때마다 위에 몇개의 DVD가 쌓여있는지 출력하는 문제이다. 이 때 본 영화는 맨위에 쌓는다고 한다. 우리는 세그먼트 트리의 구간합을 통하여 문제를 해결할 수 있다. 우선 n+m+1개의 노드중 m+1~n+m+1에 해당하는 리프에 1씩 업데이트 시킨다. 이는 n개의 DVD가 m+1부터 순서대로 존재한다는 것을 의미한다. 이 때 i번 DVD는 i+m에 존재한다고 기록해 준 뒤 i번째 영화위의 DVD의 개수는 1~(i번 DVD의 위치-1)의 구간합으로 구해줄 수 있다. DVD를 뺐으므로 원래 DVD의 위치는 0으로 갱신해 준 후 맨 위에 DVD를 갱신해 줘야한다. 맨위는 i번째 쿼리를 처리할 때 m+1-i 번째 위치일 것이다. 해당 위치.. 더보기 BOJ)6549 히스토그램에서 가장 큰 직사각형 문제: icpc.me/6549 히스토그램에서 가장 큰 직사각형을 구하는 문제이다. 세그먼트 트리를 이용한 분할 정복을 이용하여 풀 수 있는데 i,j까지의 구간의 직사각형 넓이는 i,j까지의 높이가 최솟값인 부분에 의하여 결정된다. 따라서 우리는 높이가 최솟값인 부분을 기준으로 양쪽을 분할 정복해 나갈 것이다. 이를 계산하기 위하여 높이가 최솟값인 지점을 세그먼트 트리에 저장을 해줘야 한다. 전체에서 넓이를 구하여 높이가 최솟값인 지점을 기준으로 양쪽의 넓이를 다시 구해주면서 최종적으로 높이의 최댓값을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#.. 더보기 BOJ)5419 북서풍 문제: icpc.me/5419 북서풍을 타고 항해할 수 있는 섬의 쌍의 개수를 구하는 문제이다. 여기서 북서풍을 타고 항해할 수 있는 섬이란 어떤 섬 기준으로 x좌표가 해당하는 섬보다 크거나 같고 y좌표가 해당하는 섬보다 작거나 같은 섬들을 말한다. 결국 우리는 각 섬마다 x좌표가 작으면서 y좌표는 큰 섬들의 개수를 구한 뒤 그 합을 출력하면 된다. 우리는 x좌표가 작은 수를 우선적으로 정렬하되 x좌표가 같을 경우 y좌표가 큰 수를 우선적으로 정렬을 할 것이다. 이렇게 정렬을 했을 시에 먼저 등장하는 좌표뒤에 나오는 좌표들 중 북서풍을 타고 항해할 수 있는 섬이 없다는 것은 자명하다. 따라서 우리는 정렬을 해준 뒤 순서대로 봐주면 된다. x좌표 기준으로 정렬을 했으므로 우리는 먼저 등장했던 섬들 중에서 .. 더보기 이전 1 ··· 104 105 106 107 108 109 110 ··· 118 다음