알고리즘 문제 해결 전략 FANMEETING 솔루션 질문

  • yoon3784
    yoon3784
    int hugs(const string& members, const string& fans)
    {
        int N = members.size(), M = fans.size();
        vector<int> A(N), B(M);
        for (int i = 0; i < N; ++i) A[i] = (members[i] == 'M');
        for (int i = 0; i < M; ++i) B[M - i - 1] = (fans[i] == 'M');
        //karatsuba 알고리즘에서 자리 올림은 생략한다.
        vector<int> C = karatsuba(A, B);
        int allHugs = 0;
        for (int i = N - 1; i < M; ++i)
            if (C[i] == 0)
                ++allHugs;
        return allHugs;
    }
    

    위는 알고리즘 문제해결전략 교재 205p 코드 7.9 입니다. 여기서 궁금한점은 왜 members는 그대로 순서대로 A벡터에 저장하고 fans는 B벡터에 역순으로 저장하냐는 것입니다. 책에서 구현한 카라츠바 알고리즘 조건은 역순으로 저장하는 것이었는데 members를 역순으로 하지 않는 이유를 알고 싶습니다. A를 역순으로 바꿔서 실행시켜보니 이상한 결과가 나왔고 그 이유를 디버깅을 통해 알아보고자 했으나 과정이 복잡해 찾지못하고 질문드립니다.

    //karatsuba 알고리즘에서 자리 올림은 생략한다. 부분은 multiply 함수의 normalize 함수 호출부분을 삭제하면 되는 건가요?

    multiply 교재 코드 7.3

    vector<int > multiply(const vector<int>& a, const vector<int>& b)
    {
        vector<int> c(a.size() + b.size() + 1, 0);
        for (int i = 0; i < a.size(); ++i)
            for (int j = 0; j < b.size(); ++j)
                c[i + j] += a[i] * b[j];
        normalize(c)
        return c;
    }
    

    7년 전
1개의 댓글이 있습니다.
  • cosics
    cosics

    역순으로 저장하는 것은 팬들이 멤버들과 만날때 왼쪽으로 이동하기 때문아닐까요. 다시말해 팬들이 왼쪽으로 이동하면서 만난다 할 경우 곱셈으로 표현하려면 제일 높은 자릿 수 팬들이 제일 먼저 멤버와 만나려면 역순으로 팬들을 배치해야 하기 때문이죠.

    그리고 normalize는 올림 수를 포함하여 각 자릿수 로 만들기 때문에 벡터가 짧아집니다. 즉, 멤버와 팬을 곱한 값을 자리올림하지 않아야 하기 때문에 삭제 하셔야 합니다.


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