본문 바로가기

전체 글

 (277)
[ICPC] 백준 14961 - Untangling Chain https://www.acmicpc.net/problem/14961 관찰 같은 방향으로 가는 경우가 없다. 무조건 회전한다. 어쩌면 이를 이용해서 무언가 할 수 있을지도 않을까? 예제 tc 2번을 그려보자. 이처럼 겹치는 부분이 한 번 발생한다. 이를 해결하려면 어떻게 해야 할까? 가장 명확한 방법은 위에서 2만큼 이동하는 부분을 4로 조정하면 된다. 이를 유심히 보자. 밑으로 내려가기 전엔 왼쪽 방향으로 이동을 했었다. 밑으로 내려갈 때 교차가 일어나지 않으려면 왼쪽으로 이동할 때 충분히 이동해야 한다. 얼마만큼? 방문했었던 좌표 중에 가장 작은 x 좌표보다 1 이상 더 이동해야 한다. 이를 일반화 해보자. 이번에 아래 방향으로 이동을 한 상태라면 다음 이동은 왼쪽 또는 오른쪽으로 할 수밖에 없다. 그..
세그먼트 트리로 직사각형 스위핑 feat. 3392 화성 지도 우리는 몇몇 문제를 통해 세그먼트 트리와 스위핑으로 직사각형의 면적 혹은 둘레를 구하는 방법을 알아볼 것이다. 대표적인 문제는 화성 지도가 되겠다. https://www.acmicpc.net/problem/3392 3392번: 화성 지도 첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30 www.acmicpc.net 스위핑 세그먼트 트리 소개 N개의 직사각형이 주어졌을 때 중복을 고려하여 총면적을 구하는 문제다. 바로 본론으로 들어가 우리는 두 개의 세그먼트 트리를 사용하겠다. 각 세그먼트 트리의 용..
백준 2016 국민대학교 교내 경시대회 풀이 https://www.acmicpc.net/category/detail/1541 2016 국민대학교 교내 경시대회 www.acmicpc.net 그렇다. 현재는 에디토리얼이 제공되고 있지 않으므로 후배로써 풀이를 복원하면 좋을 거 같아 글을 쓴다. PA 13410 거꾸로 구구단 시키는 대로 구구단을 수행하면서 뒤집은 수의 최댓값을 구하면 된다. CPP에서는 std::to_string으로 구구단 결과를 문자열로 바꾼 후 std::reverse로 뒤집고 다시 std::stoi로 전환하는 방법이 있다. 파이썬에서는 역시 str()로 문자열로 바꾼 후 슬라이싱 문법으로 뒤집은 다음 int()로 전환할 수 있다. std 함수의 경우 상수 시간이 크지만 문제에선 제한이 작으므로 문제없이 돌아간다. 전체 코드 - CP..
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..
백준 1498 - 주기문 https://www.acmicpc.net/problem/4354 사전 지식 이 문제를 KMP로 풀고 와야 한다. https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 풀이 문자열 제곱을 제대로 이해하고 왔다면 KMP 실패 함수에 다음 성질이 있음을 알 것이다. 길이 x의 문자열이 주기성을 만족하려면 n - x개의 접미사와 n - x개의 접두사가 같아야 한다. 또한 x|n을 만족해야 한다.(|은 정수론에서 배수관계..

티스토리툴바