본문 바로가기

PS - 알고리즘

 (48)
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..
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$개일때의 답을 알고..
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
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..
1090 - 체커 step 1더보기모든 칸에 대해서 해당 칸에 체커가 1, 2, ..., $N$개가 있기 위한 최소 이동 횟수를 알면 문제는 쉽게 해결이 가능합니다. 여기서 모든 칸이 아니라 특정 칸으로 줄이려면 어떻게 해야 할까요?step 2더보기가로와 세로는 따로 계산할 수 있습니다.체커가 판에 놓여있다고 해봅시다. 빨간색이 체커입니다. 체커를 기준으로 가로, 세로 선을 그어주었습니다.만약 아래 그림에서 초록색 위치에 $N$개가 모일 때의 이동 횟수를 구했다고 합시다.그러면 여기서 초록색 점이 한칸 오른쪽으로 이동했다고 생각해 봅시다.만약 이동 횟수가 줄었다면 초록 점은 답이 될 수 없습니다.만약 이동 횟수가 늘었다면 초록 점이 왼쪽으로 갈 때는 이동 횟수가 줄어든다는 뜻입니다. 그렇다면 초록 점은 답이 될 수 없습니..
30294 - Flea 문제 번역더보기$N*M$크기의 격자 칸에 벼룩을 잡기 위한 트랩을 만들어 두었습니다. 이 트랩에는 약한 방향(상, 하, 좌, 우)이 있어 해당 방향으로 벼룩이 도망갈 수 있습니다. 벼룩의 최대 점프력은 $K$입니다. 벼룩이 $N*M$ 칸을 벗어나면 탈출했다고 표현합니다.벼룩이 여러 번 점프를 해서 탈출할 수 있는 칸의 개수를 모두 구하십시오.step 1더보기각 격자칸을 정점으로 생각합니다. 벼룩이 칸 $A$에서 칸$B$로 이동할 수 있다면 $B$에서 $A$로 가는 간선을 그려줍니다. 탈출할 수 있는 칸을 전부 구한 다음 그 위치에서 BFS를 돌리면 답을 구할 수 있습니다.step 2더보기각 칸마다 $K$개의 간선이 나올 수 있으므로 $N*M*K$의 시간이 필요합니다. 하지만 이러면 시간초과가 나옵니다.다..
14679 - 영우와 ‘갓4’ step 1더보기전투를 1000번만 치루면 모든 스탯이 몬스터보다 높고 공격도 먼저 합니다. 즉, 이 이후로는 항상 이긴다고 생각할 수 있습니다.step 2더보기현재 몬스터의 스탯을 알고 있을 때 다음 몬스터의 스탯은 $\log n$(https://codestudycafe.tistory.com/2)에 알 수 있습니다.step 3더보기몬스터는 50,000,000마리가 있고 모든 몬스터의 상태를 계산해 주긴 해야합니다. dp를 만들어서 해결할 수 있습니다. dp[i][j][k]: 현재 몬스터의 공격력이 i, 방어력이 j, 체력이 k일 때 다음 몬스터의 공격력, 방어력, 체력 이 dp를 만들면 시간을 줄일 수 있습니다.코드더보기#define _CRT_SECURE_NO_WARNINGS#include#includ..
11401 - 이항 계수 3 step 1더보기페르마 소정리에 의하면 $p$가 소수일 때 $a^{p-2} = a^{-1}$입니다. 즉, $x/y \pmod{p} = x*(y^{-1})\pmod{p} = x*(y^{p-2})\pmod{p}$ 입니다.step 2더보기${n \choose k} = \frac{n*(n-1)*...*(n-k+1)}{1*2*...*m}$ 입니다. 분모와 분자를 각각 계산한 다음 모듈러를 취해주면 됩니다.코드더보기#includelong long int pow(long long int x, long long int y) { if (y == 1) return x; if (y == 0) return 1; long long int p = pow(x, y / 2); if (y % 2 == 1) return p * p % ..
6612 - 개미의 이동 step 1더보기개미의 위치에만 집중을 해봅시다. 개미가 서로 통과한다고 가정할 때의 위치와 개미가 충돌할 때의 위치가 동일합니다. 즉, 어떤 개미인지는 모르지만 언제 어느 방향으로 개미가 떨어질지는 구할 수 있습니다.step 2더보기개미들의 순서에 집중해 봅시다. 왼쪽 개미부터 1, 2, ..., N으로 번호를 매겨봅시다. 개미끼리 서로 뛰어넘지 못하므로 제일 먼저 왼쪽으로 떨어지는 개미는 1번 개미, 다음으로 떨어지는 개미는 2번 개미,... 이런 식으로 떨어집니다. 오른쪽도 마찬가지로 제일 먼저 떨어지는 개미는 N번 개미, 다음은 N-1번 개미,... 이런 식입니다.언제 어느 방향으로 떨어지는지 알고 있으므로 그때 떨어지는 개미가 어떤 개미인지도 알 수 있습니다. 그럼 이게 모든 개미 변형 문제를 ..
11868 - 님 게임 2 step 1더보기우선 정답부터 이야기하고 가겠습니다. 나온 모든 수를 xor을 한 값이 0이면 후공 승, 아니면 선공 승입니다.놓여진 돌의 개수를 xor한 값을 그런디 넘버라고 하겠습니다. (원래 그런디 넘버의 정의는 많이 복잡하지만 이 문제에서의 그런디 넘버는 xor로 정해집니다.)만약 그런디 넘버가 0이 아니라면 이 값이 0이 되도록 돌을 가져갈 수 있습니다.만약 그런디 넘버가 0이라면 어떻게 돌을 가져가도 이 값은 0이 될 수 없습니다.step 2더보기다음 예시를 봅시다. 29 2 이 예시에서 그런디 넘버는 9 ^ 2 = 11입니다. 그리고 9개가 있는 돌더미에서 7개를 가져가면 그런디 넘버를 2 ^ 2 = 0으로 만들 수 있습니다.그런디 넘버$G$의 최상위 비트에 집중해 봅시다. 그럼 해당 비트를..

티스토리툴바