Hyun's_Devlog

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

위상정렬 문제다.

풀이

처음 문제를 읽었을 때는 기본부품부터 완성품까지 위상정렬로 탐색하여 부품의 개수를 세는 방법으로 접근하였는데, 그렇게 되면 기본부품을 파악하기 힘들어진다.

따라서 완성품에서 기본 부품 순서로 위상정렬을 통해 접근하여 탐색하였다. 마지막 노드라면 해당 부품의 cost를 출력하는 방법으로 접근했다. 

부품의 비용을 담을 크기 N의 cost배열과, 간선정보를 (다음노드 번호, 비용) 형태로 담을 크기 N의 튜플배열을 생성. 진입차수가 0인 N번 노드를 시작으로 현재 cost X 다음 cost를 배열에 갱신하여 참색을 수행하였다. 입력 예제의 시나리오를 그림으로 표현하면 다음과 같다.

각 노드의 진입 차수, 실시간 비용, 그리고 마지막으로 출력할 정답 배열을 생성한다.

가장 첫 번째로 진입 차수가 0인 7번 노드 방문, 4번, 6번, 5번 부품의 비용을 갱신한다.

(현재 비용 * 간선 비용)을 통해 계산이 가능하다.

다음으로 진입 차수가 0인 6번 노드 방문. 탐색을 시작한다. 인접 노드의 비용을 갱신.

3번 노드를 방문. 이때 3번 노드의 경우 더 이상 탐색 가능한 인접 노드가 없다.

3번 부품을 생산하기 위한 다른 부품은 필요 없다는 뜻이므로 ans 배열에 해당 비용을 반영한다.

다음으로 진입 차수가 0인 4번 노드 방문. 마찬가지로 더 이상 탐색 가능한 인접 노드가 없으므로 현재 비용을 ans 배열에 반영한다.

다음으로 5번 노드 방문 인접 노드인 1번 노드와 2번 노드에 (현재 부품 비용 * 간선 비용)을 계산하여 cost배열에 값을 반영한다.

1번 노드 방문. 더 이상 탐색 가능한 노드가 없다. ans 배열에 현재 비용을 반영한다.

마지막으로 2번 노드 방문. 더 이상 탐색 불가능 하므로 ans 배열에 현재 cost를 반영한다.

완성된 ans 배열을 통해 0이 아닌 값들을 출력하면 정답이다.

정답 코드

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

스위핑 문제다.

풀이

입력되는 구간의 정보를 도착좌표를 기준으로 오름차순으로 정렬한다. 이후 길이가 D 이하인 구간에 대해서만 시작 좌표를 heap에 담아낸 뒤, 매 탐색마다 heap에서 (현재 구간의 도착좌표 - D) 보다 큰 좌표들의 개수를 세면 된다. 해당 값 중 가장 큰 값이 정답이다.

예제를 기준으로 다음과 같이 동작한다.

입력되는 구간을 좌표를 기준으로 오름차순, 도착좌표가 같다면, 출발좌표를 기준으로 오름차순으로 정렬한다.

이후 출발좌표를 담아낼 최소 heap 개수의 최댓값을 정답으로 출력하면 된다.

가장 먼저 탐색할 구간의 도착좌표는 20이며 해당 구간의 길이는 D(30) 보다 작으므로 heap에 해당 구간의 출발좌표인 10을 추가한다.

(도착좌표 - D)의 값이 heap의 peek보다 작으므로 다음 탐색으로 넘어간다.

다음으로 탐색할 구간의 출발좌표는 10이며 해당 구간 또한 크기가 D보다 작고

heap의 peek가 (도착좌표 - D) 보다 크므로 heap에 10을 추가하고 다음 탐색으로 넘어간다.

출발 좌표 25를 담아내고, (도착좌표 - D)의 값이 peek보다 작으므로 다음 탐색으로 넘어간다.

동일하게 출발 좌표 25를 heap에 담아내고 (도착지점 - D)가 5로 현재 peek값 10보다 작으므로 다음 탐색으로 넘어간다.

해당 구간은 길이가 D보다 크므로 아무 작업을 하지 않고 다음 탐색을 이어간다.

해당 구간의 출발 좌표 30을 담아낸다. 여기서 heap의 변화가 일어난다.

(도착지점 - D)의 값이 20이므로 peek 값인 10보다 크다. 따라서 heap에서 20보다 작은 값은 삭제한다.

heap의 크기는 3으로 변경되며 peek값은 25로 갱신되었다.

출발좌표 50을 heap에 담고, (도착지점 - D)의 값인 30보다 작은 값들은 heap에서 삭제.

현재 heap의 크기는 2, peek값은 30이 되었다.

마지막 구간의 출발좌표 80을 담고 (도착지점 - D)의 값인 70보다 작은 값은 모두 heap에서 제거.

heap의 크기는 1이며 peek값은 80으로 변경된다.

탐색동안의 heap의 최댓값인 4를 출력하면 정답이다.

정답 코드

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을 출력하면 정답이다.

정답 코드