알고리즘 일지

문제 링크17139번: 습격자 초라기와 쿼리 (Normal) (acmicpc.net)습격자 초라기를 푼 사람은 알겠지만, 이런 넓혀나가면서 dp를 응용하는 풀이는 구간 단위로도 적용할 수 있다.구간단위로 적용 할 수 있으면, 바로 세그먼트 트리를 떠올릴 것이다. 구간단위로 분할 정복하는 것은 제일 쉽게 생각하면 세그먼트 트리가 유일하다. 물론 제곱근 분할법도 있지만, 어차피 구간에 대한 합을 구현해야 하니, Bucket 구현을 안 해도 되는 세그를 하는 게 마음이 편하다. 구간단위로 찾아놓은 dp 최적화 값들을 활용하여, 구간 두개를 합칠 때, 이전 찾아놓은 dp값들을 활용하면 된다. 무슨 dp값들이 필요할까?구간의 왼쪽위, 왼쪽아래, 오른쪽 위, 오른쪽아래의 사용여부에 따른 dp 값들을 관리하면 된다...

문제 링크27173번: 수열과 쿼리 43 (acmicpc.net) 27173번: 수열과 쿼리 43길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i: Ai 를 출력한다. (1 ≤ i ≤ N) 2 x y t: 만약 Ax, Ax+1, ..., Ay 중 t 미만의 수가 있다면 이 쿼리를 무시www.acmicpc.net 문제 풀이 따끈따끈한 수열과 쿼리 43이 나왔다. 원래는 이 글을 쓸 생각이 없었지만, 지인이 풀이가 보고싶다고 해서, 기왕이면 잘 써볼려고 써보게 되었다. 일단, 이 문제를 풀 경지라고 생각하고 정말 대충 풀이를 적으려고 한다. Segment Tree Beats를 완벽하게 이해하고 있다면, 조금 더 이해가 쉬워 질 것이다. 일단..

문제 링크 10070번: 벽 (acmicpc.net) 10070번: 벽 지안지아는 똑같은 크기의 벽돌을 쌓아서 벽을 만들고 있다. 이 벽은 n열의 벽돌로 되어 있는데, 각 열은 왼쪽부터 오른쪽으로 차례대로 0부터 n-1까지 번호가 매겨져 있다. 각 열의 높이는 서로 www.acmicpc.net 문제 풀이 1번 쿼리는 지정된 높이 미달인 벽이 있으면 그 높이까지 벽을 쌓아주는 쿼리이다. 요약하면, $1$ $l$ $r$ $h$ 에 대하여, $A_i := max(A_i, h)$ $(l \leq i \leq r)$를 수행한다. 2번 쿼리는 지정된 높이를 초과하는 벽이 있으면, 그 높이까지 벽을 없애주는 쿼리이다. 요약하면, $2$ $l$ $r$ $h$ 에 대하여, $A_i := min(A_i, h)$ $(l \..