1-A : 재귀함수로 푸는 방법

1-A : 재귀함수로 푸는 방법

우리가 앞서서 이 일곱난쟁이라는 문제를 순열로 풀었습니다.

바로 do-while(next_permutation) 이라는 함수로 구현했죠. 근데 제가 순열이라고 했을 때 do-while도 있지만, 그냥 우리가 직접 재귀함수를 만들어서 하는 것도 있다고 했죠.

오늘은 재귀함수를 직접 만들어서 구현하는 방법에 대해서 얘기를 해볼까 합니다.

'선생님 이거 그냥 do while로 계속 하면 되지 않나요?'

자 근데 여러분 문제를 봤을 때 다양한 방법으로 푸는 연습을 하는 것은 굉장히 중요합니다.

왜? 이렇게 하면은 사고가 유연해지니까요.

그러니까 여러분들이 코딩 테스트를 푼다라고 했을 때는 어떤 문제에 대해서 빠르게 하나의 최적의 방법을 찾아내서 그걸 기반으로 해야 되겠죠.

코딩테스트 때 갑자기 여러가지 방법을 떠올려가지고, 그 방법 하나하나 테스팅하는 것은 사실은 불가능합니다.

근데 만약에 여러분들이 코딩 테스트를 본다고 했을 때 한 번에 풀리지 않을 가능성이 굉장히 높아요. 그래서 '이게 안 될 때는 이거 되지 않을까?'라고 하면서 사고의 유연함을 갖추는 게 되게 중요한데, 그거를 연습하는 일환이 바로 어떤 문제를 보고 여러 가지 방법으로 푸는 거를 연습을 하시는 겁니다.

---

그래서 오늘은 재귀함수로 푸는 거에 대해서 얘기를 해보도록 할 텐데, 코드를 보면서 설명을 해보도록 할게요.

지금 보시면은 makePermutation이라는 재귀함수를 만들어 놓은 걸 볼 수가 있죠.

이 문제에서 n = 9, r = 7 입니다.

지금 여기서는 solve 라는 함수로 이렇게 이 문제를 풀이하는 것을 볼 수가 있지만,

solve 하기 전에 제대로 n, p, r이 지금 구현되어 있나 확인하기 위해서 print 라는 함수를 만들었어요.

그래서 이렇게 바꿔가지고 테스팅을 해봅니다.

여러분 이 makePermutation 함수는 외우고 있으셔야 돼요.

이제 순열을 만들었으니까 합계가 100인지 확인하는 solve 함수 부분을 봅시다.

이 함수에 대해서 살펴보도록 할 텐데요.

지금 우리가 필요한 7개랑 필요없는 2가지가 있는 거죠. 근데 우리는 이 부분만 sort를 하면 되는 거죠.

그래서 정확히는 index 6번째까지 sort를 한다는 의미입니다.

그리고 나서, 정렬을 한 다음에 exit(0)으로 종료시켜버립니다.

여기서 만약에 exit(0) 대신에 return을 하게 되면은 이 solve라는 함수만 종료가 돼요.

근데 exit(0)을 하게 되면 main 함수 자체가 종료가 되어버리게 돼서 그냥 출력만 하고 종료가 되어버립니다.

이 문제 같은 경우는 다양한 경우의 수가 나타날 수가 있고, 그 중에 하나만 출력하고 종료하면 된다라고 했죠. 이게 만약에 return 이라고 하면은 틀렸다고 뜰 겁니다. 왜? 이러한 경우의 수가 여러 번 나타날 수 있기 때문이죠.

 

오늘은 이렇게 해서 재귀함수로 푸는 방법까지 알아봤습니다.