1-N 분배법칙 질문

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

1-N

작성

265

*, %는 연산자 우선순위가 같으니까

6:00 부근쯤 설명한 분배법칙을 적용하려면 해당 코드를 변경(주석처리 부분)해야 하는것 아닌가요?

typedef long long ll;

ll go(ll a, ll b, ll c)

{

    if (b == 1)

    {

        return a % c;

    }

    ll ret = go(a, b / 2, c);

    //ret = (ret * ret) % c;

    ret = ret % c * ret % c;

    if (b % 2)

    {

        ret = (ret * a) % c;

    }

    return ret;

}

c++코딩-테스트

답변 3

큰돌

지식공유자

답변주신 내용에 ret은 이미 %c가 된 상태로 나온다는게 이해가 가질 않습니다.

ll go(ll a, ll b){
    if(b == 1) return a % c;
    ll ret = go(a, b / 2);
    ret = (ret * ret) % c;

코드를 보시면 가장 마지막 기저사례에서 모듈러 연산을 한 ret이 나오게 됩니다.

마지막 부분만을 생각해볼까요?

그렇게 나온 ret이 다시 곱하면서 %c를 하게 되죠?

이 때는 (ret * ret) % c; 이렇게 해도 됩니다.

왜냐면 마지막에 나온 a%c가 ret으로 나오게 되는데 이는 모듈러 연산이 적용된 변수이기 때문입니다.

그리고 나서.. 누적으로 ~ 쌓여서 ret이 완성되는 것이죠.

예를 들어 11이 있는데 그걸 %10을 하게 되면 1이 되는데

1 * 1 을 해도 각각 다시 % 10을 안해도 되는 것이죠.

감사합니다.

인프런에서 *을 연속해서 쓰면 기울임 처리되어 곱하기를 x로 나타내겠습니다

답변주신 내용에 ret은 이미 %c가 된 상태로 나온다는게 이해가 가질 않습니다.

원래 개념 설명에서는

A^B % C 은

(A x A x A ... ) % C 인데

이렇게 하지 말고

(A%C x A%C x A%C x A%C ... ) 해서 A끼리 곱할때 발생할 수 있는 오버 플로우를 없애자는 개념이였습니다.

다시 코드로 돌아와서

ret = (ret * ret) % C 하게 되면

ret * ret이 먼저 계산되니까

결국 A%C * A%C가 아닌

(A * A) % C 으로 계산되어 분배법칙이 안쓰인 것이 아닌가요?

큰돌

지식공유자

안녕하세요 ㅎㅎ

    //ret = (ret * ret) % c;

    ret = ret % c * ret % c;

ret은 이미 %c 인 상태로 나오게 됩니다.

이 상태에서 ret 을 한번 더 곱하면 기존 ret보다 더 큰수가 되기 때문에 %c를 헤주어야 합니다.

만약 이렇게 하실거면.

    ret = ret % c * ret % c;

앞의 코드가 아니라 이렇게 해주셔야 합니다.

    ret = (ret % c * ret % c)% c;

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변

1-N 분배법칙 질문