leo020630의 블로그

시험기간 탓에 멈춰 있던 Class 9 밀기를 다시 시작했다. 그 동안도 몇 개 푼 문제가 있긴 한데, 좋은 풀이가 많길래 굳이 올리지 않았다. 문제 요약 무방향 그래프가 주어진다. 이 때, 어느 간선을 제거해도 그래프가 하나의 컴포넌트가 되기 위해 추가해야 하는 간선의 최소 개수를 구하고 실례를 구성하시오. 풀이 우선, 제거했을 때 그래프가 나누어지는 간선은 단절선이다. 따라서 단절선이 아닌 간선들은 두 정점을 union한다고 생각하고 그래프를 구성하면 트리가 된다. 단절선만 남긴 그래프이니 이는 당연하다. 단절선을 구할 때 멀티 에지가 들어오는 것만 조심하면 된다. 이제 트리에서 최소한의 간선을 추가해 잘 이어주는 것이 남았다. 개수는 대충 생각해보면 \(\lceil \frac{l}{2} \rceil..

매우 유명한 문제이다. 당연히 좋은 풀이글도 많고 다양한 풀이가 존재하지만, 좋은 문제라 정리하는 것이 의미가 있을 것 같아 따로 정리해본다. 더불어, LIS를 \(O(NlogN)\)으로 해결하는 방법에 대한 튜토리얼 글들을 보면 원리를 제대로 설명하지 않은 글들이 많아 이를 정확히 설명하고, 이 문제의 해법까지 이어가는 것이 이 글의 목표이다. 문제 요약 서로 다른 양의 정수로 이루어진 \(2 \times N\) 또는 \(3 \times N\) 행렬이 주어질 때, 각 행에서의 등수가 같도록 뽑을 수 있는 열의 최대 개수를 구하시오. 풀이 가장 윗 행을 기준으로 정렬하고 나면 \(M = 2\)인 경우 LIS (Longest Increasing Sequence), \(M = 3\)인 경우 Pair LIS ..

문제 요약 정점 \(N \leq 1000\) 개로 이루어진 트리가 있을 때, 루트를 제외한 정점 \(K \leq 100\)개를 선택해 순서대로 방문할 것이다. 이 때, 정점 간 이동은 항상 최단거리로 진행한다. 정점 \(K\)개와 순서를 잘 정해 이동거리의 합이 최대가 되게 하여라. 풀이 문제 조건이 독특해 약간 헤멨다. 우선, 제한이 적으므로 \(dp[v][i]\)를 \(v\)번 정점을 루트로 하는 서브트리에서 \(i\)개를 선택해 나올 수 있는 최적해로 정의하자. 이제 각 정점에서 해야 할 일은 자식 노드들의 DP값을 잘 합쳐주는 것이다. 이는 \(dp[v][i]\)를 \(dp[v][j]\)와 \(dp[c][i-j]\)로 분해해서 생각해주면 된다. 두 값은 이미 정해져 있으니 더해주어야 할 값은 두 ..

HeeJaYaa님의 추천으로 Class 9 문제들을 풀고 있다. Class 9 문제들은 인터넷에 풀이가 많지 않은 경우가 꽤 있어 푸는대로 풀이를 작성해보려 한다. 원래 어제부터 풀고 싶던 문제는 https://www.acmicpc.net/problem/9244 인데, 하루동안 생각해도 모르겠어서 넘어왔다. 혹시 저 문제 푸신 분 있으면 힌트 부탁드립니다.. 문제 요약 숫자로 이루어진 문자열이 주어질 때, 다음과 같은 두 쿼리를 처리해야 한다. 1번 쿼리 : 구간 \([l, r]\)에 위치한 숫자 \(x\)를 모두 \(y\)로 바꾼다. 2번 쿼리 : 구간 \([l,r]\)을 읽은 수를 998244353으로 나눈 나머지를 출력한다. 풀이 일단 업데이트 쿼리가 없다고 생각해보자. 그러면 세그트리의 각 노드에..

slah007 선배의 추천으로 풀게 된 문제이다. 푼지는 좀 됐는데, 시험기간 탓에 이제야 포스팅한다. 문제 요약 구간 \([L, R]\) 로 나타내어지는 선분 \(N\)개가 주어진다. 만약 두 선분이 겹칠 경우, 두 선분 사이의 거리를 1로 정의한다. \(A\)번 선분과 \(B\)번 선분의 거리를 구하는 쿼리를 \(Q\)번 처리하라. 풀이 일반성을 잃지 않고 두 선분이 겹치지 않으며 A가 B보다 앞에 있다고 가정하자. 당연하게도, B에 도달하기 위해서는 매 이동마다 가장 끝 좌표가 큰 선분으로 이동하는 것이 최적이다. 이렇게 같은 행동을 반복하는 문제는 DP, 그 중에서도 Sparse Table을 사용하면 해결할 수 있다. 다만, Sparse Table을 만들기 위해서 몇 가지 생각해야 할 부분이 존재..

그냥 백준을 돌아다니다 재밌어 보여서 풀게 된 문제인데, 풀고 나서 보니 다른 사람들의 풀이와 다른 것 같아 포스팅해보려고 한다. 문제 대충 저렇게 생긴 직교 다각형이 주어질 때, 햇빛에 의해 생기는 그늘의 길이를 구하는 문제이다. 풀이 코드를 까보니, 다른 분들의 풀이(이자 정해)는 전체 둘레에서 햇빛이 비치는 부분의 길이를 빼서 구하는 방식인 것 같다. 내 풀이의 발상 난이도는 저 풀이와 비슷하거나 조금 쉽고, 접근 방향이 약간 다르다. 여집합이 아니라 그림자의 길이를 직접 구해보자. 그림을 잘 보면, 이런 식으로 각 변에 의한 그림자 길이는 그 변과 같다는 사실을 직관적으로 관찰할 수 있다. 또한, 광원이 하나이기 때문에 그림자가 겹칠 가능성 또한 없음을 파악할 수 있다. 다각형을 이루는 점이 시계..

열심히 풀고 기여를 하러 갔는데, 다들 내 풀이와 방향성이 다른 것 같았다. 정해가 시간 복잡도 면에서도, 난이도 면에서도 조금 더 낫지만 내 풀이도 의미가 있다고 생각해 적어보려 한다. 해당 풀이는 7469 - K번째 수를 PST로 푸는 방법을 트리로 확장시켜 적용한다. 간단하게 요약을 하자면, 인덱스 순으로 세그트리를 \(N\)개 만든 후 \(R\)번째 세그트리에서 \(L-1\)번째 세그트리를 뺀 값으로 세그 이분탐색을 해서 K번째 수를 찾는다. (이 과정에서 배열의 각 수에 대해 좌표압축을 해 주어야 한다.) 세그 이분탐색이란 왼쪽 자식의 합과 K를 비교해 K가 크면 오른쪽, 그렇지 않으면 왼쪽으로 가는 작업을 반복하는 것을 말하며, 세그트리를 여러 개 만드는 것은 PST를 통해 수행할 수 있다. ..

랜덤 플레 디펜스를 하다 풀게 된 문제이다. 오렌지 컵 문제인데, 에디토리얼도 아직 없고 구글링했을 때 풀이가 나오지 않길래 내가 적어보려 한다. 앞으로도 푼 백준 문제들 중에 자료가 없는 것들은 이렇게 풀이를 작성할 예정이다. 문제 요약 오렌지 농장에 \(N\)개의 오렌지를 심을 수 있는 지점이 있다. 오렌지는 심은 후 \(k\)초가 지나면 수확이 가능하다. 모든 지점에 오렌지를 심고 모든 지점에서 오렌지를 수확하기 위한 최소의 시간을 구하여라. 풀이 \(DP[i]\)를 \(i\)번째 오렌지까지 모두 수확하고 i번째 지점에서 멈췄을 때의 최소 시간으로 정의하자. 그러면 다음과 같은 점화식을 통해 \(DP[i]\)를 구할 수 있다: \(DP[i]=min_{0

최근에 참여한 백준 대회 3개에 대해서 간략한 후기를 작성하려 한다. Good Bye, BOJ 2021 A. 2021은 무엇이 특별할까? (1 try, 00:02) 실버 하위 난이도의 구현 문제라 가볍게 구현해주었다. B. 예쁜 케이크 (1 try, 00:08) 언뜻 보았을 때 Hard한 소인수분해 알고리즘이 필요해 보여서 당황했지만, 식을 잘 들여다보니 답이 될 수 있는 경우는 \(9k\) 또는 \(3k+2\) 꼴이라는 것을 알 수 있었다. C. 성싶당 밀키트 (1 try, 00:18) 최근에 코드포스에서 파라메트릭 문제를 많이 보아서인지, 보자마자 파라메트릭이라는 것을 떠올릴 수 있었다. 오버플로우 처리가 약간의 issue였으나, 오버플로우가 생길 만한 범위라면 어차피 답이 되지 못해 상관없는듯 하다..