백준 24527번 이상한 나라의 갈톤보드
구간 업데이트를 lazy 세그먼트 트리와 imos 차분 배열 두 가지로 풀고 도착 구간 계산하기
모든 태그
주제
#binary-search
글 6개
-
-
백준 7469번 K번째 수
머지 소트 트리로 구간에서 어떤 값 이하인 수의 개수를 구하고 이분 탐색으로 K번째 수 찾기
-
백준 2243번 사탕상자
맛별 사탕 개수 합을 세그먼트 트리에 두고 순위를 따라 내려가며 원하는 사탕 찾기
-
백준 14003번 가장 긴 증가하는 부분 수열 5
O(N log N) LIS를 구하며 값이 갱신될 때마다 이전 원소를 기록해 실제 수열을 복원하는 방법
-
백준 14464번 소가 길을 건너간 이유 4
닭이 도울 수 있는 소가 여럿이면 가장 먼저 건너기를 끝내는 소를 고르는 그리디 매칭
-
백준 12015번 가장 긴 증가하는 부분 수열 2
길이별로 가장 작은 끝값을 유지하고 이분 탐색으로 갱신하는 O(N log N) LIS