1. 복잡도란?

• 어떤 문제를 얼마나 빨리, 얼마나 효율적으로 푸는가를 나타내는 척도예요.
• 즉, 프로그램이 입력을 받았을 때 시간이 얼마나 걸릴지, 메모리를 얼마나 쓸지를 수학적으로 계산하는 방법이에요.

2. 시간 복잡도 (Time Complexity)

👉 프로그램이 실행될 때 걸리는 시간이 입력 크기에 따라 어떻게 늘어나는지를 보는 것.

예시:

• 배열 길이가 10일 때: for문이 10번 돈다.
• 배열 길이가 100일 때: for문이 100번 돈다.

→ 실행 횟수가 입력 크기 N에 비례하니까

이런 걸 O(N)이라고 적어요.

여기서 O는 "order of"(크기 정도)라는 의미예요.

3. 공간 복잡도 (Space Complexity)

👉 프로그램이 실행될 때 메모리를 얼마나 차지하는지 보는 것.

• 예: 크기 100인 배열을 만든다 → O(N) 공간.
• 그냥 변수 하나만 쓴다 → O(1) 공간.

4. 자주 쓰이는 복잡도 예시

• O(1): 상수 시간 - 입력 크기가 얼마든 항상 같은 시간 (예: 변수에 값 할당하기).