재귀호출 관련(백트래킹, DFS) PS에 특히 약하기 때문에 재귀호출을 제대로 공부해보려 한다.
재귀호출 PS 주요 종류
단순 재귀
- 예: 팩토리얼(Factorial), 피보나치 수열(Fibonacci Sequence)
- 특징: 문제를 작은 단위로 쪼개서 반복적으로 호출하며 해결. 종료 조건(Base Case)이 명확함.
분할 정복
- 예: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 하노이 탑(Tower of Hanoi)
- 특징: 문제를 여러 하위 문제로 나누고(Divide), 각각을 해결한 뒤 합침(Conquer).
백트래킹
- 예: N-Queen 문제, 미로 찾기, 부분 집합 생성
- 특징: 해를 찾는 과정에서 조건에 맞지 않으면 이전 단계로 돌아가 다른 경로를 탐색.
트리/그래프 순회 (DFS, 이진트리순회)
- 예: DFS(깊이 우선 탐색), 이진 트리 순회(Inorder, Preorder, Postorder)
- 특징: 노드를 재귀적으로 방문하며 탐색.
DP와의 결합
- 예: 피보나치 수열(메모이제이션 적용), 배낭 문제(Knapsack Problem)
- 특징: 중복 계산을 피하기 위해 결과를 저장하며 재귀를 최적화.
1. 기본 개념 익히기
- 재귀의 핵심: 재귀는 문제를 더 작은 문제로 나누고, 그 문제를 동일한 방식으로 해결하는 방식이다.
- 필수 요소:
- 종료 조건: 재귀가 끝나는 지점 (예: depth = 5 일 때 멈춤)
- 재귀 호출: 문제를 작게 쪼개서 자신을 호출
- 연습: 팩토리얼과 피보나치 수열을 손으로 써보며 호출 과정 그려보기
트리 구조로 재귀 스택을 그리면 더 보기 쉽다.
2. 사고 방식 연습
- 문제 쪼개기: 이 문제를 더 작게 만들면 어떻게 될까? 를 고민
- 스택 이해: 재귀는 내부적으로 호출 스택을 사용. 스택이 어떻게 쌓이고 해제되는지 상상, 적으면서 문제 풀기
- 예시: 하노이 탑 문제를 풀 때 "n-1개의 원판을 옮기고, 남은 하나를 옮기고, 다시 n-1개를 옮긴다"로 분해.
💡 팁: 재귀 호출을 트리 형태로 그려보기
