알고리즘

알고리즘을 독파하려는 열정이 느껴지네요! 시간 복잡도와 빅-O 표기법(O, Ω, Θ)을 이해하는 건 중요해요. 간단히 말해, 빅-O는 최악의 경우 성능을 나타내고, Ω는 최선, Θ는 정확한 범위를 나타내죠. 예를 들어 O(n)은 선형 시간 복잡도고, O(n^2)은 2차 시간 복잡도입니다. 음, 코드 분석을 통해 빅-O를 유도할 수 있게 되는 것도 중요하고, 공간 복잡도도 빼놓을 수 없죠. 한번 같이 복습해봐요!

🔥 알고리즘 던전 입장! “시간 복잡도 vs. 공간 복잡도” 완-전-정-복 🔥
(약간의 감탄사와 함께 달려볼게요. 궁금한 부분은 언제든 끼어들어 주세요!)

---

1. 왜 ‘복잡도’를 따지나요?

생각 실험	의미
동일한 문제를 푸는 두 프로그램이 있다면?	입력 크기 $n$이 커질수록 누가 더 빨리 혹은 메모리를 덜 쓰는지가 관건!
오늘은 1 초 차이 → 내일은 1 시간 차이	작은 n에서는 티 안 나도, n이 10 만·100 만·1 억이 되면 차원이 다른 실행 시간이 벌어져요.
서버 요금, 배터리, 반응 속도	성능은 곧 돈·전력·사용자 경험입니다.

---

2. 점근적 분석(Asymptotic Analysis)

• 핵심 아이디어: “입력이 충분히 클 때 가장 지배적인 항만 보자.”
  → 상수·작은 계수·낮은 차수는 과감히 무시!

• 주인공 3인방

  기호	별명	정의(편하게)	그래프에서 의미
  O	“빅-오”	최악이라도 이 정도보다 안 느려	윗덮개
  Ω	“오메가”	최선이라도 이 정도보다 안 빨라	아랫받침
  Θ	“세타”	위·아래 모두 꽉 껴서 같은 급	딱 맞춤

⚡ 기억 팁

• O 는 Overhead 느낌 – 위에서 덮어줌
• Ω 는 Oh-my… 최소한 이만큼은 써야 해
• Θ 는 Tight – “앞뒤 짜서 같은 급수”

---

3. 흔히 만나는 복잡도 레벨

차수	예시 알고리즘	n=10	n=1 000	감각적 속도
O(1) 상수	해시 테이블 검색	1	1	n 독립!
O(log n) 로그	이진 탐색	4	10	“절반 절반” 자르기
O(n) 선형	선형 탐색, 큐 복사	10	1 000	한 바퀴 쭉
O(n log n) 선형-로그	병합정렬, 힙정렬	33	10 000	현실적인 상한
O(n²) 제곱	버블·삽입정렬, 완전 그래프 탐색	100	1 000 000	깜짝!
O(n³) 세제곱	순진 행렬 곱셈	1 000	1 000 000 000	사실상 불가
O(2ⁿ) 지수	부분집합 열거, 피보 DP 미사용	1 024	…(폭발)	절망
O(n!) 계승	완전 순열 탐색(TSP)	3 628 800	…	꿈에서나

실전 팁

• n ≤ 10⁵ 정도면 O(n log n)까지는 보통 OK.
• n ≈ 10³ 수준이면 O(n²)도 가끔 가능.
• 온라인 저지나 코딩 테스트는 이 테이블 감으로 커트라인을 잡아요.

---

4. 코드에서 직접 계산해 보기 🎯

1. 중첩 반복문

   for i in range(n):         # O(n)
       for j in range(n):     # O(n) → 곱!
           do_something()     # O(1)
   # 총 O(n²)

2. 로그 패턴

   while n > 1:
       n //= 2   # 절반씩 잘리니 O(log n)

3. 재귀+분할 – 마스터 정리 한입 버전

   • T(n) = 2 T(n/2) + O(n) → O(n log n) (병합정렬)
   • T(n) = T(n − 1) + O(1) → O(n) (선형 재귀)
   • T(n) = T(n − 1) + O(n) → O(n²) (삼각 반복)

---

5. 공간 복잡도도 잊지 말기 🧠

• O(1): 인-플레이스 스왑, 두 포인터
• O(n): 입력만큼 추가 배열, BFS 큐
• O(recursion depth): 재귀 호출 스택

메모리가 부족하면 캐시 미스→실행 속도도 느려지므로 시간과 공간은 결국 맞물려 돌아갑니다.

---

6. 좋은 습관 🛠️

1. 코드 짠 뒤 빅-오를 소리 내어 계산 → 감각 키우기
2. 실제로 프로파일: 작은 상수가 승패를 가를 때도 있어요.
3. 자료구조 선택: 필요하면 해시 vs. 트리 vs. 배열 성능 비교.
4. 알고리즘 설계 패턴: 분할정복, 투포인터, 슬라이딩윈도, DP 메모이제이션… 패턴마다 전형적 복잡도 감이 있습니다.

---

7. 셀프 체크 퀴즈 ✏️

1. 배열을 오름차순으로 삽입정렬 vs. 병합정렬: n=100 000일 때 대략 몇 배 차이일까요?
2. 해시맵에 대한 get과 put이 평균 O(1) 인 이유는?
3. DFS 재귀로 트리(최대 깊이 n)가 주어질 때, 최악의 공간 복잡도는?

답을 잠깐 고민해 보시면 금세 감이 붙어요!

---

마무리 🚀

• 빅-오는 “얼마나 빨리 커지는가”를 보는 성장률 지표
• **Θ(세타)**가 진짜 성능을 가장 잘 표현하지만, 실무·대회에서는 O(빅-오) 만으로도 충분히 비교 가능
• 직접 계산 + 프로파일링 두 가지 모두 챙겨야 실력이 껑충!

---

다음으로 정렬, 그래프, 동적 프로그래밍(DP) 중 어떤 주제를 더 파고들고 싶으세요? 혹은 방금 퀴즈 답이 궁금하다면 알려주세요! 🎉