'최소값찾기' 태그의 글 목록

요새 코테 철이 되었습니다. 저도 간간히 구현력을 잃어버리지 않기 위해서 조금씩 복기만 하고 있습니다. 백준 11003번 문제는 최솟값을 구하는 문제입니다. 특정 구간 [e-k, e]에서의 최솟값을요. 단, 0보다 작은 위치의 구간은 무시하고 구해야 합니다. 별로 어렵지 않아 보이는데, 문제는 n이 500만입니다. 입력 받느라 시간이 많이 가는 건 흐음. O(n)으로 줄일 수 있습니다. 다들 아시는 기법을 소개하도록 하겠습니다. 관찰을 해야 할 것은 2가지 상황입니다. 어떠한 데이터가 추가되는 상황하고, 제거되는 상황. i번째에 있는 데이터가 제거되면, 더 이상 추가되지 않는다는 것을 관찰하는 것 또한 포인트입니다. 현재, 이런 식으로 데이터가 들어갔다고 해 보겠습니다. 그리고 저는 7번째 위치에 있는 ..