inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

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

1 - N번 질문 있습니다.

195

고재찬

작성한 질문수 7

0

#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 _c = go(a, b/2);
_c = (_c * _c) % c;
if(b % 2) _c = (_c * a) % c;
return _c;
}
}
재귀 부분에서 _c의 값을 어떻게 결정하는건가요?? 
_c = (_c * _c) % c 이라면 값을 결정할 수 없는거 아닌가요ㅜㅠ
 

C++ 코테 준비 같이 해요!

답변 2

1

큰돌

안녕하세요. ㅎㅎ

예를 들어 go(2)라는 함수가 2를 반환하는 함수라고 해보죠. 

go(4)는 4를 반환하는 함수이구요. 

go(2) * go(2) = go(4) 라는 꼴이 됩니다. 

go(2) = 2이기 때문에

2 * 2 = go(4) 가 되죠? 

이처럼 _c는 go 함수에 인자를 2로 나눈 값을 기반으로 호출된 값이 들어가게 됩니다. 

_c와 b를 함수별로 출력해보면서

ex) cout << _c << '\n'  

디버깅을 해보시면서 보시면 충분히 이해가 가실겁니다.  

 

감사합니다.

0

큰돌

안녕하세요. ㅎㅎ

그니까  _c = (_c * _c) % c; 이게 작동을 안한다. 라는 말씀이신가요?

예를 들어

x = 2; 

x = x * x 

이게 작동을 안한다라는 건가요?

 

0

고재찬

안녕하세요!

이해가 안되는 부분이 

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

go 함수에 a, b가 들어가면 _c는 go(a, b/2)가 되잖아요

b가 짝수라면 다음 식은 _c = (_c * _c) % c 인데 _c에 어떤 값이 들어가는지 감이 안와서 질문 드렸습니다..@ 

 

1-E질문입니다!

0

533

2

3-L 틀린 부분 피드백 부탁드립니다.

0

836

2

1-A문제 순열재귀함수 질문입니다.

0

396

1

1-A 일곱난쟁이문제입니다

0

471

1

문제 풀 때 방향성에 대해

0

811

1

맥에서 vs code로 실행 관련 질문입니다

0

530

1

17071번 메모리 초과

0

390

1

1-C질문입니다!

0

428

2

2-B BFS 시간초과질문

0

638

2

1-O 13번 라인

0

447

1

6-J 놀이공원 문제 질문

0

390

1

구현관련 질문

0

492

1

강의 교안

0

322

1

실력을 더 올리고나서 강의를 보는 것이 맞을까요?

0

550

1

안녕하세요! 재귀함수에 관해서 질문드립니다

0

540

1

1-K

0

481

2

3-G번 질문있습니다.

1

481

3

3-C 실행 시간 질문드립니다.

0

504

1

4-A 문제 풀이 질문있습니다.

0

602

2

비트마스킹 연산자 "1의 보수" 영문 표기법

0

441

1

격자탐색 문제에서 BFS 시간복잡도 질문드립니다.

0

349

1

3-O go 함수 질문 드립니다.

1

453

2

4-A 출력 질문

0

308

1

1주차 1-O 질문드립니다

0

266

1