6개의 댓글이 있습니다.

• 
  astein

  음... 이런거 써도 될지 모르겠는데. 일단 몇 가지 간단한 팁[?]을 써 보면요.
  1. 문자열 S1이 다른 문자열 S2를 완전히 포함하는 경우 S2는 string에서 삭제해도 무관.
  2. String이 100개이고 최대 200글자이기 때문에, table[i][j] = {Si 뒤에 Sj를 둔다고 할 때 겹치는 최대 글자 수} 라고 정의하면 100 * 100 * 200 번의 iteration으로 모두 계산할 수 있습니다. 즉, suffix tree를 구현할 이유는 없어집니다. :-)
  저도 이 문제 예전에 TSP로 바꿔서 풀어본 기억이 있구요 'ㅁ'.. TSP에서 좋은 해를 찾으려면 SA로 구현하는게 좋지 않을까 싶은...

  
  17년 전 link

• 
  일런데스

  크.. 저도 그래서 Suffix tree로의 구현은 포기했구요.. 그냥 naive하게 table[i][j]에 i와 j가 겹치는 글자수를 넣었어요ㅠ하지만 TSP가 막막하네요. 이젠 각 문자를 Vertex로 보고 지금 얻은 table배열을 direction edge로 보고 TSP로 구현하면 될 듯 한데.. 아무리 구글링해도.. branch&bound로 해야는데, 다이나믹방법이 대세이구..branch&bound에 대한 언급이 없어서.막막합니다; 제가 검색이 부족한걸까요ㅠ

  
  17년 전 link

• 
  Neon

  N = 100이면 이미 최적해를 구할 수 없을것 같으니 걍 그리디로 해도 그닥 욕먹지는 않을 정도의 답은 나올겁니다...
  임의의 노드 X에서 시작해서 table[X][i] 가 최대가 되는 아직 방문하지 않은 노드 i를 계속해서 방문해가는...

  
  17년 전 link

• 
  일런데스

  슬프게도 브랜치엔 바운드로 고집을 해서요ㅠㅠ 무조건 브랜치앤 바운드로 하라고 하기에.. 저도 무지막지하게 크길래
  그리디로 하는게 나을거 같긴하데ㅠㅠ
  그나저나 브랜치바운드에서 중간 결과는 어디에 저장이 될까요? ㄷㄷ

  
  17년 전 link

• 
  astein

  저장이 저절로 되는건 아니구요... 따로 저장을 해야합니다;;

  
  17년 전 link

• 
  zolac

  당연하면서도 어려운 말이네요... 저절로 되는건 없죠..^^

  
  17년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.