본문 바로가기

PS - 알고리즘64

4544 - 'Roid Rage 문제 번역더보기더보기$M$개의 다각형이 있습니다. 각 다각형끼리 교차하는지 아닌지 판단하세요. 두 개의 다각형이 내부 영역을 공유하거나(즉, 겹치는 경우) 경계점을 공유하는 경우(즉, 한 점이나 가장자리를 따라 닿는 경우)를 말합니다.step 1더보기더보기다각형의 수와 꼭짓점의 수가 적기 때문에 모든 경우를 보는 방법으로도 충분히 풀 수 있어 보입니다. 두 다각형이 있을 때, 어떤 변이 교차하면 반드시 겹친다고 할 수 있습니다. 이는 CCW를 이용해서 해결할 수 있습니다.두 직선 $\overline{XY}$랑 $\overline{ZW}$가 있다고 해봅시다. CCW($XYZ$) * CCW($XYW$)가 음수고 CCW($ZWX$) * CCW($ZWY$)가 음수면 이는 확실히 교차한다고 할 수 있습니다. 만약.. 2024. 8. 1.
27933 - 대회 이름 정하기 step 1더보기카드를 고를 수 있는 구간이 정해졌다고 해봅시다. 그럼 그 구간에는 K들과 Y들이 번갈아가며 있습니다. 각 선수들이 최선을 다해 플레이를 한다면 각 구간 안에서 가장 큰 값을 가져갈 것입니다. step 2더보기연속한 K와 Y를 K묶음, Y묶음으로 표현하겠습니다. 만약 카드를 고를 수 있는 구간 안에 묶음이 포함된다면 그 묶음 안의 최댓값만 알고 있으면 됩니다. 다른 카드는 절대 고르지 않을 것이니까요. 그럼 묶음의 일부만 포함된다면 어떻게 될까요? 우선 묶음의 가운데가 포함된다면 답은 YK 0입니다. 어차피 둘 다 아무것도 고르지 못합니다.그럼 오른쪽이나 왼쪽이 포함되는 경우를 생각해 봅시다. 그럼 포함되는 영역 중 최댓값을 뽑을 것입니다. 그럼 각 위치마다내 묶음의 왼쪽에 있는 값 중 .. 2024. 7. 25.
KMP 어떤 문자열(이하 text)에서 특정 문자열(이하 pattern)이 있는지 판단하는 문제가 있다 합시다(https://www.acmicpc.net/problem/1786). text의 길이를 $N$, pattern의 길이를 $M$이라 하면 단순 비교로 할 때 $O(NM)$의 시간이 걸립니다. 이를 $O(N+M)$으로 만들어 주는 것이 KMP(Knuth-Morris-Pratt Algorithm)입니다.방법단순 비교로 하면 $O(NM)$이 걸린다고 했었죠. KMP는 이 알고리즘에서 불필요한 과정을 제거했습니다. 위 과정을 보면 aaaaaa 부분은 더이상 안봐도 될 것 같은데 계속해서 검사해 주고 있습니다. 이 부분을 줄이기 위해서는 fail function에 대해 알아야 합니다.fail functionfai.. 2024. 7. 23.
6496 - Cyclic antimonotonic permutations 문제 번역더보기다음 조건을 만족하는 길이가 $N$이고 1에서 $N$까지로 이루어 진 순열을 만들어야 합니다. 반단조성 : 인접한 세 수를 보았을 때 가운데 수가 가장 크거나 가장 작아야 합니다.사이클 : $i$번째에 있는 수 $p_i$를 $i$에서 $p_i$로 가는 포인터로 생각합시다. 1에서부터 시작해서 포인터를 따라가면 모든 위치를 다 방문하고 다시 1로 돌아와야 합니다.step 1더보기홀수 번째에서 1부터 $\lceil n/2 \rceil$까지, 짝수 번째에는 나머지가 들어온다고 생각합니다(홀짝이 반대여도 됩니다). 그럼 첫 번째 조건은 알아서 만족합니다.step 2더보기$N$이 짝수인 경우 먼저 생각해 봅시다. $N$이 4인 경우는 손으로 만들 수 있습니다.(2 4 1 3)$N$개일때의 답을 알고.. 2024. 7. 18.
16570 - 앞뒤가 맞는 수열 step 1더보기수열을 한번 뒤집어 봅시다. 그럼 앞에 있는 수를 제거하는게 아니라 뒤에 있는 수를 제거하는 문제로 바뀝니다. 그럼 저희는 각 위치마다 앞뒤계수를 구해주면 됩니다.step 2더보기앞뒤 계수를 다른말로 하면 접두사와 접미사가 얼마나 일치하는지 입니다. 그리고 이건 KMP에서 실패 함수를 만들때 구합니다. 실패함수를 만들어 준 뒤 가장 큰 숫자가 뭔지, 몇개나 나오는지를 계산해 줍니다.코드더보기#includeint b[2000000],f[2000000];int main() { int i, n,p=0,max=0,maxi=0; scanf("%d", &n); for (i = n; i >= 1; i--) scanf("%d", &b[i]); f[1] = 0; for (i = 2; i 2024. 7. 11.
10523 - 직선 찾기 step 1더보기더보기이 문제의 $p$의 최솟값이 20입니다. 왜 굳이 20으로 했을까요?step 2더보기더보기답이 있다고 가정해 봅시다. 임의의 점 하나를 찍었을 때 해당 점이 선 위에 있을 확률은 $\frac{p}{100}$입니다. 그럼 서로 다른 두 점을 찍었을 때 두 점 다 선 위에 있을 확률은 $\frac{p*p}{100*100} \ge \frac{1}{25}$입니다. 그럼아무 두 점을 잡습니다.이 직선 위에 점이 $p\%$이상 있는지 확인합니다.엄청 반복합니다.한 스텝 확인하는데 $N$만큼의 시간이 걸립니다. 그럼 500번쯤 돌리면 $p$가 20일 때 1.3665e-9의 확률로 틀릴 수 있습니다. 이정도 돌렸는데 직선을 못 찾았다면 그건 원래 직선이 없었다 보는게 맞겠죠코드더보기더보기#defi.. 2024. 7. 11.

티스토리툴바