인프런 커뮤니티 질문&답변
작성한 질문수
재귀함수 질문있습니다.
작성
·
180
0
선생님께서 유튜브에 올리신거같은데 인프런에서는 어느강의 인지 몰라서 여기부분에다 올립니다.
https://www.youtube.com/watch?v=mzLx_NWpuSY
8분 42초에는 (a*a*a)%c하게 되면 a값이 2억일때 longlong에서도 범위가 넘어가서 (a%c*a%c*a%c)를 하셔야 된다고 했는데 9분9초에서 코드를 보니까 ret=(ret*ret)%c 가 적혀있는데요. (ret*ret)%c부분에서 (ret%c*ret%c)이렇게 해야 하는거 아닌가요?
그리고 10번줄에 if(2)도 true인데 if(1)홀수일떄만 작동된다고 하셨는데 짝수일떄도 작동되는거 아닌가요?
답변 1
0
안녕하세요 ekek님 ㅎㅎ
1 - N 곱셈문제입니다.
#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;
}이 코드를 말씀하시는거죠?
(ret*ret)%c부분에서 (ret%c*ret%c)
>> 이미 ret은 %c가 먹여져서 리턴을 하게 됩니다. 그렇기 때문에 (ret * ret) % c를 해도 됩니다.
그리고 10번줄에 if(2)도 true인데 if(1)홀수일떄만 작동된다고 하셨는데
>> if(2)는 true지만 지금 보시면 모듈러 연산으로 홀수인지를 가리고 있는데요. 만약 2 % 2를 하게 되면 0이 되서 false, 짝수일 때는 작동되지 않습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
안녀하세요 ek님 ㅎㅎ
자
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;
}여기서 go라는 함수의 ret을 보면 계속해서 %c를 해서 return되는 것을 볼 수 있죠?
go 내부의 ret 또한 go의 값을 가져오는 것인데
ll ret = go(a, b / 2);
go라는 함수를 보면 b == 1 일 때는
if(b == 1) return a % c;이렇게 %c
ret을 2번 곱할 때도
ret = (ret * ret) % c;%c
만약 b가 홀수 일 때 다시한번 곱하면서
if(b % 2)ret = (ret * a)% c;로 %c를 계속해서 나가는 것을 볼 수 있습니다.
이부분들에서 %c가 걸어지고 있습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
답변감사합니다.
1번 답변 중
>> 이미 ret은 %c가 먹여져서 리턴을 하게 됩니다. 그렇기 때문에 (ret * ret) % c를 해도 됩니다. 이렇게 답주셨는데요.
이미 ret은 %c가 먹여진다는게 아래코드에서 먹여진다는 건가요? 근데 먹여진다면 %c를 계산하는게 어디인가요?
ll ret = go(a, b / 2);