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/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 - 좌측구간 군인수) 번째 군인을 우측노드에서 탐색한다. 없는 군인을 탐색하는 경우는 주어지지 않으므로 리프노드에 도달할 경우에 해당 노드의 인덱스를 반환하면 된다.

정답 코드

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

세그먼트트리 문제다. 접근방법이 떠오르지 않아 풀이를 찾아보았다.

풀이

1번 맛부터 1,000,000번 맛에 해당하는 사탕의 개수를 표현하는 세그먼트트리를 생성한다. 최대합 세그먼트 트리를 구현하면 된다.

고민할 부분은 문제의 요점인 i번째 순번의 사탕을 찾는 것인데, 해당 부분도 재귀호출을 통해 접근해야 한다. 부모노드부터 시작하여 좌측자식으로 탐색할지 우측자식으로 탐색할지 결정해야 한다. 만일 좌측노드의 값이 i이상이라면, 즉 좌측 노드에서 i번째 사탕을 찾을 수 있다면 그대로 좌측노드로 탐색을 시작하면 되고, 만일 좌측노드의 값이 i 보다 작다면, 즉 좌측노드에서 i번째 사탕을 찾을 수 없다면 우측노드로 탐색을 시도해야 하는데, 우측노드를 탐색한다는 뜻은 (i - 좌측노드의 값) 번째 사탕을 찾는다는 의미이다. 문제에서 현재 없는 사탕을 찾는 경우는 주어지지 않으므로 리프노드에 도달할 때까지 찾아야 할 사탕의 순번을 조절해서 탐색을 시도하면 된다.

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

0으로 초기화된 세그먼트 트리 생성 예제의 경우 큰 번호의 사탕이 나오지 않았기에 6번까지의 범위만 그렸다.

1번 사탕 2개 추가. 3번 사탕 3개 추가.

두 번째로 맛있는 사탕을 찾는다. 1번이 두 개 있기에 1번을 반환. 방문하는 모든 좌측노드가 2 이상이기에 1번 사탕까지 바로 접근. 사탕을 빼내는 작업이기에 방문한 리프노드에 도달할 때까지 방문한 모든 노드는 1만큼 차감해 준다.

이번에도 두 번째로 맛있는 사탕을 탐색, 0-3 범위에 도달할 때까지는 노드 값이 4이기에 좌측 노드 탐색.

이후에는 좌측 노드의 값이 1이므로 해당 노드에는 두 번째로 맛있는 사탕을 찾을 수 없다. 따라서 우측 노드 탐색 수행.

우측에서는 전체 범위에서 두 번째로 맛있는 사탕을 찾기 위해선 해당 범위에서 첫 번째로 맛있는 사탕을 찾아야 하기에 순번을 1로 변경하여 탐색을 진행하면 된다. 마찬가지로 방문했던 노드는 1 차감한다.

1번 사탕의 개수 변동. 마찬가지로 리프노드를 만날 때까지 변경 값을 반영하면 된다.

마지막으로 두번째로 맛있는 사탕 탐색. 위에서 탐색한 방법과 같은 방법으로 탐색 후 3번을 반환 후 방문했던 노드의 값 1을 차감한다.

정답 코드

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

최장증가 부분수열(LIS) 문제다. DP로 푸는 방법, 이분탐색을 이용하는 방법, 세그먼트 트리를 이용한 방법 총 세 가지 방법이 있다. 

지난번에는 이분탐색을 통해 문제를 풀어보았고 현재 세그먼트 트리를 공부 중이라, 이번에는 세그먼트 트리를 이용하여 접근해 보았다. 이분탐색 풀이와 마찬가지로 O(N*logN)의 복잡도로 풀 수 있다.

풀이

해당범위의 LIS의 길이를 담은 구간 최댓값 세그먼트 트리를 생성한다. 초기값은 0이다.

주가를 입력받을 때, (가격, 인덱스) 튜플형태로 입력받은 뒤, 주가를 기준으로 오름차순, 주가가 같다면 인덱스 기준 내림차순으로 정렬을 한다. 이후 정렬된 주가정보를 순차 탐색하면서 세그먼트 트리를 갱신해 주면 된다.

원리는 다음과 같다. 주가가 작은 값부터 탐색을 시작하기에 들어오는 정보 (주가, 인덱스)는 곧 0부터 인덱스 i까지의 최장증가 부분수열의 길이이며, 해당 수열에 입력된 주가 값을 덧붙이면(+1) 새로운 최장증가부분수열의 길이를 구할 수 있는 것이다.

예제 [5,2,1,4,5,3]을 기준으로 세그먼트를 완성시켜 보자.

가장 먼저 0으로 초기화된 세그먼트트리와 (값, 인덱스) 튜플형태를 정렬한 모습이다.

가장 먼저 인덱스 0-2 값을 조회, 길이가 0이고 여기에 배열의 가장 최솟값인 1을 붙여 길이가 1인 LIS길이가 생성된다. 해당 범위인 0-2까지의 LIS길이가 1이 되는 것이다. 따라서 0-2 범위를 1로 갱신하게 된다.

다음 값은 2이며 범위 0-1에 해당하는 값을 참고, 해당 수열에 2를 붙여 갱신하게 된다. 다음과 같은 작업을 반복하면 된다.

0-5 범위의 최장수열에 3을 붙여 길이 2인 최장수열이 생성된다. 해당 범위의 트리에 값 갱신.

0-3 범위 조회 후 갱신

0-4 범위 조회 후 갱신

가장 마지막으로 0-0 범위 조회 후 갱신

다음과 같은 과정으로 트리가 완성되며 문제에서 요구하는 전체 범위의 최장증가 부분수열의 길이는 루트 노드에 담겨있게 된다.

정답 코드

스위프트의 경우 입력 부분에서 제약이 생긴다. 라인이 분리되어서 주가가 입력되는 경우가 들어오게 되는데, 기본적인 입력으로는 해결하기 까다로워 보였다. 결국 해당 문제 질문 게시판에서 발견한 honghoker님의 글을 참고해서 입력을 처리하였다.