백준 24527번 이상한 나라의 갈톤보드
백준 24527번 이상한 나라의 갈톤보드 풀이. 구간 업데이트를 lazy segment tree와 imos 방식으로 각각 풀며 도착 구간 계산을 정리한다.
모든 태그
주제
#binary-search
6편의 기록
-
-
백준 7469번 K번째 수
백준 7469번 K번째 수 풀이. 머지 소트 트리로 구간 내 특정 값 이하의 개수를 구하고 이분 탐색으로 K번째 수를 찾는다.
-
백준 2243번 사탕상자
백준 2243번 사탕상자 풀이. 맛별 사탕 개수 합을 세그먼트 트리에 저장하고, 순위 기반 탐색으로 원하는 사탕 맛을 찾는다.
-
백준 14003번 가장 긴 증가하는 부분 수열 5
백준 14003번 가장 긴 증가하는 부분 수열 5 풀이. O(N log N) LIS 과정에서 이전 값을 추적해 실제 증가 부분 수열을 복원한다.
-
백준 14464번 소가 길을 건너간 이유 4
백준 14464번 소가 길을 건너간 이유 4 풀이. 닭이 도와줄 수 있는 소 중 종료 시간이 가장 빠른 소를 고르는 그리디 매칭을 설명한다.
-
백준 12015번 가장 긴 증가하는 부분 수열 2
백준 12015번 가장 긴 증가하는 부분 수열 2 풀이. 길이별 최소 끝값을 유지하고 이분 탐색으로 O(N log N)에 LIS 길이를 구한다.