이런 문제의 풀이 방법은??

  • leedohyun
    leedohyun

    문자열이 하나 주어지고요.
    Stack을 이용해서 또 다른 문자열로 변환을 시킵니다.
    이 때 결과 문자열로 바뀔 수 있는 Stack의 Operation 경우의 수를 구하는 문제입니다.
    문자열의 길이가 수 천개가 된다고 하면 어떻게 풀어야 할까요?
    전, Backtracking을 생각했는데요.
    그 보다 더 Smart한 방법이 있는지 궁금하네요.

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

    16년 전
11개의 댓글이 있습니다.
  • JongMan
    JongMan

    문제가 이해가 안가요~ ㅠㅜ 예제를 좀~


    16년 전 link
  • kcm1700
    kcm1700

    음.. 제가 이해한 문제가 맞다면,
    혹시 Catalan Number 말씀하시는건가요?


    16년 전 link
  • Kureyo
    Kureyo

    스택에서 pop할때마다 목표문자열과 똑같게 만드는 중인 문자열의 맨 뒤에 붙는건가요?
    저도 딱히 스마트한 방법이 떠오르지않는데요 ㅠㅠ 혹시 원문제가 있다면 볼수있을까요?


    16년 전 link
  • hyunhwan
    hyunhwan

    제 생각에는 입력되는 문자열이 주어지고, 이를 스택에 넣었을때 무조건 넣기만 하는게 아니라 도중에 pop도 가능하게 되어, pop된 결과를 가지고 최소 operation의 수를 구하는 문제 같다 라고 생각되는데... 아닐려나요 ㅠㅠ?
    자세한 문제의 description을 올려주시면 좋을꺼 같습니다~


    16년 전 link
  • Being
    Being

    어떤 문제일 지 느낌이 옵니다. 제 추측은:
    input string과 output string이 있고, input string에 적당한 조작을 가해서 output string을 만들어야 합니다.
    이 때 input string은 sequence of characters 로 이해하여, 이 글자들을 앞에서부터 적당히 스택에 push/pop 함으로써 어떤 string을 만들 수 있습니다.
    이 때 stack에 넣고 빼는 조작을 어떤 sequence (e.g. <+, +, -, +, -, ->)로 나타내었을 때, 가능한 모든 조작 sequence들 중에 output string을 만들 수 있는 것은 몇 개인가?
    인 것 같습니다.


    16년 전 link
  • leedohyun
    leedohyun

    Being님~ 100% 정답!!
    부연 설명을 드리면 APPLE -> PPLEA로 바꾼다면요
    I I O I O I O I O O <- 이렇게 나오겠죠. (I는 Push, O는 Pop)
    Input이 수천개의 문자로 이루어졌다고 가정할 때 해결 방법이 뭘까요?
    이 때 몇 개인지만 나타내는 것이 아니라 실제 Output String을 모두 출력한다고 가정합니다.


    16년 전 link
  • Being
    Being

    음......다 출력하신다구요? 위에서 kcm1700군이 말한대로 n개를 stack에 넣고 빼는 방법의 경우의 수는 catalan number C_n에 좌우됩니다. 주어진 스트링이 알파벳이라 가정하면 물론 알파벳이 26가지 밖에 없기 때문에 얼마 안 될 것 같지만, "abcdefg...xyz"의 문자열을 변경하는 방법만 하더라도 C_26인데, 대략 18367353072152 가지 쯤 되네요. -_-;;;


    16년 전 link
  • JongMan
    JongMan

    흠, 백트래킹은 절대 안 되겠네요. AAAAA....A => AAAAA....A (길이는 각각 1000) 이면, 백트래킹으론 죽었다 깨도 다 셀 수 없겠죠. -.-;;딱 DP 삘인데.. ^^;


    16년 전 link
  • helloneo
    helloneo

    이런 문제가 있네요.. -_-
    http://icpcres.ecs.baylor.edu/onlinejudge/external/7/732.html 


    16년 전 link
  • leedohyun
    leedohyun

    네~ 제가 풀고자하는 문제가 딱 저 문제였습니다ㅎㅎ
    사실 백트래킹으로 풀어보다가 실패했어요.
    경우의 수가 미친듯이 많은 걸 알긴했지만 DP로 어떻게 풀까 딱 떠오르지가 않아서요.

    종만님께서 DP로 풀어야 할 것 같다고 하셨는데요.
    어떻게 접근해야 할까요?
    (그리고 댓글을 보면서 생각해보니 카탈란 넘버 군요-.-;)


    16년 전 link
  • JongMan
    JongMan

    흠, 일단 카탈란 넘버니까 티피컬하게.. 
    original string 을 A, mapped string 을 B 로 둘 때 임의의 A 의 substring 에서 B 의 substring 으로 매핑하는 경우의 수를 구해서 O(n^4) 로 풀 수 있겠죠.
    C[i,j,k] = A[i..j] 를 B[k..k+(j-i+1)] 로 변환하는 방법의 수. 이 때, A[j] 가 B 의 어느 위치에 갈 것인가를 다 돌면서 각 경우의 수를 더해주면 됩니다. 따라서 O(n^4)
    이것보다 빠른 방법이 있다고 제 맘속의 목소리가 말하고 있는데 사실 잘 몰겠네요.. -.-;;


    16년 전 link

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