알고리즘 일지

옛날에 나와 지금의 내가 어느정도 차이가 있는지 확인하고 싶어, 옛날에 접근도 못했던 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를 완벽하게 이해하고 있다면, 조금 더 이해가 쉬워 질 것이다. 일단..

문제 링크 27114번: 조교의 맹연습 (acmicpc.net) 27114번: 조교의 맹연습 첫 번째 줄에 각각 좌로 돌아, 우로 돌아, 뒤로 돌아에 들어가는 에너지를 나타내는 세 정수 $A, B, C$와 사용하고자 하는 총 에너지양을 나타내는 정수 $K$가 공백으로 구분되어 주어진다. $(1\leq A,B www.acmicpc.net 간단한 문제니 풀고 무조건 이글을 읽어봤으면 좋겠다. 문제 풀이를 설명하기전에 왜 이문제를 풀이하는지 부터 설명하겠다. 이 풀이는 쓰는 이유는 많은 사람들이 흔히 dx dy 테크닉이라고 불리는 편한 방법에 대해, 그래프에서의 탐색에서만 쓸 수 있다고 사고가 매몰 되어있어서 쓰게되었다. dx dy 테크닉는 그래프 탐색 코드를 굉장히 줄여주는 코드 작성방법이다. 1 2 3 4..

문제 링크 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 \..

배운 알고리즘을 정리 해 놓을려고 한다. 백준 핸들은 다음과 같으며, 원래 질문을 디스코드로 많이 받지만, 이제 군대가서 못받는다. 디스코드 : 황현석#9999 사용자 명 : hy3on_se0k hhs2003 정보 (acmicpc.net) 왠만하면, 알고리즘은 그때그때 구현하는 것이 좋다고 생각한다. 템플릿 만들어 놓고 하는 것은 연습할 때는 좋지 않다고 생각한다. 그리고 코딩하면서 타자 많이 치다보면, 실수도 점점 줄어들고, 타자도 점점 빨라진다. 물론 좀 어려운 알고리즘 한정이다. 너무 왤논은 귀찮으면 템플릿 만들어서 쓰자. 넓은 의미로써의 알고리즘은, 그냥 모든 문제 해결 과정의 서술이다 즉, 과정으로 서술 할 수 있는 모든 코드다. 하지만, 여기서는 좁은 의미로 특정 문제에 대하여, 그 문제를 유..