본문 바로가기

전체 글

 (705)
kmp. [11585] [1. 문제 설명] https://www.acmicpc.net/problem/11585 [2. 풀이 접근] kmp search 원형에 대해서 문자열을 이어 붙이고, 이 문자열에서 다른 문자열을 찾는 전형적인 kmp 탐색 문제이다. 주의 할 점 주석에도 언급했지만, 이어붙인 문자열 X=2B 에 대해서 X[len(B)...] 에서 A 를 찾는 것은 의미가 없다. 기약 분수 분자와 분모의 최대공약수를 찾아야 한다. 유클리드 호제법을 이용하여 계산하도록 한다. 생각이 안나서 과거에 정리한 글을 참조 https://testkernelv2.tistory.com/107 [3. 코드]
kmp. [10266] [1. 문제 설명] https://www.acmicpc.net/problem/10266 [2. 풀이 접근] 최초에 생각해 본 방식 첫번째 시계의 배치를 1도 단위로 회전시켜서 이어 붙인다. 여기서, 두번째 시계의 배치를 찾는다. 그런데, 각도가 0 ~ 360,000 이므로, 1도 단위로 회전 시키면 메모리 및 시간 초과가 발생할 것이다. 현실적인 시간/공간 복잡도가 되도록 해야 한다. 올바른 풀이 역시 첫번째 시계의 배치를 확장한다. 그러나, [0, 360,000) 에 대해서 각도가 있으면 1, 없으면 0 으로 설정한다. 회전 한 경우는 [360,000, 720,000) 범위에 대해서 1 또는 0으로 설정하도록 한다. 이제 이 배치에서 두번째 시계의 배치를 찾는다. 즉, 첫번째 시계의 배치는 길이가 72..
kmp. [4354] [1. 문제 설명] https://www.acmicpc.net/problem/4354 [2. 풀이 접근] 시간 초과 풀이 게시판 참조한 풀이 기타 정해 풀이 [3. 코드] [4. 시간 초과 코드]

티스토리툴바