알고리즘 일지

옛날에 나와 지금의 내가 어느정도 차이가 있는지 확인하고 싶어, 옛날에 접근도 못했던 1006번 초라기 문제를 자력솔 하고, 그 연계문제를 풀게 되었다. 보통 이런 넓혀나가면서 dp를 응용하는 풀이는 구간 단위로도 적용할 수 있다. 문제를 보자마자 구간 dp를 정의하고 분할 정복하면 되겠구나를 떠올렸고 이런 거는 세그먼트트리나 제곱근 분할로 해야 한다. 제곱근 분할을 사용해도 구간합을 구현해야 하기에 그냥 구현량이 적은 세그를 선택했다. 구간단위로 dp 되어있는 최적값들을 활용하여, 새로운 구간을 만들 때, 필요한 dp는 합쳐지는 경우의 수를 다 표현하는 dp를 찾으면 된다. 비트마스킹을 이용하여, 구간마다 왼쪽 위 왼쪽아래 오른쪽 위 오른쪽 아래를 쓰는 경우를 표현하여 dp최적값을 적용한다. 합칠 때 ..

문제 링크https://www.acmicpc.net/problem/31226https://www.acmicpc.net/problem/23049 문제 풀이 임의의 점에서 최대로 이동하면 사이클에 포함된 임의의 노드의 번호를 알 수 있다. 이 번호를 v라고 하자. 개수가 N일때, 2sqrt(N)의 질의로 찾을 순 있는데 900번으로는 어케 찾는거지 ㅜ 24.3. 4 쿼리를 날릴 때 거리가 굉장히 길다. 왜 길까? 정답은 1부터 1,000,000 까지 있다. 1,000,000! 을 k라고 하자. query(v, k) = v 가 된다. 이것을 응용하는 것 아닐 까? 답이 될 수 있는 정답의 경우의 수를 적절히 압축하여 곱한뒤, 거리 쿼리를 날리고 자기 자신으로 되돌아오는 쿼리를 적절히 빨리 발견하여, 소인수 분..

문제 링크9250번: 문자열 집합 판별 (acmicpc.net) 문제 풀이 KMP를 이용한 브루트 포스 풀이로, 문제를 제한시간내에 풀지 않았던 문제였다. 클래스 8+가 깨져있길래, 살펴 보았더니, 이 문제의 데이터가 강력하게 업데이트 되어 있었다. 그래서 아호코라식을 살짝 보았다. 아호코라식은 자료구조 Trie 에서의 Kmp를 적용하는 것을 말한다. 이미 kmp는 배웠었고, Trie 도 알아서, 그냥 구현했다. 아호코라식의 구현은 dfs를 통해 포인터를 리턴하는 것으로 간단하게 하였다. 말 그대로 아호코라식을 이용하면, 문자열 집합에서 매칭을 선형으로 탐색할 수 있다. 기존풀이는, 문자열 집합 $\textbf{T}$ 에 대해, $\textbf{T}$를 Trie 자료구조를 이용하여, 저장한다음, 매칭 대..

문제 링크 27989번: 가장 큰 증가하는 부분 수열 2 (acmicpc.net) 27989번: 가장 큰 증가하는 부분 수열 2 길이가 N인 수열에서 0개 이상 N-1개 이하의 원소를 지워서 만든 수열 중, 길이가 1이거나 임의의 인접한 두 항 중 뒤의 항이 앞의 항보다 큰 수열을 증가 부분 수열이라고 한다. 양의 정수 N개로 www.acmicpc.net 문제 풀이 $O(N\log N)$ $dp[x]$를 x를 마지막으로 하는 증가하는 부분 수열 의 합중 가장 큰 값이라고 하자. 1번째 수부터, 마지막 수까지, 그 숫자와 범위를 마지막으로 하는 부분 수열중 가장 큰 값을 구해보자. 즉, 모든 $i$에 대해, 구간 $[1, i]$ 에서, $A_{i}$로 끝나는 증가수열 중, 가장 큰 합을 $dp[A_{i}]..

문제 링크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) 왠만하면, 알고리즘은 그때그때 구현하는 것이 좋다고 생각한다. 템플릿 만들어 놓고 하는 것은 연습할 때는 좋지 않다고 생각한다. 그리고 코딩하면서 타자 많이 치다보면, 실수도 점점 줄어들고, 타자도 점점 빨라진다. 물론 좀 어려운 알고리즘 한정이다. 너무 왤논은 귀찮으면 템플릿 만들어서 쓰자. 넓은 의미로써의 알고리즘은, 그냥 모든 문제 해결 과정의 서술이다 즉, 과정으로 서술 할 수 있는 모든 코드다. 하지만, 여기서는 좁은 의미로 특정 문제에 대하여, 그 문제를 유..