Hyun's_Devlog

https://www.acmicpc.net/problem/3653

세그먼트 트리 문제다. 접근방법이 떠오르지 않아 다른 분의 풀이를 보고 나서 풀었다.

풀이

n개의 DVD 중 임의의 DVD를 m번 선택한 뒤 시청한 뒤 가장 위에 놓는다는 얘기는 세그먼트 트리의 입장에서 n개의 DVD앞에 m개의 빈 공간이 필요하다는 얘기가 된다. 리프노드 m+n개를 표현할 수 있는 구간 합 세그먼트트리를 생성한다. 끝에서 n개 구간(m ~ m+n)에 하나씩 추가하여 처음 상태의 DVD 위치를 지정한다.

X번 DVD가 선택되면 [0 ~ X-1] 구간의 구간합을 반환하고 해당 DVD를 m-0번 구간으로 이동, 다음 선택된 DVD는 m-1번 구간으로 이동하면서 반복하면 된다. 예제를 기준으로 다음과 같이 그래프 상태를 그려볼 수 있다.

초기상태의 트리와 배열의 모습이다. 배열에는 1번부터 3번 DVD가 트리의 어느 구간에 있는지 나타낸다. 

가장 먼저 3번 DVD의 경우 5번에 위치. 즉 0~4번까지의 구간합을 출력한다. 

이후 자신의 위치를 DVD 진열의 최상단인 2번 인덱스로 이동. 이후 3번 DVD의 위치를 갱신해 준다.

다음으로 1번 DVD의 위치는 3번이니 0~2번 구간합을 출력한다. 

이후 해당 DVD는 다음 최상단 인덱스인 1번으로 이동. 

1번 DVD를 확인. 이번에는 0~0 구간의 구간합을 출력하면 된다.

마지막 위치인 0번으로 위치 갱신.

정답 코드

https://www.acmicpc.net/problem/7578

세그먼트 트리 문제다.

풀이

A열의 좌측부터 연결해 가면서 계산이 이루어져야 한다. 각 A열의 기계번호가 B열에서 몇 번째에 위치한 지 찾아낸 뒤, 해당 위치부터 N-1번째 까지 몇 개의 기계가 연결되어 있는지 개수를 저장하면 된다. 구간 합 세그먼트트리와 딕셔너리를 이용하여 접근하였다.

예제를 기준으로 설명하면 다음과 같다.

A열의 0번 기계는 B열의 2번에 위치해 있다. 0~4까지의 연결된 기계의 개수를 조회한다.

구간에 연결된 기계가 하나도 없으므로 +0.

다음으로 A열 1번 기계는 B열의 0번에 위치한다. 0~4구간의 연결된 기계의 개수 조회.

한 개(2번)가 있으므로 +1.

A열 2번은 B열의 3번에 위치. 3~4구간 조회.

하나도 없으므로 +0.

A열 4번은 B열의 1번에 위치하여 1~4구간 조회.

두 개(2번, 3번)가 있으므로 +2.

마지막으로 A열 4번은 B열의 4번에 위치.

마지막 인덱스이므로 뒤에 연결된 기계가 없다. 즉 정답은 3을 출력한다.

정답 코드

https://www.acmicpc.net/problem/1280

세그먼트 트리 문제다.

풀이

i번째 나무의 좌표 A에 대한 비용은 다음과 같이 정리가 가능하다. 

|(A -[i-1] 번 나무 좌표)| + |(A - [i-2] 번 나무좌표)| +... + |(A - [i-i] 번 나무 좌표)|
->  | A*i - ([i-1]번 나무 좌표 + [i-2] 번 나무좌표 +... + [i-i] 번 나무좌표) |

즉 해당 부분을 여태 심어진 나무의 갯수와 좌표의 누적값을 통해 계산이 가능하다는 것이다. 따라서 0부터 199,999 좌표의 나무개수와 해당 구간의 누적 좌표값을 표현하는 세그먼트 트리를 생성하여 다음과 같이 계산이 가능해진다.

좌측 비용 = (A보다 좌측에 있는 나무의 갯수 * A) - (A보다 좌측 좌표에 심어진 나무의 거리(좌표) 총합)
우측 비용 = ((A보다 우측 좌표에 심어진 나무의 거리(좌표) 총합) - (A보다 우측에 있는 나무의 개수 * A)
A좌표에 나무를 심는 비용 = 좌측비용 + 우측비용

매 입력마다 해당 좌표의 비용을 구하여 계산한 뒤, 다음 나무의 비용 계산을 위해 나무의 갯수를 갱신해 주면 값을 구할 수 있다.

정답 코드

세그먼트 트리의 활용은 정말 다양한 것 같다.

https://www.acmicpc.net/problem/1725

세그먼트트리로 접근한 문제다. 

풀이

구간 최솟값의 인덱스를 반환하는 세그먼트트리를 생성한다. 0~N-1 범위의 최소 인덱스를 찾은 뒤, 해당 인덱스를 사용하여 히스토그램의 넓이를 계산, 이후 해당 [0 ~ 최솟값인덱스-1] 범위와 [최솟값 인덱스+1 ~ N-1] 범위의 히스토그램 넓이를 계산해 나가면 된다. 

예제 [2,1,4,5,1,3,3]을 기준으로 다음과 같이 동작한다.

최솟값 인덱스 세그먼트트리 생성

가장 먼저 0~6 전체 범위의 히스토그램 영역을 탐색한다.

1번 인덱스가 반환되며 해당 블록의 높이인 1과 밑변에 해당하는 0~6 범위(6-0+1)를 곱해 넓이를 계산한다.

이후 해당 최소값 인덱스를 기준으로 좌, 우 영역의 넓이를 계산해 나가면 된다.

좌측의 경우 2*1 = 2가 반환되며 우측의 경우 1*5 = 5가 계산된다. 

이후 좌측의 경우 범위의 시작값과 마지막값이 동일하므로 종료.

우측의 경우 아직 탐색할 범위가 남았으므로 좌측과 우측을 계산한다.

2~3에 해당하는 넓이 4*2 = 8 계산. 5~6에 해당하는 넓이 3*2 = 6 계산.

남은 범위 계산을 위해 재귀호출을 이어간다.

3~3 범위 1*5 = 5 계산. 6~6 범위 3*1 = 3 계산.

더 이상 탐색할 범위가 없으므로 앞서 나온 모든 값들 중 최대값 8을 출력하면 정답이다.

정답 코드

https://www.acmicpc.net/problem/1849

세그먼트 트리 문제다.

풀이

숫자 i 앞에 i보다 큰 숫자의 개수는 작은 수부터 탐색했을 때, 앞에 주어진 빈칸의 개수로 접근 가능하다. 트리의 리프가 1인 구간합 트리를 생성하여 해당 숫자가 몇 번째 숫자인지 뽑아내면 문제를 해결할 수 있게 된다. 수열 [2 4 3 1]의 경우로 시나리오를 작성하면 다음과 같다.

입력 예제 : 3 0 1 0

수열의 구간중 남아있는 공간의 수를 나타내는 세그먼트 트리 생성.

트리 초기화 및 입력값 저장. 순번으로 다루기 편하게 입력값을 +1 처리하여 저장한다.

가장 먼저 1의 인덱스를 찾는다. 남아 있는 공간 중 네 번째 공간의 인덱스를 탐색. 3이 반환된다. 해당 인덱스에 1 저장.

다음 탐색을 위해 방문했던 노드는 -1 처리한다.

2의 인덱스 탐색, 현재 남아있는 공간중 첫 번째 공간의 인덱스로 0이 반환된다.

3의 인덱스를 탐색, 현재 남아있는 공간중 두 번째 공간의 인덱스인 2가 반환된다

마지막으로 4의 인덱스 탐색. 남아있는 공간중 첫 번째 공간, 즉 유일하게 남아있는 공간의 인덱스를 반환하여 수열을 완성하면 된다.

정답 코드

https://www.acmicpc.net/problem/1517

제목은 버블 소트지만 크게 세그먼트트리 또는 머지 소트로 접근하는 문제다. 세그먼트 트리를 공부하기 위해 세그먼트 트리로 접근했다.

풀이

버블 소트는 자신보다 뒷순번의 숫자 중 더 작은 숫자와 swap이 일어나게 된다. 즉 자신보다 뒷순번의 숫자 중 더 작은 수의 개수를 세그먼트 트리를 통해 구해내고 그 수의 합을 반환하면 문제에서 요구하는 swap이 일어나는 수를 구할 수 있다는 얘기다.

입력된 수열에 숫자와 인덱스가 담긴 튜플배열을 생성하여 숫자 기준 오름차순으로 정렬한다. 0으로 초기화된 세그먼트트리를 생성. 이후 (숫자, 인덱스) 튜플이 담긴 배열을 순회하면서 (인덱스 ~ N-1) 구간의 숫자를 정답에 더해준 뒤 해당 구간에 +1 갱신해 준다. 수열을 모두 돌게 되면 자연스럽게 자신보다 뒷구간에 더 작은 숫자들의 개수를 계산할 수 있게 된다.

예제 [3,2,1]을 기준으로 설명하면 다음과 같다.

구간 합 세그먼트 트리 생성. (숫자, 인덱스) 튜플을 숫자 기준 오름차순으로 정렬한다.

1의 인덱스는 2였다. 2부터 마지막 인덱스 2 즉 2~2 구간의 값을 조회. 0을 정답에 추가.

이후 들어올 구간합을 계산하기 위해 2-2에 +1 갱신작업을 한다.

다음 숫자의 인덱스는 1이다. 1~2구간의 값을 조회. 1이 반환되며 해당 결과를 정답에 저장. 

이후 마찬가지로 1-1 구간에 +1 갱신 작업을 한다.

마지막 3의 인덱스는 0이다. 0~2 구간의 값을 조회. 3보다 뒤에 있으면서 작은 숫자들의 개수는 2이다. 정답에 저장한다.

0-0 구간에 +1 갱신. 정답에는 0 + 1 + 2 즉 3이 담겨있고 해당 값이 swap이 일어난 횟수이다.

정답 코드

https://www.acmicpc.net/problem/1572

세그먼트 트리 문제다.

풀이

[1321] 군인 문제와 [2243] 사탕상자 문제와 마찬가지로 최근 K개의 숫자 중 (K+1)/2 번째 숫자에 접근하면 된다. 0부터 65536의 숫자가 몇 개가 담겨있는지를 표현하는 구간 합 세그먼트트리를 생성. 이후 N개의 입력을 받으면서 세그먼트트리에 갱신해 준 뒤, 원소가 K개 이상일 때부터 (K+1)/2 번째로 작은 숫자를 계산하면 정답을 구할 수 있다.

여기서 중요한 점은 최근 K개까지가 범위이므로 중앙값을 반환할 때마다 (수열의 크기 - K) 번째 숫자를 세그먼트트리에서 하나씩 제거해주어야 한다.

정답 코드

https://www.acmicpc.net/problem/1321

세그먼트트리 문제다. 바로 이전 문제인 [2243] 사탕상자 문제와 동일한 풀이로 접근하면 된다.

풀이

N개의 부대에 속한 군인 수를 저장하는 구간 합 세그먼트트리를 생성한다. 이후 i번째 군인의 부대를 호출할 때, 현재 구간의 군인 수가 i보다 크다면 좌측노드에서 i번째 군인 탐색. 현재 구간의 군인 수가 i보다 적다면 (i - 좌측구간 군인수) 번째 군인을 우측노드에서 탐색한다. 없는 군인을 탐색하는 경우는 주어지지 않으므로 리프노드에 도달할 경우에 해당 노드의 인덱스를 반환하면 된다.

정답 코드