이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 알고리즘 — 문제 해결의 체계적 접근 → 알고리즘 — 문제 해결의 체계적 접근 → 기초 알고리즘
Learn recursive thinking, divide and conquer pattern, merge sort deep dive, fast exponentiation, Karatsuba multiplication, and Master Theorem.
여러분, 오늘부터 재귀와 분할정복을 배웁니다.
왜 이 주제가 중요할까요?
화면 왼쪽을 보세요, 재귀가 쓰이는 곳들이 나와 있습니다.
트리 탐색, 그래프 탐색의 기본 도구가 바로 재귀입니다.
DFS를 짤 때 재귀 없이는 시작조차 어렵죠.
또한 DP와 백트래킹의 출발점이 재귀라는 점도 중요합니다.
재귀를 모르면 DP를 이해하는 게 사실상 불가능합니다.
수학에서 귀납법 증명 구조가 재귀 구조와 완전히 같다는 것도 기억하세요.
이제 가운데 주황색 박스를 보세요.
분할정복은 쪼개고, 정복하고, 합치는 세 단계입니다.
재귀라는 사고 도구를 알고리즘 전략으로 확장한 것이죠.
오른쪽을 보면 분할정복의 대표 알고리즘들이 있습니다.
머지소트는 O(n log n)의 안정 정렬입니다.
퀵소트는 실전에서 가장 빠른 정렬 알고리즘이고요.
카라츠바는 큰 수 곱셈을 O(n²)에서 O(n의 1.585승)으로 줄입니다.
Master Theorem은 분할정복의 복잡도를 바로 구하는 만능 공식입니다.
하단 초록색 결론을 보세요.
재귀는 사고 도구이고, 분할정복은 이 사고를 쓰는 설계 전략입니다.
이 레슨에서 두 가지를 완전히 마스터하는 것이 목표입니다.
자, 그럼 재귀적 사고부터 시작해볼까요?
선생님: 재귀가 왜 중요한지 한마디로 말해볼래요?
학생: 트리 탐색이나 DP 같은 고급 알고리즘의 기본이니까요?
선생님: 맞아요! 재귀를 모르면 DFS도 DP도 이해가 안 돼요.
학생: 분할정복은 재귀랑 어떻게 다른 거예요?
선생님: 분할정복은 재귀적 사고를 쪼개고 합치는 전략으로 확장한 거예요.
선생님: 재귀가 도구라면 분할정복은 그 도구를 쓰는 설계 패턴이에요.