a^x을 계산하는 다음 알고리즘의 빈칸 ㉠～㉢에 해당하는 코드로 옳게 … | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지

1[7급 국가직 알고리즘] 23년 1회차

 $a^x$ 을 계산하는 다음 알고리즘의 빈칸 ㉠～㉢에 해당하는 코드로 옳게 짝지어진 것은? (단,  $a$ 와  $x$ 는 정수,  $x \ge 0$ , mod는 나머지 연산이다)int power(a, x) {
  if (x == 1)
    return ( ㉠ );
  else if (x == 0)
    return 1;
  if (x mod 2 == 0) {
    temp ← power(a, x / 2);
    return ( ㉡ );
  } else {
    temp ← power(a, (x – 1) / 2);
    return ( ㉢ );
  }
}
㉠ ㉡ ㉢

a * a / temp * a / temp * temp * a

a * a / temp * temp / a * a * temp

a / temp * a / a * a * temp

a / temp * temp / temp * temp * a

해설

㉠은 a, ㉡은 temp * temp, ㉢은 temp * temp * a이다.
x가 1이면  $a^1=a$ 를 반환한다. x가 짝수면  $a^x=(a^{x/2})^2$ 이므로 temp를 제곱하고, 홀수면  $a^x=(a^{(x-1)/2})^2\cdot a$ 이므로 제곱에 a를 한 번 더 곱한다.
예: power(2, 5)는 temp = power(2, 2) = 4이고, 4 * 4 * 2 = 32이다.
㉠을 a * a, ㉡을 temp * a로 둔 조합은 x가 1일 때  $a^2$ 를 반환하고 짝수 지수에서도 temp를 제곱하지 않아 틀린다.
㉠을 a * a, ㉢을 a * a * temp로 둔 조합은 x가 1일 때  $a^2$ 를 반환하고 홀수 지수에서 temp를 제곱하지 않아 틀린다.
㉡을 temp * a, ㉢을 a * a * temp로 둔 조합은 ㉠은 맞지만 짝수·홀수 경우 모두 temp를 제곱하지 않아 거듭제곱 값이 맞지 않는다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 알고리즘] 23년 1회차 25문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요

비슷한 기출

7급 국가직 알고리즘 기출문제 암기장 전체 보기

💬 자격증 스터디 커뮤니티헷갈리는 문제, 같이 준비하는 사람들에게 물어보세요

→