[C++] 재귀 "우박수 길이(3n+1)"

#include <iostream>

using namespace std;

long long int memo[10000001] = { 0 };


long long int recur(long long int n) {
   if (n > 10000000) {//메모리보다 크면 배열사용안함.
      if (n % 2 == 0) return recur(n / 2) + 1;
      else return recur(n * 3 + 1) + 1;
   }
   
   //여기부터 시작.
   if (memo[n] != 0) return memo[n];//메모이제이션
   else {
      if (n == 1) {
         return 1;//실행된 횟수 반환.
      }
      else if (n % 2) {
         return memo[n] = recur(3 * n + 1) + 1;
      }
      else {
         return memo[n] = recur(n / 2) + 1;
      }
   }
}

int main() {
   int n = 0, m=0;
   
   int many=0, manyi=0;//우박수 많은 i와 최대우박수
   cin >> n >> m;
   
   for (int i = n; i <= m; i++) {
      long long int check = recur(i);

      if (check > many) { //recur(i) > recur(i-1) 비교
         manyi = i;
         many = check;
      }
   }
   cout << manyi << " " << many;
}

 

먼저 main문을 먼저 살펴보자.

 

변수

many : 최대 우박수(recur함수의 계산값)

manyi : 최대 우박수일때, 그때의 i값

 

long long int 값을 통해 recur함수의 반환값을 받는 방식이다.

 

if문은 구한 check값 중 최대값을 산출하기 위해 비교하는 조건문이다.

 

요약 :

1. 매번 반복문을 i값을 차례대로 계산해보면서 "최대우박수"를 리턴받는다.

2.그 우박수가 최대면 i값과 그 값을 저장한다

---

recur 함수를 살펴보자.

 

처음에 적혀있는 조건문은 해당 지문에서 10,000,000보다 큰 값을 받았을때 처리하는 부분이므로 무시해도 된다.

 

두번째 if((memo[n] != 0) 부분은 메모이제이션에 값이 들어있다면 그 값을 바로 리턴한다.

이 부분은 메모이제이션에 관한 부분이므로, 일단 이렇게 간단하게 설명하겠다.

상황의 예시를 하나 제시하겠다.

 

---

메모이제이션

상황 : recur(4)값을 구해야되는데 아래의 재귀에 따라서 recur(4)보다 작은 값들을 계속해서 호출해야한다.

 

이 상황에 미리 그에 대한 값을 recur(3) recur(2) recur(1) 등을 계산할때 배열memo에 저장해놓으면, 굳이 처음부터 계산할 필요가 없는 것이다.

 

즉, 수학적으로 실행속도 측면으로 바라보자면, 재귀는 똑같은 구문을 조건에 따라서 

n!의 시간복잡도를 n*(n-1)*(n-2)*(n-3) ... 이러던 시간복잡도에서,

예를들어 memo[1] memo[3]의 값이 저장되어있어서 바로 불러왔다면 n*(1)*(n-2)*(1)

이런식으로 한번에 값을 불러오기때문에 시간단축시켜주어서 코드의 효율성을 높여준다.

 

---

재귀 작동원리

자, 이제 메모이제이션에 대해서 설명을 마쳤으니, recur 재귀함수의 작동원리에 대해 알아보겠다.

리턴할때 +1씩 해주는 것은 각 시행에 따라서 실행된 횟수를 더해주는것이다.

 //여기부터 시작.
   if (memo[n] != 0) return memo[n];//메모이제이션
   else {
      if (n == 1) {
         return 1;//실행된 횟수 반환.
      }
      else if (n % 2) {
         return memo[n] = recur(3 * n + 1) + 1;
      }
      else {
         return memo[n] = recur(n / 2) + 1;
      }
   }

위 부분에서 if부분은 앞서 말한 메모이제이션으로 시간효율을 위해서 사용하는 부분이다.

 

else 부분부터 보면, 우리가 예를들어 recur(4)를 호출하게 된다면

 

#1

<recur(4)>

 

if(n은 1이아님)

else if(4%2 = 0 =false이므로 아님)

else return memo[4] = recur(4/2) +1 이므로 recur(2)를 호출을 먼저 하여 그 값에 1을 더해준다.

↓

<recur(2)>

if(n은 1이아님)

else if(2%2) = 0 = false이므로 아님)

else return memo[2] = recur(1) +1 이므로 recur(1)를 호출을 먼저 하여 그 값에 1을 더해준다.

↓

<recur(1)>

if(n=1) return 1;

↓

 

재귀의 과정

따라서 return memo[2] = 1 + 1 이고 그 값을 리턴한다.

return memo[4] = 2 + 1 이므로 return memo[4] =3을 한다.

 

메모이제이션에는 memo[2]=2  memo[4]=3 이 저장되었다.

 

 

 

다음은 i값이 5인 상황을 살펴보겠다

#2

<recur(5)>

else if(5%2 = 1 = true)

   return memo[5] = recur(16) + 1

↓

<recur(16)>

else

   return memo[16] = recur(8) + 1

↓

<recur(8)>

else

  return memo[8] = recur(4) +1

↓

이때 메모이제이션이 활용된다.

<recur(4)> -> <recur(2)> -> <recur(1)>의 과정을 거치지 않고,

바로 recur(4) = memo[4] = 3 을 가져온다.

 

 

재귀의 과정

return memo[8] = 3 +1 = 4

 

return memo[16] = 4 + 1 = 5

 

 

이렇게 메모이제이션에는

memo[2]=2

memo[4]=3

memo[8]=4

memo[16]=5

의 값이 저장되었다.

 

이와 같은 방식으로 작동한다.