1. 완탐. O(n^2 * n!)에 했는데 monotonic 관찰하면 그냥 O(n*2^n)으로 될듯함.
2. 아래서부터 필요한 만큼 제거하고 남은거 받아오는거 반복하면 DFS 한 번으로 풀림.
3. dp하면서 매번 부분문자열인지 판단하려면 10초라도 터질거같에서 해싱으로 부분문자열인지 logn에 판단했음.
완탐도 통과할듯?
4. LCA + 트리에서의 부분합으로 o(N + Q)에 가능. 다음 문제 참조. https://www.acmicpc.net/problem/12746
플레2 실화냐 저거. 3번도 문자열 알고리즘 잘 모르면 재대로 건드리지도 못하겠던데... 플5 골드나 열심히 풀던 늅늅이는 1번풀고 맨탈 터져서 런함
근데 플레2는 에바인거같고 lca빠르게 구하기 플레 5에 트리에서 imos법 하는것도 안어려워서 플레4정도로 봄
3은 문자열 거의 안 쓰고 오히려 이거랑 비슷함
https://www.acmicpc.net/problem/2613
3번도 해싱할줄만 알면 그냥 n^2개 subarray의 해시값 전부 set에 넣어놓으면 되서 해싱만 알면 되고..
공통조상이나 아호코라식 세그맨트리 같은 플레에서 쓰이는 알고리즘들은 맛만보고 재대로 공부 안했단 말이야.. 내가 생각하는 코테랑 이 코드몬스터는 많이 다른거 같아... 진짜 ㄹㅇ ps혼모노들 뽑는 느낌이었음
아호코라식은 혼모노 맞는데 해싱은 너무 유용해서 알아야함 그리고 밑에 댓글 보니까 해싱도 필요 없더라
니 생각에 채감난이도 어떤거 같냐. 느낌상 카카오보다 어려운거 같음...
기업코테는 쳐본적이 없어서 모르겠네 앳코더 ABC에 D D E F 로 내면 딱 맞을듯
업솔빙 드가자
3번은 nm dp 하나로 가장 큰 부분문자열 찾아내고 n dp로 탐색해나가면 돌아가더라
가장 큰 공통 부분 문자열 ㅇㅇ
그 방법이 있었네
3은 완탐으로 풀었음... 검사한 문자열이 현재 경신된 answer보다 작을 때 백트래킹하면 백트래킹 더 추가안해도 풀려짐