gubshig

https://www.acmicpc.net/problem/8193한국어 지문에 사소한 오류가 있는데, 1번 정점과 2번 정점은 항상 연결되어있다는 조건이 빠져있다. 문제를 간단히 요약하면,가중치 없는 무향 그래프 $G = (V, E)$가 주어질 때, 간선을 최대한 많이 추가해야한다. 단 이때 1번 정점과 2번 정점 사이의 최단거리가 5 이상임이 유지되어야 한다. 보통 우리는 자료구조를 다룰 때 간선을 삭제하는 것 보다 추가하는 것이 쉽기에 이를 활용하는 경우가 많다. 그러나 이 문제의 경우엔 완전그래프에서 간선을 최소한으로 삭제하는 문제로 생각해주는 것이 편하다. 문제를 다음과 같이 환원하자. 완전그래프와 지워지면 안되는 간선의 집합이 주어졌을 때, 간선을 최소한으로 삭제하여 1번 정점과 2번 정점의 최..

https://justicehui.github.io/teach/gubshig/ 안녕하세요. 김준호입니다. 알고리즘 / 코딩테스트 과외 합니다.프로필소속선린인터넷고등학교 제117기 소프트웨어과 (2022/03/02 ~ 2025/02/07)한양대학교 25학번 산업공학과 (2025/02/25 ~ ) 온라인 저지 프로필https://www.acmicpc.net/user/gubshig - 1009 solvedhttps://solved.ac/profile/gubshig - Diamond II 2574https://codeforces.com/profile/cerise_bouquet - Rating (max. expert, 1726)https://atcoder.jp/users/revue - Rating (max. 16..

https://www.acmicpc.net/problem/20617 요약: $1, 2, 3$으로 이루어진 길이 $n \leq 10^6$의 수열 $a$와 길이 $m \leq 10^6$의 수열 $b$ 의 Longest Common Increasing Subsequence (LCIS) 를 구하라. 편의상 $m = n$이라 하겠다. 만약 수열이 $1, 2$로만 이루어졌다면 어떨까? $SA_x(l, r)$을 $a$의 구간 $[l, r]$에서 $x$의 개수라 하자. $SB_x(l, r)$도 비슷하게 정의하자. $a$에선 구간 $[1, i_a]$에서 $1$만을, 구간 $[i_a + 1, n]$에서 $2$만을 선택하고, $b$에선 구간 $[1, i_b]$에서 $1$만을, 구간 $[i_b + 1, n]$에서 $2$만을 ..

https://www.acmicpc.net/problem/32766 이런 형태의 문제는 우선 트리를 만들고 생각하고 싶다. 각 직사각형의 외부 중 가장 가까운 직사각형을 그 직사각형의 부모라 하자. 모든 직사각형을 포함하는 직사각형을 추가해주면, 이 직사각형을 루트로 하는 하나의 트리가 생긴다. 그럼 쿼리에서 물어보는 것이 무엇일까? 트리에서 쿼리로 주어진 점을 포함하는 직사각형 중 깊이가 가장 작은 정점을 잡아보자. 그럼 트리에서 경로 쿼리가 된다. 트리의 어떤 정점에서 부모로 가는 간선은 그 정점에 해당되는 직사각형이 가지고 있는 색 중 적어도 하나를 지나야 한다는 관찰도 할 수 있다. 이때 색은 $6$가지기 때문에, 트리의 경로 중 임의의 색 조합만 지나는 경로가 존재하는지에 대한 문제를 $2^6$..

A. 그냥 하면 된다B. 같은 변이 존재하는지 확인하면 된다C. 인접해 있는 같은 문자들을 묶어주면 조합식을 세우기 편해진다D. $2^{5 \cdot K}$개들의 최댓값에 대해 완탐해주면 된다.E. 기우성에 대해 생각해보는 똑똑한 풀이가 존재하고, bfs를 통해 규칙 찍기를 하는 풀이도 존재한다.F. 길이가 $B$인 선분을 만들 때 $B$보다 작은 선분들만 이용해줘야 함을 관찰하자. $B$와 선분들의 길이 $L$에 대해 정렬해주고, $dp(i) = $ 물건의 가격이 $i$ 일때 가능한 선분 합의 최댓값을 계산해주면 된다. 그럼 $A$, $B$ 쿼리에 대해 $dp(A) \geq B$ 를 확인해주면 된다. $\mathcal{O}(NX + Q)$에 풀 수 있다. G, H는 풀이가 상당히 신기한 것 같다I는 모..

https://gubshig.tistory.com/49을 읽고 오면 좋다.MDMTSP(Multi Depot Multiple TSP)https://www.acmicpc.net/problem/20185 (814-3) 이 문제의 정확한 명칭을 모르겠으나 가장 유사한 문제론 MDMTSP(https://www.uv.es/~benavent/MDMTSP/report_MDMTSP.pdf)가 있는 것 같다. 이 문제를 요악하자면,$N$개의 도시를 $K$명의 외판원에게 분배하자. 각 외판원은 분배받은 도시를 순회할 순서를 정하여 모든 도시를 방문하고 다시 시작 도시로 돌아온다. 이때 각 외판원이 이동하는 시간의 최댓값을 최소화하라.$K = 1$이면 이 문제는 TSP와 동일하기에, NP-hard이다.현실 세계에서도 다양한 ..

0.  서론2학년 때 학교 프로젝트로 TSP에 대해 다룬 적이 있는데, 이와 관련하여 MDMTSP(814-3)에 대한 해결책을 요즘 찾고 있어 정리해볼까 한다. TSP(외판원 순회 문제)는 대표적인 NP-complete(결정 문제의 경우) 문제 중 하나이다. ps에선 흔히 bit dp라 불리는 테크닉을 처음 접할 때 많이 소개되곤 한다. $\mathcal{O}(N \cdot 2^N)$ 정도의 해결책은 널리 알려져 있지만 P = NP가 아닌 이상 다항 시간 해결책을 기대하긴 어렵다. 근사해를 구하기 위한 시도를 해볼 수도 있지만, 다항 시간 근사해 조차 구하기 힘들다. 그러나 TSP로 환원 되는 다양한 문제들이 존재하고 현실 세계에서 이에 대한 해결책이 필요한 경우가 있다. 이 글에서는 TSP를 해결하는 ..

1. 리차오 트리리차오 트리는 주로 CHT(Convex Hull Trick)이라 불리는 다음과 같은 문제에 사용된다.직선 $ax + b$ 추가$x$가 주어질 때 직선들 중 $ax + b$의 최댓값 쿼리물론 최솟값 쿼리 또한 해결 가능하다.이때 직선의 기울기 $a$가 단조증가/단조감소하고, 쿼리로 주어지는 $x$가 단조증가/단조감소 하는 경우 스택을 이용한 업데이트, 쿼리 amortized $O(1)$ 해법이 존재한다(https://justicehui.github.io/hard-algorithm/2019/01/25/CHT/).  리차오 트리는 단조 조건이 없는 경우에도 사용할 수 있지만, 업데이트와 쿼리가 $O(\log X)$ ($X$는 쿼리로 주어지는 수의 범위)가 걸린다는 단점이 있다. 단조 조건이 있..

수능 공부 끝에 다시 돌아왔습니다. 이번 5월에 1차에서 동상을 받아서 본선에 진출하게 되었습니다. 정시 때문에 딱히 준비를 하진 않았고 대회 1~2주 전 즈음에 재활을 조금 했습니다. 생각보다 좋은 결과를 받았습니다. 아직 가채점 결과가 나오진 않았지만 운이 좋으면 은상을 노려볼 수 있지 않을까요? 14:21:16 가로등(1번) 100점대회는 13:30분에 시작했습니다.시작하고 1번 문제를 읽었습니다. 일단 구간을 적당히 $2N$개로 쪼개서 최솟값을 관리해줄 수 있는 자료구조에 넣고 $K$번 뽑아주면 될 것 같았습니다. 구현을 딱히 생각 없이 하다 조금 틀리고 1시간 정도 지나서 100점을 받았습니다. 쉬운 문제였는데 구현도 말리고 오래 걸려서 이때까진 대회가 망한 줄 알았습니다. 16:27:34 xo..

https://youtu.be/cof3wZFfDrY?si=RaH9QREx484eQ2cV 중등부 왜케 좋지 A - split('.') B - toroidal 이 무슨 뜻인가 했는데 그냥 움직일때마다 mod H, mod W 해주면 되는 그림으로 그리기는 힘들 것 같은 무언가? 더라고요. 아무튼 구현 하면 됩니다. C - 구간합을 쭉 구해준 후 min값을 찾고 총합에서 빼주면 됩니다. D - 첫번째 플레이어의 위치와 두번째 플레이어 위치의 경우의 수는 $O(N^4)$개 이기에, 각 상태를 정점으로 두고 bfs를 돌려주면 됩니다. E - $dp_i$ = i번째 수로 끝나는 가장 긴 smooth subsequence 라 하면, $dp_i$ = $\min_j$ $dp_j$ ($a_i - D \leq a_j \leq..