파라메트릭서치2 [문자열 문제] 가장 긴 '반복 부분 문자열' 길이 구하기 참고 문제 출처 www.acmicpc.net/problem/1605 1605번: 반복 부분문자열 알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분문자열을 '반복 부분문자열' www.acmicpc.net 문제 알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분 문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분 문자열을 '반복 부분 문자열'이라고 부르자. 문자열이 주어지면, 가장 긴 '반복 부분 문자열'의 길이를 구하는 프로그램을 작성하시오. 입력 (+테스트 케이스 추가, -문자열의 길이 제공X) 첫째 줄에 테스트 케이스의 수 .. 2020. 12. 17. [파라메트릭 서치] Parametric Search의 이해 및 구현 "파라메트릭 서치" 최적화 문제를 결정 문제로 바꾸어 푸는 것 이론 파라메트릭 서치 (Parametric search)는 이분 탐색(binary search)의 일종으로 선형 탐색에 비해 효율적인 시간 복잡도를 가집니다. 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정문제 로 바꾸어 푸는 것이라고도 할 수 있습니다. 어떤 명제 에 대해 True와 False의 경곗값 v0를 찾아야 할 경우 파라메트릭 서치를 이용하게 됩니다. 중간 위치는 (0+8)/2 =4 이므로, p(4)를 확인해보니 True -> 4는 v0의 후보군이 되고, 5~8은 탈락. 다음 중간 위치는 (0+3)/2 =1 이므로,p(1)을 확인해보니 False -> 0~1은 탈락. 다음 중간 위치는 (2+3.. 2020. 12. 16. 이전 1 다음
