목록전체 글 (19)
알고리즘 일지
안녕하세요. 참가자 여러분들! 2023 SW - IT Contest에 운영진으로써 참여하게 된 황현석이라고 합니다. 이번 운영진 체험(?) 비스무리한 활동을 하며, 얻어가는 것도 배워가는 것도 많은 뜻깊은 좋은 시간이었다고 생각합니다. 대회 당일날 딱봐도 군인처럼 생긴 이상한 아저씨가 한명 돌아다니고 있었는데요!.. 저였습니다.. 그냥 휴가를 나왔는데, 대회 일정이랑 겹쳐 있어서 운이 좋았네요!!... 오랜만에 학교 공기도 쐐고.. 흐음~~ 공기가 별로 좋지는 않았어요.. 1등이.. 22학번 최약체라... 그중 최약체가 1등을 하게 되었군요. 제가 빨리 복귀해야겠어요. 그리고 이번에 1등한 최약체는 내년에는 군대에 있겠지만, 출제에 참여 할 수 있도록 제가 강제 조취하겠습니다. 저는 23. 1. 17일날..
https://www.acmicpc.net/problem/25353 25353번: 게임의 꽃주어진 트리에서 길이가 가장 긴 증가 경로는 번호가 4, 2, 5인 정점을 순서대로 지나는 경로이다.www.acmicpc.net 생각 나는 걸 순서대로 적어 놓은 곳입니다. 풀이 1 A [i]를 i의 서브트리로 가는 방향에서 가장 긴 증가 경로의 길이, B [i]를 증감경로 라고 하자. 그럼 정답은 모든 정점 i에 대해, max(A[i] + B[i] - 1)이다. 초반에 A와 B배열은 dfs를 이용하여 , O(N)에 찾을 수 있다. 어떻게 하면, A와 B배열을 빠른 속도로 업데이트할 수 있을까? 풀이 2 순서에 의해 연결될 수 있는 수열에 대해 가중치 1, 없는 수열에 가중치 -1e 9를 부여, 그 후 최대 연속합..
PS가 절실히 하고 싶다. 요즘은 폰코딩을 해볼까 진짜 진지하게 고민하고 있다. 폰으로 아직 안배운 알고리즘 논문이나, 어려운 문제, 신기한 발상들을 보면서, 그 대단한 발상들과 알고리즘을 빨리 내 손으로 키보드를 두드려서 구현하고 싶다. 진짜, 키보드 주세요;;
문제 링크 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 \..