본문 바로가기

분류 전체보기

 (133)
백준 3444번 Robotic Sort 문제 요약 길이가 N인 배열에 대해서 정렬을 진행한다. 정렬 과정은 다음과 같다. $i$번째 과정에서 배열에서 $i$번째로 작은 원소를 $i$에 위치시키려고 한다. 이를 위해서 매 과정마다 $i$번째로 작은 원소를 $[i, N]$에서 찾고 그 위치를 $p$라고 하면 $[i,p]$를 뒤집어서 정렬을 수행한다. 여기서 숫자가 같더라도 원래 배열에서 더 앞에 있는 것을 작은 것으로 친다. 이 때, 각 과정마다 $i$번째로 작은 원소의 위치인 $p$를 모두 출력하라. N은 최대 10만이다. 풀이 먼저 각 배열의 원소에 대해서 제시한 방법대로 정렬을 했을 때 해당 원소가 어디에 위치하는지를 계산한다. 이는 $O(NlogN)$에 가능하다. 위에서 계산한 값을 $pos_i$라고 하자. 그러면 각 과정에서의 $a_p ..
백준 13159번 배열 문제 요약 처음에 $a_i = i$인 크기가 N인 배열 $a$가 주어진다. 이 배열에 대해서 다음과 같은 쿼리를 수행하고 모든 쿼리를 수행한 뒤에 배열 $a$를 출력한다. 풀이 해당 문제는 스플레이 트리로 해결이 가능하다. 제일 처음에는 선형 모양의 스플레이 트리를 만들고 1부터 N까지를 차례대로 값에 넣어주도록 하자. 1번 쿼리는 각 노드 별로 최솟값, 최댓값, 합을 관리해줌으로 값은 구할 수 있고 구간을 뒤집는 연산은 Lazy Propagation으로 가능하다. 2번 쿼리는 k가 양수인 경우에는 [l,r]을 오른쪽으로 shift해야 되는데 이 경우는 구간을 뒤집는 연산을 세번 하면 가능하다. [r-k+1, r]을 먼저 뒤집고, [l,r-k]를 뒤집고 그 다음엔 [l,r]을 뒤집으면 shift가 완료된..
백준 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의 서브트리에 속해 있..

티스토리툴바