인프런 커뮤니티 질문&답변

안녕하세요, 노력왕님!

순열 알고리즘에 대해 직관적으로 와닿지 않아 고민이 있는 것 같은데요.

이에 대해, 제가 조합, 순열, DFS 등을 포함한 재귀함수를 어떻게 이해하고 공부했는지를 알려드리겠습니다.

[재귀함수의 구조에 대한 이해]

재귀함수는 기본적으로 함수이기 때문에 입력 변수(들)이 있으며, 재귀(자신을 재호출)이기 때문에 recursive case, 그리고 재귀(자신을 호출하는 과정)를 끝내야 하므로 base case 부분이 존재합니다.

따라서, 어떠한 로직을 재귀함수로 구현한다면 입력 변수(들), recursive case, base case 등을 고려하면 되는 것이죠.

그리고 입력 변수(들), recursive case, base case 등은 "함수의 의미를 어떻게 설정할 것인가"에 따라서 달라집니다.

[permutation 함수 파헤쳐보기]
예를 들어, permutation(level) 함수 에 대해 생각해 봅시다.

permutation(level) 함수는 어떤 의미를 가질까요? "전역변수 arr의 원소들에 대해 R개를 나열하는 순열을 전역변수 choose 배열을 통해 모두 살펴보는 함수" 라는 의미를 가집니다. 따라서, 이러한 의미에 맞게 입력 변수(level)에 대해 base case, recursive case를 작성해 봅시다.

(recursive case) 만약 level이 골라야 할 원소의 개수에 아직 못 미치면, choose[level]에 들어갈 원소를 넣습니다. (base case) 만약 level이 골라야 할 원소의 개수에 도달했다면, 현재 choose는 완성된 상태이므로 적절히 처리합니다.

더 자세히 설명하면, 골라야 할 원소의 개수가 R이라고 하면 choose[R-1]까지 원소를 채워야 완성이 된 것입니다. 따라서, (recursive case) level이 R-1보다 작으면(choose 배열이 완성된 상태가 아니면) recursive case를 통해서 원소를 넣고 다음 재귀함수(permutation(level + 1))로 넘겨주는 것이며, (base case) level이 R-1이면 choose[0]부터 choose[R-1]까지가 다 완성된 상태이므로, 해당 choose 배열(순열 중에서 1가지 경우에 해당)에 대해 처리를 하는 것이죠.

[정리]

정리하면, 재귀함수의 의미를 적절히 정의하고, 그 의미에 맞게끔 입력변수(들), recursive case, base case 부분을 정의하면 재귀함수를 작성하는 것과 이해하는 것 모두 쉬워질 것이라고 생각이 듭니다.

강의에서 재귀함수에 대해 설명할 때 해당 함수의 의미를 주석으로 적는 경우가 많이 있으니, 그 의미를 생각하며 재귀함수를 이해하면 더 잘 이해할 수 있을 거라는 생각이 드네요!

[수강생 분의 질문에 대한 답변]

재귀함수에 대해 제가 어떻게 생각하고 이용하는지 적으려다 보니 서두가 길어졌네요. ㅎㅎ

"실제로 문제를 풀 때 이렇게 하나하나 재귀깊이를 따라가면 시간이 많이 소요될 거 같은데 이러한 부분과 관련해서 팁이 있을까요?"

: 위에서 설명했듯이, 저는 재귀를 이해할 때 하나하나 해보면서 이해하는 것이 아닌 재귀함수의 의미를 통해 재귀를 도는 부분(recursive case)과 재귀가 끝나는 부분(base case) 딱 2가지 부분만 집중적으로 생각하여 구현합니다. 사실은, 재귀를 시작하는 부분 (즉, 재귀함수를 처음 호출하는 부분)도 생각해주시면 좋습니다. 예를 들어, permutation(level)같은 경우는 choose[level]을 완성하는 함수이므로, 처음에는 choose[0]부터 완성해야 하므로 permuation(0)을 호출해야 하는 거겠죠?

하지만, 처음에는 재귀함수에 대해 어색하여 위와 같이 간단하게 생각하면 해당 재귀함수가 이해가 되지 않을 수도 있는데요.(직관적으로 와닿지 않을 수 있는데요.) 그럴 때는 질문자분이 하신 것처럼 어떻게 돌아가는지 스택 프레임 등을 직접 그려보는 방식으로 먼저 이해하시고, 제가 한 것처럼 큰 틀에서도 이해하는 것이 좋을 것 같습니다.

"실제로 풀 때는 permutation(level + 1)을 재귀로 쓰면 대충 "[1, 2, 3], [1, 2, 4]... 순으로 나오겠지"와 같은 경험에 기반한 예측을 바탕으로 바로 사용하시는 건지 사고 과정이 궁금합니다."

: 경험에 기반하여 믿고 구현하는 것도 있으며, 정확하게는, 이전에 permutation(level) 함수에 대해 완벽히 이해했기 때문에 믿고 구현한다고 생각하시면 좋을 것 같습니다. 재귀함수에 대해 (제 기준) 간단하고 쉽게 이해하는 방법은 위에 설명해 놓았으니 참고하시면 좋을 것 같습니다! 참고로 permutation 함수를 시행하면 [1, 2, 3], [1, 2, 4] 순으로 나오는 것은 recursive case에서 인덱스가 작은 순으로 원소를 넣기 때문이라고 생각해 주시면 됩니다.

질문에 대해 만족스러운 답변이 되었기를 바랍니다!

추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

5점 수강평을 남겨주시면 향후 더 나은 강의를 만드는 데 큰 도움이 됩니다. 🌟