알고리즘 일지

옛날에 나와 지금의 내가 어느정도 차이가 있는지 확인하고 싶어, 옛날에 접근도 못했던 1006번 초라기 문제를 자력솔 하고, 그 연계문제를 풀게 되었다. 보통 이런 넓혀나가면서 dp를 응용하는 풀이는 구간 단위로도 적용할 수 있다. 문제를 보자마자 구간 dp를 정의하고 분할 정복하면 되겠구나를 떠올렸고 이런 거는 세그먼트트리나 제곱근 분할로 해야 한다. 제곱근 분할을 사용해도 구간합을 구현해야 하기에 그냥 구현량이 적은 세그를 선택했다. 구간단위로 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 \..