2026-04-29 TIL (47일차)

알고리즘

분할 정복과 재귀란?

• 분할 정복: 말 그대로 엄청나게 크고 복잡한 문제를, 해결할 수 있을 만큼 아주 작은 단위로 쪼개어(Divide) 해결(Conquer)한 뒤, 그 결과들을 다시 합치는(Combine) 알고리즘 설계 기법입니다. (예: 병합 정렬)
• 재귀와의 관계: 문제를 쪼개다 보면 “크기만 작아졌지, 결국 똑같은 성질의 문제”가 됩니다. 따라서 자기를 다시 부르는 재귀 함수를 사용하는 것이 가장 자연스럽고 완벽한 짝꿍이 됩니다.

재귀 VS 반복문

둘 다 ‘어떤 작업을 반복한다’는 목적은 같지만, 동작 방식과 메모리 사용에 큰 차이가 있습니다.

• 반복문 (for, while):
  • 메모리를 거의 쓰지 않아 가볍고 속도가 빠릅니다.
  • 로직이 복잡해지면(예: 트리 순회, 그래프 탐색) 코드가 엄청나게 길어지고 가독성이 떨어집니다.
• 재귀 (Recursion):
  • 함수가 자신을 부를 때마다 메모리의 ‘콜 스택(Call Stack)’에 데이터가 차곡차곡 쌓입니다. 너무 깊이 들어가면 메모리가 터지는 스택 오버플로우(Stack Overflow) 위험이 있습니다.
  • 코드가 수학 공식처럼 매우 간결해지고 가독성이 압도적으로 좋아집니다.

사고방식의 차이

재귀를 어려워하는 이유는 반복문의 ‘순차적’ 사고방식에 익숙해져 있기 때문입니다.

• 반복문적 사고 (Bottom-Up): “1부터 10까지 1씩 더해가면서 올라가야지. 1 더하고, 그다음 2 더하고…” (과정을 하나하나 통제)
• 재귀적 사고 (Top-Down & 위임): “나머지 작은 문제들은 이미 완성되었다고 믿고 맏기자!”
  • 예를 들어 $1$부터 $100$까지 더해야 한다면, “나는 $100$만 더할 테니, 누군가 $1$부터 $99$까지 더한 결과를 나한테 가져와!”라고 자신 있게 떠넘기는(위임) 마인드가 필요합니다.

수학적 귀납법

“재귀 함수가 진짜로 끝까지 잘 동작할까?”라는 불안감을 없애주는 수학적 증명 방식입니다.

1. 기저 조건(Base Case): $N = 1$일 때 성립함을 증명한다. (재귀의 탈출 조건)
2. 귀납적 가정: $N = K$일 때 성립한다고 가정(믿음)한다.
3. 증명: 그 가정을 바탕으로 $N = K + 1$일 때도 성립함을 증명한다.

   핵심: 재귀 코드를 짤 때 “함수가 $N-1$을 완벽하게 처리해 줄 것이다”라고 믿고(가정하고), 나는 $N$일 때의 처리만 딱 적어주면 전체가 수학적으로 완벽하게 돌아간다는 뜻입니다.

꼬리 재귀

재귀의 치명적인 단점인 ‘스택 오버플로우’를 해결하기 위한 특수한 코딩 기법입니다.

• 조건: return RecursiveCall(); 처럼 재귀 함수를 호출하는 시점이 함수의 제일 마지막(꼬리)이어야 하며, 반환된 이후에 추가적인 연산(+ 1 등)이 없어야 합니다.
• 장점 (꼬리 재귀 최적화): 컴파일러가 이 코드를 보고 “어? 굳이 메모리 스택을 계속 쌓을 필요 없이 반복문(while)처럼 덮어쓰기로 몰래 바꿔치기해도 똑같겠네?” 하고 내부적으로 최적화(Tail Call Optimization)를 해줍니다. 덕분에 재귀의 가독성을 챙기면서 반복문의 성능을 얻을 수 있습니다.

피보나치 수열과 DP

피보나치 수열은 fib(n) = fib(n-1) + fib(n-2) 로 정의되는 완벽한 재귀의 예시입니다. 하지만 그냥 재귀로 풀면 대참사가 일어납니다.

🔹 중복 계산의 지옥 ($O(2^n)$)

fib(40)을 구하기 위해 컴퓨터는 fib(39)와 fib(38)을 부릅니다. 그런데 fib(39) 안에서도 또 fib(38)을 부릅니다. 이렇게 가지를 치며 내려가다 보면, 고작 fib(2)나 fib(3) 같은 작은 값들을 구하기 위해 똑같은 계산을 수백만 번, 수천만 번 중복해서 반복하게 됩니다.

🔹 구원자: 메모이제이션(Memoization)과 DP

• 해결책: “한 번 계산한 정답은 수첩(배열 등)에 메모해 두자!”
• 동작 원리 (메모이제이션): fib(n)을 호출했을 때, 수첩을 먼저 봅니다.
  1. 수첩에 적혀있으면? 👉 계산 안 하고 그냥 그 값을 바로 반환! (초고속)
  2. 안 적혀있으면? 👉 그때만 열심히 계산해서 정답을 수첩에 적어놓고 반환!
• 결과: 수천만 번 하던 중복 연산이 싹 사라지고, 단 40번의 계산(시간 복잡도 $O(N)$)만으로 끝나는 기적이 일어납니다. 이것이 바로 동적 프로그래밍(DP)의 핵심인 ‘부분 문제의 중복(Overlapping Subproblems)’ 해결입니다.