Hyun's_Devlog

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

세그먼트 트리 문제다. 금방 풀 수 있을줄 알고 접근했는데, 생각보다 오랜시간이 소요됐다.

풀이

1부터 n까지의 숫자가 몇개가 있는지를 나타내는 세그먼트 트리를 구현. 남아있는 숫자중 x번째 수를 반환하는 함수와 구간별 숫자의 갯수를 반환하는 함수를 구현하여 접근하였다.

k번째 돌이라는 의미는 이전에 치워진 돌부터 시작하여 k%(현재 남아있는 돌의 갯수)번째 돌을 의미한다. 즉 치워진 돌 앞에 몇개의 돌이 있는지 정보를 가지고 있어야 한다는 점이다. 따라서 치워진 돌 앞의 돌의 갯수를 cnt라고 정의할 때, 우리는 (k+cnt)%현재 남아있는 돌의갯수 번째의 돌을 치우면 된다.

예제 "8 5 3"을 기준으로 다음과 같은 시나리오를 그릴 수 있다.

초기 상태의 구간 합 세그먼트 트리 생성

가장 먼저 m번째 돌인 3번 돌을 제거. 앞에는 두개의 돌이 있다. 

k + cnt % 남아있는 돌의 갯수. 즉 5 + 2 % 7 계산을 통해 0번째 돌을 제거해야하는데, 모듈러 계산에 의한 순서이므로 마지막 돌, 즉 일곱번 째 돌인 8번 돌을 제거하면 된다. 이때 앞에 남아있는 돌의 갯수는 6개가 된다.

6 + 5 % 6 계산. 5이므로 다섯번째 돌인 6번 돌을 제거한다. 

앞순번에 다섯번째 돌을 제거했기에 4 + 5 % 5 계산, 4번째 돌인 5번 돌 제거

다음으로는 3 + 5 % 4 계산, 4번째 돌인 7번 돌 제거

3 + 5 % 3 계산, 남아있는 돌 중 2번째 돌 2번 돌을 제거한다.

1 + 5 % 2 계산, 0번째 돌 즉 남아있는 마지막 돌인 4번 돌 제거.

마지막으로 1 + 5 % 1 계산, 0번째 즉 남아있는 마지막 돌 1번 돌이 제거된다.

마지막으로 제거된 1을 출력하면 정답이다.

정답 코드

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

세그먼트 트리문제다. [7578] 공장 문제와 같은 풀이로 접근가능하다.

풀이

[7578] 공장 문제와 달리 유의할 점은 입력되는 간선의 정렬이 필요하다는 점이다.

출발지 기준 오름차순, 출발지가 같다면 도착지기준 오름차순으로 고속도로 정보를 정렬한 뒤, 매 순간 도착도시 다음번호 ~ 마지막 도착도시 구간의 건설된 고속도로의 개수 총합을 출력하면 된다.

입력 예제를 기준으로 시나리오를 그려보면 다음과 같다.

좌측의 N개의 도시, 우측의 M개의 도시와 정렬된 간선 그리고 구간 합 세그먼트 트리를 생성한다.

1번 도시와 4번 도시를 연결, 4번은 가장 마지막 도시이므로 구간합 조회 시 범위를 넘어가게 되어 0을 반환하게 된다.

다음 탐색을 위해 4번 노드에 1 추가.

2번 도시와 3번 도시 연결, 이때 3번 도시 이후의 구간 즉 4~4번 구간의 고속도로의 개수 1을 정답에 추가한다.

이후 3번 노드에 1 추가.

3번 도시와 1번 도시 연결, 2번 도시부터 4번 도시 구간의 고속도로의 수를 조회한다. 고속도로의 개수 2가 반환된다.

이후 1번 노드에 1 추가.

마지막으로 3번 도시와 2번 도시 연결, 3번 도시와 4번 도시 구간합을 조회. 정답에 해당 구간값 2를 추가한다.

2번 노드에 1 추가.

정답 코드

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/1572

세그먼트 트리 문제다.

풀이

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

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

정답 코드