# 복잡도와 입력 크기 감각

알고리즘 문제를 풀 때 가장 먼저 해야 하는 일은 "어떤 풀이가 시간 안에 가능한가"를 가늠하는 것입니다. 아이디어가 맞아도 입력 크기에 비해 복잡도가 크면 통과할 수 없습니다. 반대로 입력이 작다면 복잡한 자료구조보다 단순한 완전탐색이 더 안전할 수 있습니다.

## 시간 제한을 연산 횟수로 바꾸기

보통 1초에 몇 번의 연산이 가능한지는 언어, 서버, 연산 종류에 따라 달라집니다. 그래도 처음 풀이를 고를 때는 아래처럼 거칠게 생각하면 충분합니다.

| 감각 | 의미 |
| --- | --- |
| `10^6` 정도 | 대부분 여유 있음 |
| `10^7` 정도 | 보통 안전한 편 |
| `10^8` 정도 | C++에서도 구현과 상수에 따라 위험 |
| `10^9` 이상 | 거의 항상 다른 풀이가 필요 |

이 숫자는 정답이 아니라 필터입니다. `10^8`번의 단순 덧셈과 `10^8`번의 map 탐색, 문자열 비교, heap 연산은 체감 시간이 다릅니다. 복잡도 판단은 "가능성이 있는 후보를 남기고, 명백히 느린 후보를 버리는" 용도로 씁니다.

## 입력 크기에서 가능한 복잡도 찾기

![입력이 두 배면 n은2배, n제곱은4배, n세제곱은8배입니다. n log2 n은1024에서2048로 늘 때2.2배입니다.](lesson-assets/structure-trace.svg)

[그림 크게 보기](https://git.readiz.com/h-contest-lesson/lessons/complexity-input-size/lesson-assets/structure-trace.svg)

같은 구현에서 입력이 커질 때를 비교한 그림입니다. `n log₂ n`의 비율은 `n`에 따라 달라지며, 실제 실행 시간의 배율을 보장하는 수치는 아닙니다.

입력 크기를 보면 먼저 아래 표처럼 후보를 좁힙니다.

| 입력 크기 | 자주 가능한 복잡도 | 대표 풀이 감각 |
| ---: | --- | --- |
| `n <= 10` | `O(n!)` | 모든 방문 순서 열거 |
| `n <= 20` | `O(2^n * n)` | 비트마스크 DP |
| `n <= 100` | `O(n^3)` | Floyd-Warshall, 구간 DP |
| `n <= 2,000` | `O(n^2)` | 모든 쌍, 기본 DP |
| `n <= 100,000` | `O(n log n)`, `O(n sqrt n)` 일부 | 정렬, 이분 탐색, heap, Fenwick Tree |
| `n <= 1,000,000` | `O(n)`, `O(n log n)` 일부 | 한 번 훑기, 누적합, counting |
| `n <= 10^9` 이상 | `O(log n)`, `O(sqrt n)`, 수식 | 이분 탐색, 빠른 거듭제곱, 수학 |

예를 들어 `n <= 100,000`인데 모든 쌍을 보는 `O(n^2)` 풀이를 떠올렸다면, 대략 `10^10`번의 비교가 필요합니다. 이 경우 정렬 후 한 번 훑기, 이분 탐색, 자료구조, 누적합처럼 반복문 하나를 줄이는 구조를 찾아야 합니다.

테스트 케이스가 여러 개면 전체 비용을 합산합니다. 각 TC의 상한만 주어졌다면 최악 `T × n²`이고, 전체 입력 합에 제한이 있다면 그 제한으로 다시 계산합니다.

## 반복문을 보고 직접 세기

다음 이중 반복문이 실행되는 횟수를 세어 봅니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp
long long countPairs(int n) {
    long long count = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            count++;
        }
    }
    return count;
}
```

이 코드는 정확히 `n * (n - 1) / 2`번 반복합니다. Big-O로는 `O(n^2)`입니다. `n = 2,000`이면 약 200만 번이라 괜찮지만, `n = 100,000`이면 약 50억 번이라 어렵습니다.

중첩 반복문이 항상 `O(n^2)`인 것은 아닙니다.

```cpp
int moves = 0;
for (int left = 0, right = 0; left < n; ++left) {
    while (right < n && canExtend(left, right)) {
        right++;
        moves++;
    }
}
```

겉으로는 `for`와 `while`이 중첩되어 있지만, `right`가 전체 실행 동안 `0`에서 `n`까지 한 번만 증가한다면 `canExtend`가 `O(1)`이면 전체는 `O(n)`입니다. 투 포인터와 슬라이딩 윈도우에서 자주 쓰는 감각입니다.

## 로그와 제곱근 감각

`log n`은 아주 천천히 증가합니다. `n`이 10억이어도 `log2(n)`은 약 30입니다. 그래서 정렬의 `O(n log n)`, 이분 탐색의 `O(log n)`, heap 연산의 `O(log n)`은 큰 입력에서도 자주 버팁니다.

반대로 `sqrt n`은 `n`보다는 작지만 생각보다 큽니다.

| `n` | `sqrt(n)` |
| ---: | ---: |
| `10^4` | `100` |
| `10^6` | `1,000` |
| `10^9` | 약 `31,623` |

약수 열거, sqrt decomposition, Mo's Algorithm 같은 풀이에서는 `sqrt n`이 등장합니다. `n sqrt n`이 가능한지 판단할 때는 실제 곱을 계산해 봐야 합니다.

## 메모리도 같이 본다

시간만 맞아도 메모리가 넘치면 실패합니다. C++에서 자주 쓰는 타입 크기는 아래처럼 잡으면 됩니다.

| 타입 | 대략적인 크기 |
| --- | ---: |
| `int` | 4 bytes |
| `long long` | 8 bytes |
| `double` | 8 bytes |
| `pair<int, int>` | 8 bytes |

예를 들어 `int dp[5000][5000]`은 원소가 2,500만 개입니다. `int`는 4 bytes이므로 약 100MB가 필요합니다. 여기에 다른 배열과 실행 환경 오버헤드까지 더해지면 제한에 걸릴 수 있습니다.

원소 수를 계산하는 곱셈도 overflow가 날 수 있어 `long long`으로 계산합니다.

## 로컬 연습: 연산 수와 배열 메모리 계산

TC마다 모든 서로 다른 원소 쌍을 한 번씩 비교하고, 길이 N인 배열 하나를 재사용합니다. 전체 비교 횟수와 배열에 필요한 바이트 수를 계산하세요. 이 값은 실행 시간의 측정값이 아닙니다.

**입력:** 한 줄에 T N W. 1 <= T <= 10000, 1 <= N <= 1000000, 1 <= W <= 16이며 W는 원소 하나의 바이트 수입니다.

**출력:** 전체 비교 횟수와 배열 바이트 수를 공백으로 출력합니다. TC 사이에 배열을 재사용하므로 메모리에 T를 곱하지 않습니다.

### 예시

```text exercise=complexity-input-size role=input
3 4 8
```

```text exercise=complexity-input-size role=output
18 32
```

**확인 방법:** N <= 20에서는 두 중첩 반복문의 실제 비교 횟수와 공식을 대조합니다. N=1이면 비교는 0입니다. 곱하기 전에 long long으로 확장하고, 첫 숫자가 32비트를 넘는 입력도 넣습니다.