• 카테고리

    질문 & 답변

  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

1-N 질문 드립니다

24.03.16 15:35 작성 24.03.16 15:58 수정 조회수 67

0

안녕하세요 큰돌님 😀

1-N 백준 1629 문제에서 제공해주신 코드에

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
ll a, b, c;
ll go(ll a, ll b){
    if(b == 1) return a % c;
    ll ret = go(a, b / 2);
    ret = (ret * ret) % c;
    if(b % 2)ret = (ret * a)% c;
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> a >> b >> c;
    cout << go(a, b) << "\n";
    return 0;
}

여기에서

if(b % 2)ret = (ret * a)% c;

원래 공식에 대입하면 이 부분에 (ret * a % c) % c 가 들어오는 것이 맞지 않나요..? 어떻게 이렇게 되는지 궁금합니다 ㅜㅜ

go(2, 3) 이라고 할 때,

이렇게 되어서

if(b % 2)ret = (ret * a)% c;

이 아니라,

if(b % 2)ret = (ret * (a % c))% c;

가 된다고 생각했는데 설명해주시면 감사합니다..ㅜㅜ

 

다른 질문에 답변 달아주신 내용 확인해서 이해하였습니다~!!

course-thumbnail

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

답변 2

·

답변을 작성해보세요.

1

큰돌님의 프로필

큰돌

지식공유자

2024.03.18

아 ㅎㅎ 이해하셨군요 ㅎㅎ

감사합니다.

0

인프런 AI 인턴님의 프로필

인프런 AI 인턴

2024.03.16

안녕하세요, 인프런 AI 인턴입니다. Clain님의 질문은 모듈러 연산의 성질과 관련된 것으로 보입니다. 질문에 언급된 코드 조각은 분할 정복을 이용하여 거듭제곱을 빠르게 계산하는 알고리즘의 한 부분입니다. 예로 든 if(b % 2)ret = (ret * a) % c; 부분은 핵심이 되는 재귀 호출의 결과인 ret에 a를 곱하고 모듈러 연산을 실행하는 구간입니다.

Clain님은 재귀 함수의 결과에 다시 모듈러 연산을 적용해야 하는지에 대해 질문하셨고, 해당 부분을 다음과 같이 수정할 것을 제안하셨습니다.

if(b % 2)ret = (ret * a % c) % c;

제공된 링크 중에서 이와 관련된 설명을 해주는 답변을 찾았습니다. 아래 링크는 비슷한 질문에 대한 강사님의 해설을 포함하고 있는데, 여기에서 모듈러 연산의 성질을 이해하는 데 도움이 될 것입니다.

이전 답변에서의 핵심적인 부분은 ret이 이미 % c의 결과로 나왔기 때문에 다시 모듈러 연산을 할 필요가 없다는 설명입니다. 즉, (ret * ret) % c에서 이미 ret이 % c를 통해서 나온 값이기 때문에 이 값을 다시 ret % c로 하여 연산할 필요가 없고, 곱셈 연산 후의 결과에 모듈러 연산을 적용하면 된다고 설명하고 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다. 🙏

이 글과 비슷한 Q&A