6장: 무식하게 풀기 - 1 (145p ~ 162p)

<재귀 호출과 완전 탐색>

1. 재귀 호출(recursion)

• 재귀 합수(recursive function)은 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수이다.
• ex) 1부터 n까지의 합 = n + 1부터 n-1까지의 합으로 나타낼 수 있고 1부터 n까지의 합을 구하는 함수만 완성하면 이를 구할 수 있다.
• 모든 재귀 함수는 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 하며 이를 재귀 호출의 기저사례(base case)라고 한다.
• 기저 사례는 존재하는 모든 입력이 항상 기저 사례의 답을 이용해야 한다.

2. 예제: 중첩 반복문 대체하기

• 집합에서 n개의 원소 중 k개를 고르는 모든 경우를 출력하는 코드를 반복문으로 구현하면 k개의 반복문을 사용해야 하므로 복잡한다. 또, k에 따라 반복문의 개수가 달라지므로 반복문으로 코드를 짤 수는 없다. 그러나 이를 재귀 함수로 나타내면 간단하게 코드를 짤 수 있다.

3. 기저 사례 선택

• 입력이 잘못되거나 범위에서 벗어난 경우도 기저 사례로 택해서 맨 처음에 처리하면 함수를 호출하는 시점에서 이런 오류를 검사할 필요가 없다. 재귀 함수는 항상 한군데 이상에서 호출되기 때문에, 이 습관은 반복적인 코드를 제거하는 데 큰 도움이 된다.

4. 완전 탐색 레시피

1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있는지를 가늠한다.
2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다.
3. 그중 한 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.
4. 조각이 하나밖에, 또는 없는 경우 답을 생성 했으므로, 이것을 기저 사례로 선택해 처리한다.

5. 이론적 배경: 재귀 호출과 부분 문제

• 원래 문제를 구성하는 조각들 중 하나를 뺀 문제를 원래 문제의 부분 문제라고 한다.

 

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.