USACO (7) 썸네일형 리스트형 KMP 알고리즘으로 부분 문자열 효과적으로 제거하기 이 포스트에서는 USACO 문제인 Censoring에서 문제 풀이를 통해 KMP와 동적 계획법으로 특정한 부분 문자열을 전체 시간 복잡도 $O(N + M)$로 처리하는 방법을 알아본다. https://www.acmicpc.net/problem/10747 10747번: Censoring Farmer John has purchased a subscription to Good Hooveskeeping magazine for his cows, so they have plenty of material to read while waiting around in the barn during milking sessions. Unfortunately, the latest issue contains a rather inap.. [USACO] 백준 6002 - Job Hunt https://www.acmicpc.net/problem/6002 힌트 더보기 어떤 도시를 도착하든 D원을 벌어야 나갈 수 있다. 시작 도시도 예외는 아니다. 풀이 더보기 도시를 잇는 도로와 비행기 노선이 제공될 때 어떻게 하면 큰돈을 벌 수 있을까? 비행기를 타는데 소비되는 비용을 음수 가중치라 생각하면 이 문제는 음수 가중치가 있는 그래프에서 최장 경로를 찾는 문제가 된다. C도 220 이하이므로 벨만포드 알고리즘의 사용을 적극 고려해볼 수 있다. 다만 돈을 버는 행위는 간선이 아닌 정점에서 일어난다는 것에 유의해야 한다. 문제의 상황을 벨만포드로 모델링하기 위해 기존 알고리즘의 구현에서 두 가지 조치를 행하면 된다. 1. 시작점의 초기값을 0이 아닌 D로 둔다. D만큼 벌어야 도시를 나갈 수 있기 .. [USACO] 백준 1774 - 우주신과의 교감 https://www.acmicpc.net/problem/1774 2021-08-17 기준 한글 번역의 질이 좋지 못하다는 코멘트가 있는 상황이다. 영어로 문제를 읽을 것을 추천한다. 이 문제는 2차원 평면에서 MST(Minimum Spanning Tree)를 완성해야 하는 문제이다. 각 정점이 서로 연결되었을 때의 간선들을 전부 생성해서 적절한 방법으로 MST를 구성하여 얻은 가중치의 합이 정답이 된다. 시간 복잡도는 간선을 생성하는 과정이 dominant factor이므로 $O(N^{2})$이다. 구현 다른 MST 문제와는 달리 2차원 평면이라 구현에 막연함이 있을 수 있다. 우리는 map을 이용하여 각 좌표의 index를 매기고 이 index를 기반으로 유니온 파인드를 만들면 간단하게 구현할 수 있.. [USACO] 백준 6156 - Cow Contest https://www.acmicpc.net/problem/6156 힌트 더보기 어떤 소의 순서를 정확히 알기 위해선 자기보다 낮은 스킬의 소와 높은 스킬의 소의 합이 n - 1마리가 되어야 한다. 각 소들의 sparse 한 스킬 관계를 그래프 형태로 정리하는 방법을 생각해본다. 풀이 더보기 소의 순서를 확정하기 위해선 자기보다 높은 스킬의 소가 몇 마리인지, 자기보다 낮은 스킬의 소가 몇 마리인지 알아야 한다. 하지만 입력은 서로 두 소의 상하 관계만이 주어졌을 뿐이다. 파편화된 관계를 가지고 전체 순위를 알 수 있는 방법이 있을까? 사실 순위가 몇위인지 아는 건 딱히 중요하지 않고 순위가 있다는 것을 알아내기만 하면 된다. 각 관계를 높은 스킬의 소가 낮은 스킬의 소로 향하는 단방향 간선을 가진 그래프.. [USACO] 백준 14165 - Team Building www.acmicpc.net/problem/14165 문제 소개 농부 존과 폴은 스테이트 페어에서 best in show라는 경쟁을 한다. 서로 가지고 있는 소들에게 점수를 부여하고 각 농부가 K마리의 소를 서로 점수가 높은 순으로 매칭하는데 한 진영의 소가 다른 진영의 소보다 모두 높은 점수로 매칭되면 이긴다. K가 주어지고 농부 존과 폴이 각각 N, M마리의 소를 가지고 있을 때 존이 이기는 경우의 수를 $10^9 + 9$로 나눈 모듈러를 출력해야 한다. 풀이 단순하게 존이 i번째 소, 폴이 j번째 소까지 각각 k마리를 뽑아서 존이 이기는 경우를 삼차원 동적계획법으로 풀 수 있다. (dp[i][j][k]) 다만 서로의 소를 매칭하는 경우를 일일이 탐색하면 시간복잡도는 $O(NM \times NMK)$.. 이전 1 2 다음
