백준 Online Judge 문제
체크리스트
✅ 해결 🟩 미해결 🟩 포기
풀이에 걸린 시간: 2시간
- 풀이가 떠오른 과정
✅ 문제를 읽고 주어진 시간제한과 메모리제한 내에서의 풀이가 떠올랐다.
🟩 문제를 읽고 시간제한과 메모리제한 내에서 해결이 가능한 지는 모르겠지만 풀이가 떠올랐다.
🟩 문제를 읽고 풀이가 떠오르지 않았다.
🟩 문제가 곧바로 이해되지 않았다.
- 풀이 작성 과정
🟩 풀이를 아무런 도움 없이 작성하였다.
✅ 풀이를 관련된 알고리즘 지식만을 찾아 숙지한 채 작성하였다.
🟩 풀이를 남의 정답코드를 찾아 참고하여 작성하였다.
🟩 알고리즘 개념에 대한 공부를 하다 해당 개념에 대한 문제를 찾았고, 풀었다.
알고리즘 개념
-
세그먼트 트리(Segment Tree)
세그먼트 트리란, 완전이진트리의 한 종류로 특정한 배열에 대하여 전체구간을 대상으로 하는 루트노드부터 시작하여 리프노드까지, 각 노드의 대상구간을 이분할하여 각 자식에게 할당하는 형태의 트리이다. 모든 노드는 구간정보와 배열 내에서의 특정값(누적합, 최솟값, 최댓값 등)을 그 데이터로 담고 있으며 루트노드는 배열 전체의 정보를, (Bottom-up 형태로 구현한 세그먼트 트리의 경우) 리프노드는 길이가 1인 각 구간의 정보(배열의 모든 각각의 원소)를 담게 된다.
배열에 대하여 특정 구간에 대한 합, 최댓값, 최솟값 등 특수한 값을 탐색할 때 선형탐색에서 필요한 시간복잡도를 기준으로 하여, 연산의 횟수가 많아지거나 배열의 특정 값을 계속해서 갱신하는 등의 행위가 추가된다면 세그먼트 트리 형태를 통하여 이를 수행하는 것이 시간복잡도를 줄이는 하나의 방법이 된다.
트리의 생성(init)에는 lazy propagation을 구현할 수 있는 탑-다운(Top-down)형태의 생성과 리프레벨의 탐색으로 전체 배열을 확인할 수 있는 바텀-업(Bottom-up)형태의 생성이 있다.
특정 구간에 대한 합, 최댓값, 최솟값 등을 계속해서 요청하는 쿼리함수(Query)는 세그먼트 트리의 루트노드부터 시작하여 목표 구간과 노드 각각이 가지고 있는 구간의 포함관계를 비교하여 필요한 최소한의 value들을 수집한다.
배열 특정 인덱스의 값을 새로운 값으로 갱신하는 함수는 루트노드부터 시작하여 구간 내에 목표 인덱스가 포함되어 있다면 이를 반영시키고 그렇지 않다면 리턴하는 형태로 재귀한다. -
병합정렬(Merge Sort)
병합정렬이란 정렬 알고리즘 중 대표적인 분할정복(Divide and Conquer) 정렬로, 전체 배열을 분할 가능할 때까지(길이가 1이 될 때까지) 분할(Divide)하고, 분할되었던 역순으로 병합(Merge)한다. 모든 병합 과정에서 각 분할된 두 개의 부분배열에 동시에 0번째 인덱스부터 비교하여 작은 값을 temp list에 push하고 작은 값을 가리키는 이터레이터만 증가시키는 방식으로 두 부분배열의 모든 원소를 탐색하고, 이를 통해 정렬된 병합 부분배열로 병합된 결과를 대체한다. 이런 과정을 거치면 병합과정에서 계속하여 정렬이 이루어지고, 마지막으로 병합된 배열은 전체 원본 배열을 정렬한 결과가 된다. -
머지소트트리(Merge Sort Tree)
세그먼트 트리 중 하나로, 각각의 노드는 전체 배열에 대하여 가지고 있는 구간 내의 원소가 정렬되어있는 배열을 value로 갖는다. -
파라메트릭 서치(Parametric Search)
풀이과정
- 문제의 조건에 맞게 머지소트트리를 생성하여 쿼리문을 처리해주었다.
머지소트트리를 생성하는 것은 어렵지 않았다. 문제는 쿼리문이었는데, 일반적인 세그먼트 트리처럼 구간의 포함관계에 따라서 쿼리를 처리하도록 하는 방법으로는 결국에 목표구간의 조각을 포함하고 있는 모든 노드들을 병합정렬하는 과정을 거쳐야하므로 세그먼트 트리의 시간복잡도상의 이점을 활용하지 못하여 TLE가 발생하고 말았다.
여기서 한 시간 넘게 고민하다가 결국 구글링을 동원하였는데, 이 문제는 쿼리함수의 구현에서 파라메트릭 서치의 개념을 빌려오지 않으면 위에서 말한 세그먼트 트리의 이점을 살려낼 수 없는 구성이었다. 파라메트릭 서치에 대한 개념은 이분탐색을 공부하면서 함께 알고 있었지만, 이러한 문제에도 적용될 수 있다는 것과 이를 떠올리지 못했다는 것으로 아직 개념적용에 대한 직관과 경험적인 측면이 많이 부족하다는 것을 느꼈다. 쿼리를 파라메트릭서치로 구현한 자세한 내용을 코드에 주석으로 포함시켜 놓았다.
코드
from math import ceil, log2
import sys;rl = sys.stdin.readline
n,m = map(int,rl().split())
An = list(map(int,rl().split()))
leafLevel = int(log2(n))+1
#왼쪽리스트와 오른쪽리스트를 입력하면 머지소트된 리스트를 반환하는 함수
def merge(leftList:list,rightList:list):
rtnList = []
leftIter = 0
rightIter = 0
while leftIter < len(leftList) and rightIter < len(rightList):
if leftList[leftIter] < rightList[rightIter]:
rtnList.append(leftList[leftIter])
leftIter+=1
else:
rtnList.append(rightList[rightIter])
rightIter+=1
rtnList+=leftList[leftIter:]
rtnList+=rightList[rightIter:]
return rtnList
#입력 리스트를 리프노드 레벨에 초기화시킨 후 부모를 따라가면서 노드를 채워주는 형태
#리프노드의 n번째 이후 노드가 구간값을 가질 수 있도록 설정해야함에 주의.
def init():
for i in range(2**leafLevel):
MST[(2**leafLevel)+i][0] = MST[(2**leafLevel)+i][1] = i+1
for i in range(n):
MST[(2**leafLevel)+i][2].append(An[i])
level = leafLevel-1
while level>=0:
for i in range(2**level,2**(level+1)):
MST[i][0] = MST[i*2][0]
MST[i][1] = MST[i*2+1][1]
MST[i][2] = merge(MST[i*2][2],MST[i*2+1][2])
level-=1
MST = [[0,0,[]] for _ in range(2**(leafLevel+1))]
#MST의 노드는 [구간시작,구간끝,[자식노드 머지한 리스트]] 형태.
MST[0] = None
init()
#노드에서 x보다 큰 원소가 나오는 첫 번째 위치를 반환.
def upperBound(x,nodeIndex):
left = 0
right = len(MST[nodeIndex][2])-1
mid = 0
while left<right:
if MST[nodeIndex][2][mid]<=x:
left = mid + 1
else:
right = mid
mid = (left+right)//2
if mid == right:
if MST[nodeIndex][2][mid] <= x:
return len(MST[nodeIndex][2])
else:
return right
if MST[nodeIndex][2][left] > x:
return 0
return left + 1
#목표가 (start~end), 노드의 구간이 (left~right)
#start부터 end까지의 구간에서 x라는 수보다 작은 수의 개수가 몇 개인가요?
#라는 질의를 1번 노드부터 재귀하여 리턴함.
#만약에 노드의 구간이 목표의 구간에 포함된다면, 노드의 리스트에서
#x보다 큰 가장 작은 수의 인덱스를 리턴함(upperBound). 이는 리스트 안의 인덱스이므로
#x보다 작은 수의 개수라고 할 수 있음.
#그리고 이를 모두 더하면, 목표 구간에 포함되는 모든 노드 내에서의 x보다 작은 수의 개수가 됨.
def query(x,start,end,nodeIndex):
left = MST[nodeIndex][0]
right = MST[nodeIndex][1]
if left > end or right < start:
return 0
elif start<=left and right<=end:
return upperBound(x,nodeIndex)
return query(x,start,end,nodeIndex*2)+query(x,start,end,nodeIndex*2+1)
#목표 구간에 포함되는 모든 노드의 리스트 내에서의 x보다 작은 수의 개수가 k-1개가 됐을 때,
#x값이 목표 구간 안에서 k번째 수의 값이 됨. 비교연산에 따라 start가 그 값이 되면,
#start는 더 이상 증가하지 않고 end만 감소하다가 start와 end의 대소가 역전되고 while문 탈출.
for _ in range(m):
i,j,k = map(int,rl().split())
start = -(10**9)
end = 10**9
while start<=end:
mid = (start+end)//2
result = query(mid,i,j,1)
if result<k:
start = mid + 1
else:
end = mid - 1
print(start)
