kth990303의 코딩 블로그

학교 채점현황을 둘러보다가 발견한 문제. KOI(한국정보올림피아드) 2020 고등부 2차대회 문제이기도 하다. 문제는 아래와 같다. https://www.acmicpc.net/problem/20191 20191번: 줄임말 문자열 A가 문자열 B의 줄임말이라는 것은 B의 순서를 바꾸지 않고 0 또는 그 이상 개수의 문자를 지워 A를 만들 수 있다는 뜻이다. 정의에 의해서 B는 자기 자신의 줄임말임에 유의하라. 예를 들 www.acmicpc.net 요약하자면, 문자열 T를 몇 번 반복해야 문자열 S와 T의 LCS가 문자열 S일지를 파악하는 문제이다. 의식의 흐름 및 해설 처음에는 해결 방법이 떠오르지 않았다. 생각보다 어려운 문제가 아닐까? 싶어서 출처를 확인하고, 티어도 확인해보았다. 골드2 정도의 문제였..

이분매칭 (Bipartite Matching) Maximum Flow를 구하는 방법에는 Dinic Algorithm이 존재한다. 그런데, 모든 간선의 flow가 1이고, 이분 그래프 형태로만 존재한다면 bipartite Matching을 시도할 수 있다. (예를 들어 남녀가 미팅을 하며 각자가 원하는 짝을 1명씩 선택할 때, 최대 수로 성사시킬 수 있는 경우의 수는 이분 매칭으로 구할 수 있다.) 참고로 먼 옛적에는 Blossom Algorithm (1961)으로 최대 이분매칭 수를 O(EV^2)에 구했었다. 최악의 경우 O(V^4)까지 나올 수 있었던 셈. 원리가 궁금하다면 소멤 글을 참고해보자. https://www.secmem.org/blog/2020/04/18/Blossom/ 이분매칭의 시간복잡도..

알고리즘 중급 스터디에서 과제로 해결해야 했던 문제. 포인트를 놓쳐 생각보다 굉장히 많이 삽질했다. 문제는 아래와 같다. https://www.acmicpc.net/problem/24520 24520번: Meet In The Middle 첫 번째 줄에 마을의 수 $N$, 약속의 수 $K$가 주어진다. $(1 \le N, K \le 100\,000)$ 이어지는 줄부터 $N-1$개의 줄에 도로 정보를 나타내는 세 정수 $u$, $v$, $w$가 주어진다. $u$번 마을과 $v$번 마을 사이에 www.acmicpc.net 의식의 흐름 및 해설 N이 10만이기 때문에 DFS O(N)으로 모든 노드를 훑으면 시간초과이다. 따라서 특정 노드만 확인해주면 되는데, 정점들 사이의 거리는 LCA로 O(logn)에 구할 ..

추천받은 문제 중 하나. 입력 범위가 상당히 크기 때문에 꽤나 어려워 보이지만, 오히려 그러한 점이 힌트가 되는 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/15816 15816번: 퀘스트 중인 모험가 첫째 줄에 지금까지 달성한 퀘스트의 개수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄에 지금까지 달성한 퀘스트들의 번호 Q1 ... QN 까지의 N개의 수가 주어진다. (−1,000,000,000 ≤ Q[i] ≤ 1,000,000,000, Q www.acmicpc.net 의식의 흐름 및 해설 수의 범위가 굉장히 크기 때문에 O(N^2) 이상의 시간복잡도 풀이는 불가능하며, 입력받는 퀘스트 범위가 -10억 ~ 10억인 점, 요청으로 추가되는 퀘스트 개..

추천받은 문제 중 하나. 문제는 아래와 같다. https://www.acmicpc.net/problem/14863 14863번: 서울에서 경산까지 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 두 자연수 N과 K가 공백으로 분리되어 주어진다(3 ≤ N ≤ 100, 0 < K ≤ 100,000). 두 번째 줄에는 구간 1을 도보로 이동할 때 걸리는 시간(분), 이 www.acmicpc.net 의식의 흐름 및 해설 처음엔 평범한 knapsack인줄 알았는데, 생각해보니 자전거를 탈지, 도보로 갈지 선택을 해야되기 때문에 모든 경우를 선택하는 문제가 아니므로 knapsack dp가 아니었다. 따라서 top-down이든, bottom-up이든 시간복잡도 상 큰 차이가 없기 때문에 탑다운으로 풀었으며, N..

스터디그룹 채점현황 둘러보다가 발견한 문제. 결론부터 까고 말하자면, 이 문제는 BFS/DFS 뿐만 아니라 SCC로도 풀 수 있고, 만약 이게 정해라면 Platinum IV 티어 정도 받았을 것 같다. 문제 풀기 전에는 티어 열람 기능을 꺼놓기 때문에, 처음 봤을 땐 되게 쉬울줄 알았던 문제인데, 막상 풀 땐 그렇지 않았던 문제이다. 시간제한이 5초나 돼서 단순한 방법으로 풀리지만, 꽤 배울 점이 많은 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/1325 sync_with_stdio(0); cin>>n>>m; while(m--){ int a,b; cin>>a>>b; v[b].push_back(a); } int M=0; for(int j=1;j>a>>b; v[b]...

적당히 어려워보이면서 문제 이해가 쉬운 문제 찾다가 발견한 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/12969 12969번: ABC 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net N N >> K; memset(d, -1, sizeof(d)); if (!K) { for (int i = 0; i < N; i++) { cout

백준 잔디 채우려고 G4..G2 티어 중 랜덤하게 뽑아본 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/14452 14452번: Cow Dance Show After several months of rehearsal, the cows are just about ready to put on their annual dance performance; this year they are performing the famous bovine ballet "Cowpelia". The only aspect of the show that remains to be determined is the size of the stage www.acmicpc.net 여기서 제일 중요한 점! 소 ..

오랜만에 가벼운 문제로 백준 포스팅을 들고와보았다~! 문제는 아래와 같다. https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 괄호 관련 문제는 언제나 재밌다 재미는 개뿔...ㅠㅠ 의식의 흐름 및 해설 1. O(N^2) dp 괄호를 보면 보통 나는 stack을 떠올리는데, 이 문제는 경우의 수를 묻기 때문에 바로 dp를 떠올릴 수 있었다. 괄호 개수에 따라 충분히 메모이제이션이 가능하다는 사실은 한눈에 보이기 때문. 일단 N이 상당히 작은 데다가..

제목이 뭐 이리 길어 문제는 아래와 같다. https://www.acmicpc.net/problem/18251 18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) 욱제는 🎄포화이진트리🎄를 종이에 그렸다. 노드에 정수 가중치도 채워 넣었다. 욱제는 적당한 직사각형 영역을 잡아서, 영역 내에 있는 노드들의 가중치 합을 최대로 하고 싶다. 직사각형은 www.acmicpc.net 이걸 A번으로 생각하시다니... wookje님이 워낙 god이시긴 하지만 이럴 땐 진짜... 말잇못 나만 모르는 웰노운 소재가 있어서 기록해두는 문제. 의식의 흐름 및 해설 대체 직사각형을 어떻게 할 지 한참 고민했다. 일단 일렬로 나열된 트리노드들의 x값, y값을 어떻게 비교할지조..