사용 개념: 시간 복잡도로 방법 고르기.

이 어림이 필요한 신호는 문제의 제한사항에 적힌 최대 크기다. 코드를 짜기 전에 늘 같은 네 하위목표로 센다. 파이썬은 1초에 대략 천만 번으로 잡는다.

  1. 제한 읽기: 입력의 최대 크기 n을 적는다.
  2. 단순한 방법 세기: 가장 먼저 떠오르는 방법의 계산 횟수를 n으로 쓰고, 최댓값을 넣는다. 반복문이 겹쳐 있고 안쪽 바퀴 수가 바깥 값과 상관없이 같으면, 전체 횟수는 바퀴 수끼리의 곱이다(곱의 법칙).
  3. 되는지 판단: 횟수를 천만으로 나눠 걸리는 초를 어림한다.
  4. 필요하면 더 나은 방법 세기: 안 되면 더 빠른 방법을 찾아 같은 방식으로 센다.

문제 1 · 완전한 풀이

배열 A와 B의 길이는 각각 최대 100,000이다. 두 배열에 모두 들어 있는 서로 다른 수가 몇 개인지 센다.

  1. 제한 읽기: n = 100,000.
  2. 단순한 방법 세기: A의 수마다 B를 처음부터 훑는다. 10⁵ × 10⁵ = 10¹⁰번이다.
  3. 되는지 판단: 10¹⁰ ÷ 10⁷ = 1,000초. 안 된다.
  4. 더 나은 방법 세기: B를 집합으로 바꾸면(10⁵번), A의 수마다 in이 평균 한 번에 끝난다(10⁵번). 모두 2 × 10⁵번, 0.02초 정도다. 된다.

문제 2 · 마지막 하위목표를 채운다

길이 n ≤ 2,000인 배열에서 두 수의 합이 0인 쌍 (i < j)의 개수를 센다.

  1. 제한 읽기: n = 2,000.
  2. 단순한 방법 세기: 모든 쌍을 확인한다. n(n − 1)/2 = 1,999,000번이다. i < j인 쌍은 n개 중 둘을 순서 없이 고르는 조합이라 n × (n − 1)을 2로 나눈다.
  3. 되는지 판단: __
답

2 × 10⁶ ÷ 10⁷ = 0.2초. 된다. 더 빠른 방법을 찾을 필요가 없다. 제한이 작으면 단순한 방법이 가장 좋은 답이다.

문제 3 · 하위목표 절반을 채운다

정수 n ≤ 1,000,000개 가운데 가장 자주 나온 수를 찾는다.

  1. 제한 읽기: n = 1,000,000.
  2. 단순한 방법 세기: __
  3. 되는지 판단: 안 된다.
  4. 더 나은 방법 세기: __
답

  1. 수마다 a.count(x)로 배열 전체에서 센다. count는 O(n)이니 n × n = 10¹²번이다.

  2. 딕셔너리로 한 번 훑으며 센다. 10⁶번, 0.1~0.3초다. 정렬한 뒤 같은 수가 이어진 길이를 세도 된다. 이때는 n log n ≈ 10⁶ × 20 = 2 × 10⁷번이다. log₂ 10⁶ ≈ 20인 것은 2²⁰ = 1,048,576이 100만에 가깝기 때문이다(로그).

문제 4 · 혼자 풀기

친구 n명 가운데 몇 명을 골라 모임을 만든다. 가능한 모든 모임을 하나씩 만들고, 모임마다 n명을 훑어 조건을 확인한다. n ≤ 18이면 될까? n ≤ 30이면?

답

모임은 친구마다 “넣는다/안 넣는다”로 2ⁿ가지다. 모임마다 n번 훑으니 2ⁿ × n번이다.

  • n = 18: 2¹⁸ × 18 = 4,718,592번. 0.5초 정도라 된다.
  • n = 30: 2³⁰ × 30 ≈ 3.2 × 10¹⁰번. 3,000초가 넘어 안 된다.

지수로 늘어나는 방법은 n이 조금만 커져도 갑자기 안 된다. n이 1 늘 때마다 시간이 두 배쯤 되기 때문이다. 2ⁿ처럼 n이 “몇 번 곱하는가”를 정하면 지수, n²처럼 “곱해지는 값”이면 거듭제곱이다(거듭제곱함수와 지수함수 비교).