[SWEA] 1217. [S/W 문제해결 기본] 4일차 - 거듭 제곱 (Java)

문제 링크 / level: D3

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14dUIaAAUCFAYD&categoryId=AV14dUIaAAUCFAYD&categoryType=CODE

 

 

내가 생각한 풀이

가장 쉽게 생각할 수 있는 방법 한 가지는 Math 클래스의 pow 메소드를 활용하는 것. (참고: java.lang)

※링크: https://docs.oracle.com/javase/8/docs/api/

JAVA API 문서에서 캡처해온 것인데 이 pow 메소드를 활용하면 아주 손쉽게 거듭 제곱한 결과를 얻을 수 있다.

 

그리고 또 하나의 쉬운 방법은 그냥 거듭 제곱 하려는 횟수만큼 for문을 돌리는 것이다.

이 또한 아주 쉽게 생각해낼 수 있는 방법이다.

 

하지만 이 문제에서 요구하는 것은 재귀를 이용해 풀어내라는 것이므로 어떻게 풀 것인지에 대한 고민을 잠시 해볼 필요가 있다. 좋게(?) 생각하면 이 문제를 통해서 Math 클래스에서 제공하는 pow 메소드를 내가 직접 만들어보는 것이라고도 할 수 있겠다.

 

재귀에서 가장 중요한 것은

1. 무엇을, 어떻게 반복할 것인가?

2. 그 반복은 언제 끝낼 것인가?

이 두 가지라고 할 수 있다.

고민해보자!

(1) 무엇을, 어떻게 반복할 것인가?

이 문제에서는 예를 들어 2 5 라는 입력이 주어졌을 때 2를 다섯번 곱해야 한다. (2 5 = 2 X 2 X 2 X 2 X 2 = 32와 같은 형태)

반복해야할 부분은 명확하다. 2라는 숫자를 반복해서 곱해주기만 하면 되는 것이다. 몇 번이나? 5라는 숫자 만큼이나.

 

(2) 그 반복은 언제 끝낼 것인가?

흔히 말하는 기저조건에 관한 것이다. 재귀에서 가장 중요한 부분이기도 하다. 이게 제대로 되지 않으면 무한루프에 빠지기 십상이다. 재귀가 반복되는 형태를 생각해서 기저조건을 설정해주어야 하는데... 여기가 가장 어려운 것 같다. 핵심부분이기 때문이겠지?🤔

 

예를 들어, pow(2, 5)라는 형태로 메소드를 호출했을 때 재귀가 어떻게 반복될까 생각해보는 것이 중요하겠다.

나는 일단 재귀를 반복할 때마다 횟수가 점점 차감되는 방식으로 코드를 작성하는 쪽으로 아이디어가 떠올랐다.

 

하지만 구체적으로는 생각이 나지 않아서 좀 더 디테일하게 상황을 가정해보았다.

만약에 pow(2, 1)같은 경우라면? 입력받은 2라는 숫자를 그대로 return해주면 끝이다. 여기서 기저조건 아이디어가 나왔다.

n = 2, m = 1이라고 했을 때 n을 그대로 리턴해주면 되는 것이니까 만약 m가 1일 경우에 재귀를 끝내주면 되지 않을까?

그리고 재귀함수는 횟수를 점점 차감하는 방식으로 해주면 되지 않을까?

 

// 핵심 코드
private static int pow(int n, int m) {
	// 기저조건
	if (m == 1) {
		return n;
	}
	return n * pow(n, m - 1);
}

 

그리고 성공!!🤗👩‍💻

스스로 재귀함수를 고민하고 실제로 구현해보는 것은 거의 처음이어서 넘나 뿌듯한 것❤️

 

 

▼아래 더보기를 누르면 코드 전체를 볼 수 있습니다.

[코드 보기]