[프로그래머스] 소수 만들기 recursion, 재귀

https://school.programmers.co.kr/learn/courses/30/lessons/12977

프로그래머스

주어진 배열에서 숫자 3개를 골랐을 때 소수의 개수를 구하는 문제이다. for문을 3중으로 걸쳐서 만들 수도 있겠지만 재귀로 풀어보면 숫자가 3개가 아닐 때도 적용시킬 수 있을 것 같아서 재귀로 풀어보기로 했다.

 

아래는 전체 코드이다.

#include <vector>
#include <iostream>
using namespace std;

bool isPrime(int num) {
	for (int i=2; i*i <= num; i++)
	{
		if (num % i == 0)
			return false;
	}
	return true;
}

int Rprime(vector<int> nums, int pos, int cnt, int num) {
	int sum = 0;

	if (cnt == 3)
	{
		return isPrime(num) ? 1 : 0;
	}
	for (int i=pos; i < nums.size(); i++)
	{
		sum += Rprime(nums, i+1, cnt+1, num+nums[i]);
	}
	return sum;
}

int solution(vector<int> nums) {
    return Rprime(nums, 0, 0, 0);
}

 

소수 판별

먼저 isPrime을 살펴보자.

bool isPrime(int num) {
	for (int i=2; i*i <= num; i++)
	{
		if (num % i == 0)
			return false;
	}
	return true;
}

어떤 숫자 num에 대해 num의 제곱근(i*i = num 인 경우, i는 num의 제곱근, num은 i의 제곱)까지 값을 탐색했을 때

num을 나누는 값이 존재한다면 소수가 아닌 것(false)으로,

num을 나누는 값가 없다면 소수인 것으로 (true) 판별한다.

 

재귀

재귀함수인 Rprime을 살펴보자.

int Rprime(vector<int> nums, int pos, int cnt, int num) {
	int sum = 0;

	if (cnt == 3)
	{
		return isPrime(num) ? 1 : 0;
	}
	for (int i=pos; i < nums.size(); i++)
	{
		sum += Rprime(nums, i+1, cnt+1, num+nums[i]);
	}
	return sum;
}

매개변수

nums는 주어진 숫자 배열을 가지고 있는 벡터이다.

pos는 벡터에서 현재 탐색하고 있는 위치 값이다.

cnt는 현재 몇 개의 수를 조합했는지 세는 변수이다.

num은 조합한 수의 합계를 나타내는 수이다.

 

지역변수

sum은 소수의 개수를 반환하는 변수이다.

 

만약에 cnt(조합한 수의 개수)이 3개라면 3개의 수를 조합했으므로 조합한 수(num)가 소수인지 isPrime으로 판별한다.

소수라면 1을 아니라면 0을 반환해서 소수의 개수를 센다.

 

pos는 for문에서 탐색하는 범위를 제한하는 역할을 한다.

for문에서는 pos 이상의 값만 탐색할 수 있다.

만약 주어진 배열 nums가 [1,2,7,6,4]라면

i) 1번 재귀 함수,

i = 0이고, [1]을 num에 넣고 Rprime에 [1]이 합해진 채로 pos = 1 이 된다.  => Rprime([1,2,7,6,4], 1, 1, 1)

 

ii) 2번 재귀 함수,

i = 1이고, [2]을 num에 넣고 (num은 1+2가 된다) Rprime에 [1,2]가 들어간 채로 pos = 2가 된다.

=> Rprime([1,2,7,6,4], 2, 2, 3)

 

iii) 3번 재귀 함수,

i = 2이고, [7]을 num에 넣고 (num은 1+2+7이 된다) Rprime에 [1,2,7]이 들어간 채로 pos = 3이 된다.

=> Rprime([1,2,7,6,4], 3, 3, 10)

 

iii) 4번 재귀함수,

cnt가 3이라 현재 num=10 이 소수인지 판별한 값을 반환한다.

 

iv) 3번 재귀함수,

i = 3이고, [6]을 num에 넣고 (num은 1+2+6이 된다) Rprime에 [1,2,6]이 들어간 채로 pos = 4가 된다.

=> Rprime([1,2,7,6,4], 4, 3, 9)

.

.

.

총 5C3 = 10 개의 조합을 찾게 된다.

파란색만 소수인지 체크

위와 같이 현재 체크 중인 배열 위치를 확인할 수 있다.

 

재귀 깊이를 더 깊게

if (cnt == 3)에서 3을 다른 수로 바꾼다면 조합하는 수의 개수를 조절할 수 있다.

cnt == 4 라면 4개까지 조합할 수 있고, 0이라면 아무것도 조합하지 않는다.

코드 상으로는 재귀의 depth를 조절한다고 볼 수 있다.