목록2017/04/29 (1)
개인공부용123 프로그래밍 블로그
[백준] 9426(세그먼트 트리)
백준 9426문제는 N개의 원소중에서 K개의 부분집합원소의 중앙값들의 합을 구하는 문제입니다. 이 문제는 세그먼트 트리를 이용해서 풀었습니다. 세그먼트 트리의 각노드에는 노드들의 갯수를 저장하고있습니다. (리프 노드에는 해당 노드가 세그먼트 트리에있는지 없는지를 표시) 업데이트시 1, -1로 원소를 추가 삭제 가능합니다. 쿼리함수를 이용해서 서브트리에 대한 중간값에 해당하는 값을 찾을수있습니다. 세그먼트 트리는 보통 포화 이진트리이므로 값이 N개일 떄 높이는 O(logN)입니다. 즉 하나의 중간값을 찾는데 걸리는시간은 O(logN)이 걸립니다. 그러므로 세그먼트 트리를 이용한 최악의 경우 시간 복잡도는 약 O(NlogN)입니다. Worst Case time Complexity = O(NlogN) incl..
알고리즘문제
2017. 4. 29. 19:40