qwerasdfzxcl의 ps 블로그 qwerasdfzxcl의 ps 블로그

길이가 각각 $N$, $M$인 두 문자열 $A$, $B$의 LCS (Longest Common Subsequence)을 구하는 문제는 매우 유명한 문자열 비교 문제이며, 이는 간단한 dp로 $O(NM)$에 해결할 수 있음이 알려져 있다. 또한, 이를 더 빠르게 하기 힘들다는 것도 알려져 있다. 이 글에서는 $A$와 $B$의 substring의 LCS를 구하는 문제인 semi-local LCS에 대한 빠른 알고리즘을 설명한다. 내용이 매우 길고 복잡하기 때문에, 이 글에서는 핵심적인 내용만 요약해서 설명할 것이며, 자세한 증명은 모두 생략할 것이다. 목차 1. ALCS algorithm 2. Seaweed braids 3. Unit-Monge matrix distance multiplication 4. P..

06/27 학교 수업시수 채워야 해서 불참했다. 06/28 BOJ 8243 (POI 12/13 Arch) / O 왕이 1번 노드에서 시작해서 트리 위를 움직이는데, 왕이 도착한 노드는 색칠이 된 상태여야 한다. 현재 왕의 위치는 알 수 있지만, 왕이 어디로 갈지는 모른다. 하루에 칠할 수 있는 노드의 최대 개수를 $X$개라고 할 때, 조건을 만족하도록 할 수 있는 $X$의 최솟값을 구해야한다. $X$에 대한 이분탐색 + 트리 dp로 해결가능하다. BOJ 11746 (Landscape Improved) / O 돌 $N$개를 바위들 위에 적절히 쌓아서 꼭대기의 높이를 최대화해야 한다. 답에 대한 이분탐색을 한다고 가정하고, 각 x좌표에 대해 그 지점에 꼭대기가 있을 경우 돌이 몇 개 필요한지를 세그트리 + ..

1. 국대교육은 아침연습 3문제, 오후실습 3문제로 구성되어있다. 글에 적힌 순서대로 아침연습 123번, 오후실습 123번이다. 2. O는 대회 시간 내로 AC를 받은 문제, △는 업솔빙을 한 문제, X는 업솔빙 안 한 문제이다. 06/21 이 날은 학교 수행 때문에 교육을 빠졌다. 06/22 BOJ 22491 (Repairing) / X 파이프와 밸브가 여러 개 있고, 밸브를 적절히 잠궈서 끝점에 물이 못 흘러들어가게 해야 한다. 이때, 물이 안 흐르는 구간의 길이의 합을 최소화해야 하고 이 값을 출력해야한다. 대충 그래프를 만들었다고 생각하면 끝점에서 bfs 같은걸 돌려서 가장 가까운 밸브들을 전부 잠근 다음 시작점에서 물을 흘려보내서 계산을 하면 될거같다. AC를 받은 사람이 없어서 맞는지는 잘 모..

어떤 점 x에서 시작해서 방문할 수 있는 점의 집합을 A_x라고 합시다. A_x의 값이 최솟값이라면, A_x의 임의의 원소 y에 대해 A_y = A_x를 만족합니다. 이러한 집합 A_x들을 "최소 집합"이라고 합시다. 구하고자 하는 집합은 최소 집합의 합집합입니다. dfs를 다음과 같은 규칙에 따라 돌려봅시다. 현재 dfs tree를 만들고 있는 상황이라고 생각하고, dfs(v)가 실행중이라고 합시다. v의 서브트리의 원소를 S_v라고 할 때, 1. S_v와 S_v의 여집합을 연결하는 간선 중, S_v에서 얻은 key를 이용하여 갈 수 있는 간선을 차례로 확인합니다. (주의: S_v는 원소가 계속 추가됩니다.) 2. 그 간선을 타고 가서 나온 정점 w를 방문한 적이 없다면 dfs(w)를 호출합니다. df..

문제 셋: 1번 IOI09 POI (https://www.acmicpc.net/problem/5462) 2번 BOI06 Coin Collector (https://www.acmicpc.net/problem/3368) 3번 CEOI13 Adriatic (https://www.acmicpc.net/problem/9284) 4번 KTST20 하나 둘 셋 (https://www.acmicpc.net/problem/25013) KOI 스타일로 구성된 4시간 셋입니다. 0:00 ~ 0:06 난이도 순이라는 걸 알고 있었기 때문에 1번부터 차례로 풀었습니다. 매우 쉬운 문제이므로 바로 AC를 받고 넘어갔습니다. 0:06 ~ 1:30 2번을 봤습니다. 문제를 잘못 이해해서 1시간 가까이 뇌절을 했고, 일단 나이브라도 ..

문제 셋: 2011 IOI day 2 실제 대회처럼 5시간 타이머를 해놓고 봤습니다. 0:00 ~ 0:24 일단 1번 문제부터 읽어봤습니다. 부모 정점을 고려해서 적당한 트리 dp를 돌리면 서브태스크 1을 맞출 수 있다는 강한 확신이 있었지만 구현과 디버깅을 빠르게 할 자신이 없어서 일단 보류했습니다. 서브태스크 1의 배점이 매우 높기 때문에 일반그래프를 트리로 줄이면 문제가 해결되지 않을까 하고 생각을 해봤지만 잘 되진 않았습니다. dp관점으로 생각해보면 답이 작은 정점부터 차례로 계산해나갈 수 있고, 이는 다익스트라와 동일한 발상입니다. 구현도 매우 간단하기 때문에 바로 코딩을 했고, 100점을 받았습니다. 다른 문제를 읽지 않고 한 문제의 100점 코드를 짠다는 것은 매우 위험한 전략이지만, 풀이가..

레드 후기를 올릴 때 IGM을 찍으려면 1년은 걸릴 줄 알았는데 생각보다 빨리 찍게 되었네요. 딱히 적을 말도 없고 아마 코포 레이팅 관련 글은 이게 마지막일 것 같으니 (누텔라를 찍으면 얘기가 달라지지만) 제가 코드포스 IGM을 찍을 때까지 어떻게 공부했는지 정리하려고 합니다. 1. Virtual Contest로 많은 대회를 풀어보기 코드포스 레이팅을 올리는 가장 효과적인 방법은 최대한 많은 코드포스 대회에 참가하는 것입니다. 코드포스에서 제공하는 기능인 virtual contest로 과거 대회를 풀어보면 실제 대회랑 유사한 환경에서 문제를 풀 수 있고, 코드포스에 자주 나오는 유형을 파악하거나 전략을 세우는데 매우 큰 도움이 됩니다. 저는 오렌지이던 시절에 Div.1 contest들을 virtual ..

대회장에선 섭태 1만 긁고 접근도 못했는데 백준에 올라왔길래 업솔빙을 했습니다. 서브태스크 2와 3의 풀이를 urd05님에게 듣고 100점 풀이를 찾았습니다. https://www.acmicpc.net/problem/23347 23347번: 수열 연산 모든 수가 $1$ 이상 $K$ 이하의 수로 구성된 수열이 있다. 이 수열에 다른 연속한 부분수열을 삽입하거나 삭제하는 연산을 원하는 만큼 할 수 있다. 단, 이 수열은 길이가 $M$ 이상이어야 하며, 수열 www.acmicpc.net 실제 대회에서의 서브태스크는 다음과 같습니다. 서브태스크 1: $2M \le K$ 서브태스크 2: $M, K, |C|, |D| \le 6$ 서브태스크 3: $M, K, |C|, |D| \le 10$ 서브태스크 4: $M, K,..