코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
알고리즘 — 문제 해결의 체계적 접근 → 기초 알고리즘
재귀(Recursion)는 프로그래밍의 가장 강력한 사고 도구이고, 분할정복(Divide & Conquer)은 이 사고를 알고리즘으로 확장한 것입니다.
재귀가 중요한 이유:
분할정복이 중요한 이유:
이 레슨에서 배울 것:
1. 재귀적 사고의 원리
2. 분할정복의 3단계 패턴
3. 머지소트 심화
4. 거듭제곱, 카라츠바 곱셈
5. Master Theorem
여러분, 오늘부터 재귀와 분할정복을 배웁니다.
왜 이 주제가 중요할까요?
화면 왼쪽을 보세요, 재귀가 쓰이는 곳들이 나와 있습니다.
트리 탐색, 그래프 탐색의 기본 도구가 바로 재귀입니다.
DFS를 짤 때 재귀 없이는 시작조차 어렵죠.
또한 DP와 백트래킹의 출발점이 재귀라는 점도 중요합니다.
재귀를 모르면 DP를 이해하는 게 사실상 불가능합니다.
수학에서 귀납법 증명 구조가 재귀 구조와 완전히 같다는 것도 기억하세요.
이제 가운데 주황색 박스를 보세요.
분할정복은 쪼개고, 정복하고, 합치는 세 단계입니다.
재귀라는 사고 도구를 알고리즘 전략으로 확장한 것이죠.
오른쪽을 보면 분할정복의 대표 알고리즘들이 있습니다.
머지소트는 O(n log n)의 안정 정렬입니다.
퀵소트는 실전에서 가장 빠른 정렬 알고리즘이고요.
카라츠바는 큰 수 곱셈을 O(n²)에서 O(n의 1.585승)으로 줄입니다.
Master Theorem은 분할정복의 복잡도를 바로 구하는 만능 공식입니다.
하단 초록색 결론을 보세요.
재귀는 사고 도구이고, 분할정복은 이 사고를 쓰는 설계 전략입니다.
이 레슨에서 두 가지를 완전히 마스터하는 것이 목표입니다.
자, 그럼 재귀적 사고부터 시작해볼까요?