인프런 커뮤니티 질문&답변
작성한 질문수
홀수인경우 처리방식에 궁금점이 있습니다
작성
·
127
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
해당 강의 홀수일때 처리하는 아래 코드에서
if (b % 2) ret = (ret * a) % c;
(ret * a) % c 가 아니라 (ret * a%c) % c가 맞다고 생각 하였습니다.
예를 들어서 2^5가 들어간다고 생각해보면 모듈러 계산 공식에 맞춰서
(2^5)%c = (2^4%c * 2%c)%c 로 계산이 되기때문에 (ret * a%c) % c 라고 생각하였는데, 혹시 이 부분에서 제가 개념을 잘못 파악하고있는건지 궁금합니다
답변 2
0
안녕하세요 수현님 ㅎㅎ
모듈러 연산의 특징은 앞의 그림과 같습니다.
(ret * a%c) % c
>> 이렇게 하셔도 되긴 합니다. 사실 수현님의 방법이 좀 더 안전한 방법입니다. a가 매우 큰 수일 때는 c로 먼저 모듈러 연산을 적용하는게 좋습니다.
하지만 이 문제에서 a는 int의 최대값이며 제곱했을 때 long long을 초과하지 않는 범위기 때문에 저 연산은 필요가 없으며(ret * a) % c 이렇게 해도 어차피 모듈러 공식에 의해 안에 다 모듈러가 적용이 되기 때문에 그렇게 안하셔도 됩니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다.
전수현님의 질문과 유사한 상황에 대한 설명을 제공하는 내용이 있어서 안내해드리겠습니다.
홀수일 때의 처리 방식, 특히 모듈러 연산에서 (ret * a) % c와 (ret * a%c) % c의 차이에 대해 궁금증을 가진 경우와 관련해, 큰돌 강사님께서 제공한 설명을 참조하실 수 있습니다.
- 질문: 홀수일 경우의 처리 방식에 대한 이해가 어려울 때, 특히
(ret * a) % c사용의 타당성에 대한 질문입니다.
해당 질문과 가장 잘 맞는 설명은 “선생님 홀수인 경우가 살짝 이해가 안됩니다.”에서 제공되었습니다. 이 답변에서 큰돌 강사님은 모듈러 연산에서의 처리 방식, 특히 if (b % 2) ret = (ret * a) % c; 부분의 사용 이유와 그 타당성을 설명하고 있습니다.
요약하자면, 강사님이 제시한 (ret * a) % c 계산 방식은 올바른 모듈러 연산 처리 방식입니다. (ret * a%c) % c로 계산하셔도 궁극적으로는 같은 결과가 나오지만, a%c를 하게 되면 불필요한 모듈러 연산이 추가되므로, 이미 ret % c가 적용되어 c보다 작은 상태라면 a에 대해서만 % c를 해도 충분히 올바른 결과를 보장합니다. 이는 효율적인 코드 작성을 위한 한 방법으로 볼 수 있습니다.
이에 대해 더 자세한 설명을 원하신다면, 위 링크를 참조해 주시면 좋을 것 같습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
감사합니다~!
강사님 덕분에 궁금하던 의문이 해결되었습니다.
앞으로도 완강까지 잘 달려보겠습니다!