시간복잡도와 공간복잡도

📌 시간복잡도(Time Complexity)란?
시간복잡도는 어떤 문제가 커질 때, 해결하는 데 걸리는 시간이 얼마나 늘어나는지를 나타내는 개념이야.

🏃‍♂️ 예제: 친구 찾기 게임
네가 친구 100명 중에서 한 명을 찾는 게임을 한다고 해보자!

모두 한 명씩 확인하는 방법

친구 100명에게 한 명씩 "너 철수야?"라고 물어보는 방법
이 경우, 최악의 경우 100번 물어봐야 함
→ 시간복잡도: O(N) (N명이면 N번 검사해야 함)
정렬된 명단에서 반씩 줄여가는 방법 (이진 탐색)

명단이 이름 순서대로 정리되어 있다면?
중간 친구를 보고, 철수가 앞쪽인지 뒤쪽인지 확인
이렇게 절반씩 줄여가면서 찾으면 100명이 있어도 최대 7번이면 찾을 수 있음
→ 시간복잡도: O(log N) (반씩 줄이면 시간이 훨씬 짧아짐!)
🎯 정리:
시간복잡도는 문제를 해결하는 데 걸리는 시간이 입력 크기에 따라 어떻게 변하는지를 나타내는 거야!

친구를 하나씩 찾으면 O(N)
반씩 줄이면 O(log N) (훨씬 빠름!)
📌 공간복잡도(Space Complexity)란?
공간복잡도는 문제를 해결하는 데 필요한 기억 공간(메모리)이 얼마나 늘어나는지를 나타내는 개념이야.

📦 예제: 초등학생 수학 시험 채점
너가 100명의 수학 시험 점수를 채점하고 저장하는 프로그램을 만든다고 해보자.

모든 점수를 종이에 적는 방법

100명의 점수를 전부 적어야 하니까 100칸 필요
→ 공간복잡도: O(N)
평균 점수만 저장하는 방법

점수를 하나씩 보고, 평균값만 계산해서 저장
그러면 단 하나의 숫자(평균 점수)만 기억하면 됨
→ 공간복잡도: O(1) (항상 같은 공간만 사용)
🎯 정리:
공간복잡도는 문제를 해결하는 데 필요한 메모리(기억 공간)가 입력 크기에 따라 어떻게 변하는지를 나타내는 거야!

모든 데이터를 저장하면 O(N)
계산 결과만 저장하면 O(1) (훨씬 적은 공간 사용!)
🎉 마무리 요약!
개념 뜻 예제
시간복잡도 문제가 커질 때 걸리는 시간 변화 친구 찾기: 하나씩 찾으면 O(N), 반씩 찾으면 O(log N)
공간복잡도 필요한 메모리 공간 변화 점수 저장: 전부 저장하면 O(N), 평균만 저장하면 O(1)
이제 시간복잡도랑 공간복잡도가 뭔지 알겠지? 😊
쉽게 말하면:

시간복잡도: 문제를 풀 때 걸리는 시간
공간복잡도: 문제를 풀 때 필요한 메모리 크기
🚀 빠르고 적은 메모리를 쓰는 방법을 찾는 게 프로그래밍에서 중요해!