노력하는 공대생의 공부일지

최근에 KMP에 관해 이해도가 조금 올랐다.KMP나 아호코라식과 같은 문자열 매칭은 실패함수를 정의하고 dp같이 이해하면 조금 헷갈린다.DFA로 변환시켜서 경로 찾기로 문제를 환원하자. 실패함수를 정의하는게 헷갈릴 수 있는데, 아호코라식에서 결국 back edge는 suffix tree에서의 경로와 동일하다.따라서 일대다 문자열 매칭도 suffix tree로 가능구현 난이도는 둘이 비슷한거 같고 이해는 아호/kmp가 더 쉽긴 한 듯..?

핵심은 홀 -> 홀/짝 으로 나누어 진다는 점이다. 즉 모두 홀수인 상태로 상대에게 넘겨주게 되면, 상대는 임의의 개수의 홀수를 다시 홀/짝으로 분해해서 줄 텐데, 홀수의 개수 >= 짝수의 개수 이다. 따라서 다시 항상 홀수인 상태로 상대에게 넘겨줄 수 있다. 따라서 내 차례에서 모든 짝수를 없앨 수 있다면 승리한다. 이에 생각을 확장해보면모두 홀수인 게임판은 후공이 이긴다.홀수와 짝수가 동시에 존재하는 게임판은 선공이 이긴다.짝수만 존재하면서 짝수가 짝수개인 게임판은 선공이 이긴다.결국 짝수만 있는, 짝수가 홀수개인 게임판이 문제가 된다.그런데 2번 상태 때문에, 홀수를 하나라도 넘겨주면 진다...따라서 이제 상대 차례에 모든 수를 짝수로 넘겨줄 수 있어야만 내가 이긴다.이 문제는 어떻게 풀까? 전체를..

뇌풀이인 이유는 시험기간이라 구현을 할 시간이 없기 때문이다...까먹기전에 여기에 기록한다.  https://www.acmicpc.net/problem/32484학회에서 예선 대비 팀 연습했을 때 만났던 문제이다. 아호코라식을 몰라서 실제 연습때는 던졌는데 롸선배의 풀이 세션에서 깨달음을 좀 얻어서 작성.여기서 S=10^6,N=10^5정도로 본다. 우선.... 이 문제는 여러 문자열 매칭을 하는 부분을 빼고 풀어보자.연결되는 부분들에 대해 간선을 이어서 유니온 파인드를 한다고 생각하면 동치임을 쉽게 알 수 있다.즉 같은 유파의 문자열들은 같은 횟수만큼 나왔어야 한다. 따라서 각 유파에 대해서, 가장 등장횟수가 많은 값 x, 등장횟수가 최대인 문자열의 개수 y, 그 유파의 크기 z를 관리하면항상 x==y이..

https://dsstar.tistory.com/53여기 있는 셋입니다.감사합니다.  #11709 Toliets우선 정렬을 하기 이전에, 언제 불가능한 상태가 될까를 생각해본다..총 2N명이 있는데, N초 안에 완수하기 위해서는 한번도 놓치면 안된다는 뜻이다.즉 매초마다 2개의 화장실이 전부 채워져 있어야 한다. 그런데 M은 공용화장실만 사용 가능하므로, 아직 사용하지 않은 M의 개수만큼의 시간은 최소한으로 걸린다.따라서 현재 시간 + 남은 M의 개수 > N이 되버리면, 불가능하다. 문제 상황이 어떻게 흘러가는지를 생각해보자. 만약 특정 시점에 화장실이 전부 비어져 있고, M이 연속되게 나오는 경우를 보자..ex) MMM.....MF~그럼, M의 연속된 개수가 x라고 하면 x초 동안, 공용화장실에는 M이..

scpc는 2021년부터 출전했고, 2022,2023년도에 Final까지 올라갔었습니다. 2022년은 탈 실력이 아니었고, 2023년은 막차탈 실력은 됐었다고 생각하고, 실제로 탈 수 있었는데 놓쳐서 너무 아쉬웠습니다. scpc가 ps하는 잉여 인간들에게는 매우 중요한 대회입니다. 대기업인 삼성에서 매우 큰 혜택이 포함된 삼성SW멤버십에 가입시켜주기 때문입니다. 제 팀원이자 서강대 소멤 goat셨던 검굿님이 많이 알려주셨습니다... 이번 대회때 점수가 괜찮아 기대하고 있는 심정입니다. 제발 상 타게 해줘~~ 대회는 13시에 시작했습니다. [13:09] 1. 시간여행 AC 파이널 올 실력이라면 다 풀수 있는 문제입니다. 전 min세그를 박아서 풀었는데, 매우 빠르게 풀었다고 생각했는데 이미 10명 넘게 풀..

뇌풀이인 이유는 구현에 실패했기 때문이다.대략 140줄 정도 짜고 ide 껐다. 정해는 특수한 형태의 세그먼트 트리를 사용하면 풀 수 있다고 한다.문제를 분할정복으로 해결해보자. 각 분할하는 문제마다 결국 mid를 넘는 배열들에 대해서만 문제를 풀어주면 된다. 예제41 2 1 33 1 2 1로 문제를 설명해보면 이렇게 mid로 나눠버린다. 그러고 양쪽 방향으로 prefix max,min suffix max,min을 구한다. 그럼 문제는 이렇게 환원되는데 왼쪽 (Amax, Amin,Bmax,Bmin)원소와 오른쪽 (Amax,Amin,Bmax,Bmin)원소를 적절히 골라서 합쳤을 때,max=min이 되어야 한다. 물론 모든 쌍을 순회화면 O(n^2)이므로 빠르게 할 방법을 생각해봐야하는데,max의 suffi..

이 문제를 그래프로 해석해서 풀어보자. 각 학생은 다음 두 집합중에 하나에 속하게 된다. A = {우승가능성이 있는 학생} B = {어떻게 해도 항상 패배하는 학생} 우리의 목표는 A에 속한 학생들을 모두 구하는 것이 목적이다. 천적관계에 대해서 간선을 만든다고 생각해보자. 즉 x가 항상 y를 이긴다면 x->y인 모든 간선을 추가한다고 생각해보자. 첫번째 아이디어는 다음과 같다. A에 속해있는 임의의 정점을 a, B에 속해있는 임의의 정점을 b라고 해보자. 우선 연결그래프가 아닐 경우는 무조건 모든 정점이 되므로 넘어가자. (이건 쉬우니 생략하겠다...) 1. b에서 a로 가는 간선은 존재할 수 없다. 쉬운 증명: a는 이길 가능성이 있는데, a를 b가 이긴다는 것은 b도 이길 가능성이 있다는 뜻. 직관..

어제 있었던 라운드의 D번을 한번 풀어 보겠다. 어제는 셋이 매우 어려웠다. A,B,C,D모두 애드혹으로 발상이 힘들었다. 하지만 퀄리티 자체는 좋은듯... 어렵긴 해도... 풀이의 핵심은 절대 0이 될 수 없는 ai를 배제하자는 것에서 나온다. a,b,c 세 수가 있다고 하자. 그리고 gcd(a,b),gcd(a,c),gcd(b,c)를 알 때, 0이 될 수 없는 수를 어떻게 찾을까? 어떤 변수 x에 대해서 gcd(0,x)=x라는 사실을 이용하자. val[a]=gcd(a,b)+gcd(a,c) val[b]=gcd(b,a)+gcd(b,c) val[c]=gcd(c,a)+gcd(c,b) 라고 정의하자. 세 수 a,b,c중에 0이 존재한다면, val이 가장 큰 것이 0이된다. 그것도 strictly 하게 크다. 이..

더보기 이 문제는 3-coloring 문제와 연관시켜 푸는게 좋다. 즉 3-coloring보다 1-in-3 sat이 더 어렵다는 것을 보이면 (즉 1-in-3-sat을 풀 수 있다면 3-coloring 을 풀 수 있다는 것을 보이면 된다.) 3-coloring이 np complete임을 아므로, 자연스럽게 증명이 된다. 3-coloring문제를 다음과 같이 해석해보자. 각 정점 v에 대해서 v의 색깔 red,blue,green에 대한 세 변수 Rv,Bv,Gv를 만든다. 이 변수는 v가 red라면 Rv만 true이고, 나머지는 false이다. 모든 색에 대해 동일하게 적용된다. 그렇다면 (Rv or Bv or Gv)라는 clause를 각 v에 대해 만든다. 그 후 모든 edge (a,b)에 대해 다음과 같..

퀴즈가 2문제가 나왔는데 증명까지 써서 제출해야 하는데 문제당 4분을 줬다; 족보가 없으면 불가능하다고 개인적으로 생각 ㅜㅜ. 둘 다 못 풀었다. 1. 그래프가 주어졌을 때, k개 이하의 clique들로 그래프를 분할 할 수 있는지 판단하는 것은 np complete임을 증명하라. 더보기 complement graph를 생각한다. 즉 간선들의 연결관계를 뒤집는다. 그렇다면 originial graph에서의 clique는 complement graph에서 independent 하다. 즉 complement graph에서 k-coloring 문제와 정확히 동치임을 알 수 있다. k-coloring은 k>=3에서 np-complete임을 아므로 끝. 2번 문제는 3-sat 어쩌구 였는데... 기억이 안나서 모..