[editorial] 2007년 서울 온사이트 본선 B번 Editor

  • JongMan
    JongMan

    B - Editor

    B 는 이번 대회 문제들 중 A 와 함께 가장 많은 팀이 푼 문제로, 굉장히 다양한 종류의 해법이 있으며 이들 모두가 문제를 풀 수 있다는 점에서 매력적인 문제였습니다. 이들 방법들은 모두 시간 복잡도도 달랐는데, 대부분의 방법으로 큰 무리 없이 해결할 수 있었습니다.

    이 문제를 간략하게 바꾸면 다음과 같습니다.

    "소문자 알파벳 5,000개 이하로 구성된 문자열 S 가 주어질 때, S 의 부분 문자열은 S 의 연속된 일부를 잘라낸 것이다. 이 때 두 번 이상 등장하는 부분 문자열 중에서 가장 긴 것의 길이는?"

    앞으로 편의를 위해서 다음과 같은 표기를 사용하겠습니다.

    • S[i] = S 의 i번째 글자
    • S[i:] = S 의 i번째 글자에서부터 시작하는 S 의 suffix
    • S[i:j] = S 의 i번째 글자에서 시작하고 j번째 글자에서 끝나는 S 의 부분 문자열
    • prefix: S 의 앞을 0글자부터 n글자까지 잘라낸 것
    • suffix: S 의 뒤를 0글자부터 n글자까지 잘라낸 것

    1. 가장 직관적이지만 너무 느린 O(n^3lgn)

    가장 직관적인 방법은 S의 모든 부분 문자열을 생성해서 이들을 정렬하고, 중복이 있는지를 확인하는 것입니다. 아니면, map 와 같은 연관 컨테이너를 써서 각 부분 문자열의 개수를 셀 수 있겠지요. 이렇게요:

    void solve1(const string& S)
    {
          map<string,int> freq;
          for(size_t begin = 0; begin < S.size(); ++begin)
                  for(size_t end = begin+1; end <= S.size(); ++end)
                          freq[S.substr(begin, end-begin)]++;
          int res = 0;
          for(map<string,int>::iterator it = freq.begin(); it != freq.end(); ++it)
                  if(it->second > 1)
                          res = max<int>(res, it->first.size());
          cout << res << endl;
    }
    

    간단하죠? 하지만 이 방법은 O(n^2) 개의 부분 문자열을 모두 생성합니다. map 에 삽입하는 데 O(lg n) 번의 비교만 해도 된다고 하더라도, 각 문자열의 비교가 최대 O(n) 이기 때문에 전체의 시간 복잡도는 O(n^3lgn) 이 될 수밖에 없습니다. n = 5000 일때 n^3lgn = 1,535,964,047,443 정도 되는데.. 이래서야 시간 복잡도 안에 안 들어가겠지요.

    2. 조금 더 나은 O(n^3)

    모든 부분문자열을 생성하지 않으면 그보다 조금 나은 방법을 만들 수 있습니다. 이 아이디어는 모든 a, b 위치에 대해 S[a:] 과 S[b:] 의 가장 긴 prefix 의 길이를 매번 구하는 것입니다.
    다음과 같은 함수로 이런 일을 할 수 있습니다.

    // S[a:] 와 S[b:] 의 최대 공통 prefix 의 길이를 구한다
    // 예: S[a:] = "abcdef" S[b:] = "abcefg" 라면 답은 3
    int getPrefixLength(const string& s, int a, int b)
    {
      int len = 0;
      while(a+len < s.size() && b+len < s.size() && s[a+len] == s[b+len]) ++len;
      return len;
    }
    

    getPrefixLength 를 모든 a 와 b 에 대해 호출하면 이 중 최대값이 답이 된다는 것은 비교적 자명합니다. 그런데 각 getPrefixLength() 함수 호출은 최대 O(n) 의 시간이 들고, 모든 a 와 b 의 조합은 O(n^2) 개가 있기 때문에 이 알고리즘은 O(n^3) 이 됩니다. 여전히 희망이 없어 보입니다. 그러나, 만약에 S[1] 이 "abcd.." 로 시작하고, S[372] 에서 시작하는 부분문자열이 "efgce.." 라고 하면, getPrefixLength() 는 한 번 조건문 판단하고 종료해 버리기 때문에 실제 실행에 드는 시간은 훨씬 적습니다.

    5천개의 같은 문자가 들어올 경우 이 프로그램은 시간 안에 동작할 가능성이 별로 없습니다만, 실제 대회에서는 이 알고리즘으로 Yes 를 받은 팀이 있다고 합니다. (아주대학교 the pulza 팀)

    3. 동적 계획법을 사용해서 O(n^2)

    getPrefixLength() 함수는 a 와 b 가 정해져 있으면 언제나 같은 값을 반환합니다. 따라서, 이를 재귀함수로 다음과 같이 구현할 수 있습니다.

    int getPrefixLength(const string& s, int a, int b)
    {
      if(a == s.size() || b == s.size() || s[a] != s[b]) return 0;
      return getPrefixLength(s, a+1, b+1) + 1;
    }
    

    이 함수는 여전히 S[a:] 와 S[b:] 의 최대 공통 prefix 길이를 반환합니다. 다른 점은 재귀적으로 구현되어 있다는 것인데요.

    • S[a:] 나 S[b:] 가 텅 빈 문자열이거나 (a == S.size() or b == S.size()), S[a] != S[b] 면 답은 0 입니다.
    • 아니라면, S[a+1:] 과 S[b+1:] 의 최대 공통 prefix 앞에 S[a] 를 붙여서 최대 공통 prefix 를 만들 수 있습니다. 이렇게 문제를 재귀적으로 표 현하는 것은 동적 계획법(Dynamic Programming) 알고리즘의 기반이 됩니다. 동적 계획법 알고리즘은 이렇게 재귀적으로 표현된 문제의 부분해를 각각 저장해 속도를 올리는 알고리즘 설계 방법으로, 대표적으로 memoization 이라고 부르는 테크닉을 사용할 수 있죠. memoization 은 재귀호출의 각 parameter 에 대해 한번 계산 후에는 결과를 저장해 두고, 그 후부터 호출되었을 때는 저장되었던 값을 그냥 리턴하는 방식으로 구현됩니다. 자세한 것은 다음 기회에.. ^^; 위 코드를 memoization 을 사용하도록 바꾸면 다음과 같이 됩니다.
    int cache[5000][5000];
    int getPrefixLength(const string& s, int a, int b)
    {
      if(a == s.size() || b == s.size() || s[a] != s[b]) return 0;
      if(cache[a][b] != -1) return cache[a][b]; // -1 이 아니라면 이미 한 번 계산한 값이라고 봄
      return cache[a][b] = getPrefixLength(s, a+1, b+1) + 1;
    }
    int main()
    {
      ...
      memset(cache, -1, sizeof(cache)); // cache 배열을 -1 로 초기화
      ...
    }
    

    이 방법을 이용하면 getPrefixLength() 함수가 모든 a, b 에 대해서 O(1) 의 시간에 동작하기 때문에 O(n^2) 의 시간이 걸립니다. 자세한 시간 복잡도 분석은 약간 복잡하니까 여기서는 생략하고, 다음에 동적 계획법 튜토리얼에서 설명해 보도록 하겠습니다.

    (이 방법은 WE ARE BUT MEN, ROCK! 팀에서 사용했다고 하는군요~)

    4. Suffix Array 를 이용한 O(n^2lgn) 해법

    문 자열 문제를 해결하는데 익숙한 사람들은 자동적으로 이 해법을 떠올렸을 법 한데요, Suffix Array 를 이용한 것입니다. Suffix Array 는, S 의 모든 suffix 를 정렬해서 담고 있는 배열입니다. 예를 들어, "abracadabra" 의 Suffix Array 는

    suffixArray[0] = a
    suffixArray[1] = abra
    suffixArray[2] = abracadabra
    suffixArray[3] = acadabra
    suffixArray[4] = adabra
    suffixArray[5] = bra
    suffixArray[6] = bracadabra
    suffixArray[7] = cadabra
    suffixArray[8] = dabra
    suffixArray[9] = ra
    suffixArray[10] = racadabra

    가 됩니다. 이와 같은 자료 구조는 생물정보학(Bioinformatics) 나 정보검색(Information Retrieval) 같은 분야에서 활발히 연구되고 쓰이고 있죠. 이를 만들기 위한 가장 간단하고 시간이 오래 걸리는 방법은, S 의 각 위치를 가리키는 char* 를 정렬하는 것입니다. 다음과 같이요:

    bool cmpChar(const char* a, const char* b) { return strcmp(a, b) < 0; }
    void solve2(const string& s)
    {
          vector<const char*> suffix;
          for(size_t i = 0; i < s.size(); ++i) suffix.push_back(s.c_str() + i);
          sort(suffix.begin(), suffix.end(), cmpChar);
          // 여기서부터는 생략
    }
    

    이렇게 하면, 두번 등장하는 부분 문자열은 반드시 인접해 있기 때문에 p 의 인접한 요소들만을 O(n) 걸려서 비교하면 됩니다. 여기에 O(n^2) 의 시간이 들고 소트에 드는 시간이 O(n^2lgn) 이기 때문에, 전체 시간 복잡도는 O(n^2lgn) 이 되죠.

    5. Suffix Tree 를 이용한 O(n^2) 해법

    Suffix Tree 는 Suffix Array 처럼 문자열을 다루는 문제에 자주 사용될 수 있는 자료 구조입니다. Suffix Tree 는 S 의 suffix 를 모두 담고 있는 일종의 트라이(trie) 입니다. Trie 는 각 노드가 알파벳의 개수만큼의 자손을 가질 수 있는 트리로, 다음과 같이 생겼습니다. http://en.wikipedia.org/wiki/Image:Trie_example.svg

    자세한 것은 따로 공부해 보시고.. ^^;; Trie 를 만들고 거기에 S의 모든 suffix 를 집어넣으면 O(n^2) 의 시간이 걸립니다. 여기서 모든 노드를 순회하면서 2번 이상 나타난 노드들 중 루트에서 가장 먼 것까지의 거리를 기록하면 되겠지요.

    6. 궁극의 O(n) 해법

    놀랍게도, Suffix Tree 는 n 에 대한 선형시간에 생성할 수 있습니다. 이렇게 하면 Suffix Tree 생성만으로 간단히 O(n) 시간에 이 문제를 풀 수 있게 되죠. 이 알고리즘은 꽤 어렵고 복잡하기 때문에 아마 문제를 출제할 때 이 해법을 요구하지는 않았을 거라고 생각되구요. 자세한 것을 원하시는 분은 열심히 구글링해 보세요~ :D

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    16년 전
14개의 댓글이 있습니다.
  • 최치선
    최치선

    오오 1등이군


    16년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    저희 팀은 4번으로 풀었습니다. ^^


    16년 전 link
  • 진영
    진영

    S[a:a+(k-1)]와 S[b:b+(k-1)]가 같다면 (a<b) 스트링 S를 b-a만큼 오른쪽으로 shift한 스트링 S'를 만들어서
    S와 S'을 비교했을 때, 서로 같은 부분이 길이 k만큼 연속으로 존재해야 한다는 점을 이용해서 풀었어요-
    k를 1, 2, 3, ... 순서로 돌리는데, S[i]와 S[i+k]를 비교한 뒤 연속으로 같은 가장 긴 부분을 구하는 과정을 반복합니다.
    커팅이 많이 들어갈 수 있지만 기본적으로 시간복잡도는 O(n^2)이 되네요.ㅎ
    소스도 짧고 간결해요~


    16년 전 link
  • Megalusion
    Megalusion

    저는 KMP를 이용해서 풀었는데, 정말 많은 해법이 있네요 ㅋㅋㅋ


    16년 전 link
  • nocut98
    nocut98
    1. Suffix Tree 를 이용한 O(n^2) 해법, 문제 5번의 해법에서 만약에 문자열이 "ssssss"라면, 답은 "sss"이 되지 않나요? 1줄짜리 suffix tree를 만들고, 해당 트리에 차례로 넣어버리면, 2번 겹치게 되는 건 ... sssss 가 되버리지 않나요? 제가 문제를 잘못이해하거나 설명을 잘 못 이해한 거 같은데, 알려주시면 감사하겠습니다(굽신굽신)

    16년 전 link
  • JongMan
    JongMan

    count// 두 스트링은 겹쳐도 됩니다. ^^ 문제 설명 마지막 부분에 The two occurrences are allowed to overlap. 이란 구절이 있지요. _


    16년 전 link
  • nocut98
    nocut98

    오- 그랬군요. 저는 그러면 안되는 줄 알고 아- 문제 종니 어렵네- 라고 생각했었는데 ㅎㅎㅎ 희망이 보이는 군요 +_+


    16년 전 link
  • JongMan
    JongMan

    겹치면 안된다면 3번 해법이 젤 쉽겠네요. ㅎㅎ


    16년 전 link
  • astein
    astein

    http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix/ Suffix Tree 관련된 사이트로는, 이 링크도 꽤 괜찮아요.


    16년 전 link
  • 김우현
    김우현
    1. 궁극의 O(n) 해법 Linear Time Algorithm for the Longest Common Repeat Problem 이 내용인 것 같아요~. 관심있는 분들 참고하세요.

    http://www.dcs.kcl.ac.uk/staff/csi/publications/LIP05LongestCommonRepeat.pdf


    16년 전 link
  • soyoja
    soyoja

    UVa Live 에 2007 년도 서울대회 셋이 올라와 있어서 풀어보는 중인데..
    이 문제는 O(N^3) 로 풀면 TLE, O(N^2) 의 DP 로 풀려고 하니 Memory Limit Exceed 나네요 ㅋ
    결국 Suffix Array 로 풀었다는.. -0-


    15년 전 link
  • JongMan
    JongMan

    이 문제에 있는 O(N^2) DP 는 메모리 O(N) 만 사용하도록 바꿀 수도 있습니다. 한번 해 보세요! :D


    15년 전 link
  • JongMan
    JongMan

    그나저나 UVa Live 에 이 문제가 올라와 있다고요? 흠.. 그러면 서울 대회 측에서 데이터를 제공한건지, 임의로 만들어 실은건지가 궁금하네요. 실은 알고스팟 저지에도 과거 기출 문제들을 올리고 싶은데, 과거 문제들을 올리기에는 저작권 문제도 있는 것 같고, 해서 어떻게 해야 할까 고민 중이거든요. (저지부터 만들고 이런 말을 해야 하는데 ㅋㅋ)


    15년 전 link
  • nocut98
    nocut98

    제대로 푼 건지 테스트 삼아서 O(n^3) 으로 풀어서 넣어봤는데, Accept 뜨더군요
    단, 제출한 사람 중에서 제일 느린속도 더군요 -.-;;;


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