본문 바로가기

Problem Solving/문제풀이

 (89)
백준 16977번 히스토그램에서 가장 큰 직사각형과 쿼리 문제 요약 길이 N인 히스토그램이 주어진다. 다음과 같은 쿼리를 처리해야 한다. l r w 가 주어지면 [l,r]에 있는 히스토그램만 있을 때, 너비가 w인 직사각형들 중에서 가장 높은 직사각형의 높이를 출력해야 한다. N, Q 둘다 최대 10만이다. 풀이 어떤 배열이 0 혹은 1로 이루어져 있는데 어떤 구간에서 연속으로 1인 구간의 최대 길이를 계산하는 세그먼트 트리를 생각해보자. 금광세그로 유명한 그것을 살짝 변형해보면 될 거 같다. 각 노드에서 관리할 정보는 담당 구간의 제일 왼쪽에 시작하는 1의 연속 구간의 길이와 제일 오른쪽부터 시작하는 1의 연속구간의 길이이다. 그리고 제일 긴 1의 연속구간의 길이이다. 그러면 두 구간을 합해줄 때 새로운 노드의 왼쪽 1의 길이는 왼쪽을 담당하는 노드의 왼쪽 ..
백준 10076번 휴가 문제 요약 크기 n인 배열이 주어진다. 그리고 시작위치 start와 휴가일수 d가 주어진다. 배열의 값 $a_i$는 i번째 지점에 위치한 관광지 수이다. 배열을 한 칸 이동하는데에 1일이 사용되고 현재 위치한 곳의 관광지를 전부 보는 데에 1일이 사용된다. 한 번 본 곳은 다시 봐도 의미가 없다. 이 때, 돌아볼 수 있는 최대 관광지 수를 구해야 한다. n은 최대 10만이며 d는 최대 2n + n//2이다. 풀이 제일 먼저 할 수 있는 관찰은 왔다갔다를 여러번 하는 것은 절대 최적일 수가 없다. 왼쪽으로 갔다가 오른쪽으로 갔다가 다시 왼쪽으로 가는 것은 휴가일수를 낭비하기만 한다. 따라서, 한 방향으로 쭉 갔다가 한번 꺾어서 쭉 가는 것만 고려한다고 하자. 그러면 왼쪽으로 갔다가 오른쪽으로 가는 거랑 오..
백준 17373번 녜힁 문제 요약 N개의 1이상 M이하의 정수가 주어진다. 1이상 M이하의 정수 중에서 두 숫자를 뽑아서 나열하려고 하는데 이 때, 나열할 수 없는 경우가 존재한다. N개의 주어진 수 중에서 어떤 숫자 x가 어떤 숫자 y보다 앞에 위치한다면 x y는 나열이 불가능한 경우이다. 쿼리로 숫자 K가 주어지는데 이런 식으로 나열이 가능한 경우들 중에서 사전순으로 K번째의 경우를 출력해야 한다. 만약 나열 가능한 경우의 수가 K보다 작다면 -1 -1을 출력하도록 한다. 제목이 녜힁이다. 녜힁~ 풀이 두 글자로 이루어져 있으니 먼저 첫 글자에 집중해보자. 어떤 숫자 x를 첫 글자로 사용한다고 했을 때, x의 뒤에 올 수 있는 숫자의 가짓수는 $O(N)$에 구하는 것이 가능하다. start_num[i] : i가 처음 등장하..
백준 14898번 서로 다른 수와 쿼리 2 문제 요약 길이 N인 배열이 주어진다. l r로 쿼리가 주어진다. 구간 [l,r]에서 서로 다른 수의 개수를 출력해야 한다. N은 최대 100만이다. 풀이 숫자가 크다. 좌표압축부터 하고 시작하자. [1...x]까지를 나타내는 $segtree_x$를 생각해보자. 이 세그트리에서 1이 켜지는 위치는 해당 구간에서 한 번만 등장하는 수는 그 수가 등장하는 위치에 1이 켜지고, 여러 번 등장하는 수가 있다면 그 수가 등장하는 곳들 중에서 제일 오른쪽에만 1이 켜진다. 예를 들어서 배열이 [1,1,4,2,1,2]라고 하면 [0,0,1,0,1,1]이 된다. 이런 세그먼트 트리가 있다면, [l,r] 쿼리가 들어오면 $segtree_r$에서 [l,r]로 구간합 쿼리를 날리면 우리가 원하는 답이 된다. 이런 세그먼트 ..
백준 11932번 트리와 K번째 수 문제 요약 크기가 N인 트리가 주어진다. 각 노드에는 숫자가 있다. X Y K 로 쿼리가 주어지는데 이는 X번 노드부터 Y번 노드까지 가는 경로 중에서 K번째 수를 출력하는 것이다. 트리의 크기와 쿼리 수 둘 다 최대 10만이다. 풀이 선생님 이거 문제가 너무 어렵지 않습니까 일단 트리에서 경로를 빠르게 찾아야 한다. 만약에 어떤 자료구조가 루트부터 시작해서 $i$번 정점까지 가는 경로를 나타내고 있다고 하자. 그런 자료구조를 $d_i$라고 하면 X부터 Y까지 가는 경로는 $d_X + d_Y - d_{LCA(X,Y)} - d_{par(LCA(x,y))}$라고 할 수 있다. 무슨 소린지 모르겠어도 괜찮다. 일단 정점에 적혀 있는 숫자들을 전부 좌표압축하고 압축한 수로 바꿔주자. 그럼 대략 0부터 N-1까지..
백준 13513번 트리와 쿼리 4 문제 요약 크기 N인 트리가 주어진다. 처음 정점의 색은 전부 흰색이다. 다음과 같은 쿼리를 처리하자. i번 정점의 색을 바꾼다. 흰색이면 검은색으로, 검은색이면 흰색으로 모든 흰색 정점 쌍 중에서 그 정점간의 거리가 가장 긴 거리를 출력하자. 풀이 내가 짰던 코드를 보기만 해도 머리가 아파온다. 가능하면 백준 13431번 트리 문제을 풀고 이 문제를 푸는 것을 추천한다. 이 문제가 훨씬 간단한거 같다. 일단 전체에서 가장 긴 흰색 정점간의 거리를 처리해야 한다. 위 사진에서 선언한 컨테이너들의 역할부터 차례차례 소개하겠다. subtree[x]는 센트로이드 트리를 만들었을 때, x의 서브트리들에 속해 있는 흰색 정점과 x와의 거리를 각 서브트리별로 들고 있다. sub_dm[x]는 x의 서브트리에 속해 있..
백준 20045번 Trading System 문제 요약 길이 n인 배열이 주어진다. 여기서 최대 연속합 k개를 구해야 한다. n은 최대 25만이고 k는 최대 1만이다. 풀이 여담으로 대회 중에 상수 큰 로그 두개 붙은 풀이 떠올렸다가 짜보지도 못하고 박살났다. ㅜㅜ 배열 a의 누적 합 배열을 $p$라고 하자. [i...j]의 연속합은 $p[j] - p[i-1]$이다. 오른쪽 끝이 고정 됐을 때 가장 큰 연속합은 $p[0...j-1]$중에서 가장 작은 값을 $p[j]$에서 빼준 값이 된다. 그러면 오른쪽 끝이 j인 연속합에서 두번째로 큰 값을 $p[0...j-1]$에서 두 번째로 작은 값을 빼준 값이 된다. 이 점을 고려해서 문제를 풀 수 있다. 먼저 모든 $i$번째 원소에 대해서 $i$번째 원소에서 끝나는 가장 큰 연속합을 뽑느다. 그리고 이것들을..
백준 13538번 XOR 쿼리 문제 요약 다섯 종류의 쿼리를 처리해야 합니다. 배열의 끝에 원소를 하나 추가한다. $A_L \cdots A_R$에서 x와 xor한 값이 가장 큰 $y(=A_i)$를 출력한다. 배열의 끝에서 k개를 제거한다. $A_L \cdots A_R$에서 x보다 작거나 같은 원소의 개수를 출력한다. $A_L \cdots A_R$에서 K번째 수를 출력한다. 쿼리는 최대 50만개가 들어오고, 입력되는 수는 최대 50만이다. 풀이 A의 최대 길이는 50만입니다. 그래서 그냥 50만짜리 배열이 있고 원소가 추가된다고 치면 추가될 자리에 변경이 일어난다고 치고, 삭제 쿼리는 그냥 길이를 줄인다고 생각합시다. 이제 등장가능한 원소의 범위를 커버하는 세그먼트 트리를 만듭시다. $n$번째 원소의 제일 최근 업데이트를 가지고 있는 ..

티스토리툴바