| [ QuizWit ] in KIDS 글 쓴 이(By): ilusion (아지&환상) 날 짜 (Date): 1996년08월08일(목) 08시44분07초 KDT 제 목(Title): 스트링 문제 어제 rec.puzzle 뉴스그룹에서 본 기가막힌 문제입니다. 코넬대의 누가 낸문제인데 다음과 같습니다. n진법으로 구성된 숫자들의 집합을 L 이라고 합니다. (L을 n진법으로 구성된 모든 숫자들의 집합이라고는 하지않았습니다. ) 그럴경우 generate a string X s.t. every substring of X is contained in L . 두번째문제는 generate a string Y s.t. elements of L is substrings of Y. 이문제는 쉽습니다. 그런데 generate a string X of the minimal length. 가장 길이가 짧은 그러한 스트링 X를 만드는건 이거 N.P. 문제일까요 아닐까요. hint: 이문제를 grapth theory 문제로 동치화 시킬수있습니다. how ? consider each element in L is a path in a graph. each vertex has at most n edges ( n 진법에서 나왔습니다. ) now generate a minimal path that contained given pathes in L. iLUSiON 환상 직책: KIDS BBS counselor 상담소장 chung@math.toronto.edu http://www.undergrad.math.uwaterloo.ca/~ewpark 개인보드 csqueen.kaist.ac.kr/writers/iLUSiON |