Hyun's_Devlog

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

세그먼트트리 문제다.

풀이

구간의 최솟값이 담기는 세그먼트트리를 구현, 출력과 갱신을 담당하는 함수를 구현하여 접근하였다. 

예제를 기준으로 만든 세그먼트 트리다. 리프노드부터 더 작은 값을 부모노드로 결정하여 만들면 된다. 트리의 갱신을 하게 된다면 가장 먼저 리프노드 값의 갱신이 이루어지고, 해당 노드부터 루트노드까지의 대소비교를 진행하면서 새로운 값으로 갱신을 해주면 된다.

재귀호출을 통해 갱신이 이루어지는데, 해당 호출 범위가 갱신인덱스가 포함되지 않는 구간이라면, 바로 해당 노드의 값을 반환하여 반대편 구간과의 대소비교를 진행하면 된다.

정답 코드