시간 복잡도 생각하며 문제 풀기

3중 반복문으로 통과한 문제와 2중 반복문인데 시간 초과가 난 문제를 같은 날 만났습니다. 차이는 코드가 아니라 제한사항에 있었습니다

개요

같은 날 두 문제를 풀었는데 결과가 반대였습니다. 3중 반복문을 쓴 쪽은 통과했고, 2중 반복문인 쪽은 시간 초과가 났습니다. 3중 반복문을 제출할 때는 오히려 "이렇게 겹쳐도 되나" 싶었는데 통과했고, 반복문을 하나 줄인 쪽이 떨어졌습니다

원인은 코드가 아니라 문제가 준 제한사항에 있었습니다. 그동안 제한사항을 "입력이 이 범위로 들어온다"는 안내문 정도로 읽었는데, 사실은 어떤 풀이를 써도 되는지를 정해주는 조건이었습니다

3중 반복문인데 통과한 문제

삼총사 문제입니다. 학생들의 소지금 배열에서 세 명을 뽑아 합이 0이 되는 조합의 개수를 구합니다

세 명을 뽑는 모든 조합을 만들어 합이 0인지 확인했습니다

def solution(number):
    count = 0
    for i in range(len(number) - 2):
        for j in range(i + 1, len(number) - 1):
            for k in range(j + 1, len(number)):
                if number[i] + number[j] + number[k] == 0:
                    count += 1
    return count

안쪽 반복문이 각각 i + 1, j + 1에서 시작하는 것이 핵심입니다. 이렇게 하면 같은 사람을 두 번 뽑거나, 이미 센 조합을 순서만 바꿔 또 세는 일이 없습니다

3중 반복문이면 계산량은 n³입니다. 제한사항을 보니 배열 길이가 최대 13이었습니다.

13³ = 2,197

2천 번이면 시간 제한에 걸릴 일이 없습니다

2중 반복문인데 시간 초과가 난 문제

기사단원의 무기 문제입니다. 1번부터 number번까지 각 기사의 번호마다 약수의 개수만큼 철을 쓰고, 그 개수가 limit을 넘으면 power로 대체해 총합을 구합니다

약수의 개수를 세야 하니 1부터 그 수까지 나누어떨어지는지 전부 확인했습니다

def solution(number, limit, power):
    divisor_arr = []

    for num in range(1, number + 1):
        count = sum(1 for i in range(1, num + 1) if num % i == 0)
        divisor_arr.append(count)

    for i in range(len(divisor_arr)):
        if divisor_arr[i] > limit:
            divisor_arr[i] = power

    return sum(divisor_arr)

로직은 맞았고 예제도 통과했습니다. 그런데 채점하니 시간 초과가 났습니다. 반복문은 삼총사보다 하나 적은데 왜 이쪽만 죽는지 한참 감이 안 와서 제한사항을 다시 봤습니다

1 ≤ number ≤ 100,000

기사가 10만 명이고, 각 기사마다 자기 번호까지 확인하니 또 최대 10만 번입니다

100,000 × 100,000 = 10,000,000,000 (100억)

삼총사는 2천 번이었는데 이쪽은 100억 번입니다. 반복문은 오히려 하나 적은데 계산량은 400만 배가 넘습니다

제한사항을 읽는 법

두 문제의 차이는 제한사항에 적힌 최대 크기였습니다. 그래서 코드를 짜기 전에 30초만 계산해 보기로 했습니다

① 제한사항에서 최대 크기를 찾는다
② 내가 쓰려는 방법의 계산량을 곱한다
③ 1억을 넘으면 그 방법은 버린다

1억이 기준인 이유는 대부분의 채점 환경이 1초에 1억 번 정도를 처리하기 때문입니다. 이 기준으로 반복 깊이별 감당 가능한 크기를 정리해봤습니다

이 표를 놓고 다시 보면 두 문제의 제한사항이 다르게 읽힙니다

• 삼총사의 n ≤ 13은 3중 반복(450까지)은 물론 부분집합(25까지)도 됩니다. 다 뒤져봐도 된다는 뜻입니다
• 기사단원의 number ≤ 100,000은 2중 반복(1만까지)부터 이미 막힙니다. 생각 없이 짜면 안 되는 문제였습니다

제한을 100으로 줬다면 처음 코드도 통과했을 겁니다. 10만이라는 숫자 자체가 다른 방법을 찾으라는 표시였습니다

약수는 √n까지만 세면 된다

약수를 더 빨리 세는 방법이 필요했습니다. 36의 약수를 짝지어 나열해 보니 규칙이 보였습니다

1 × 36
2 × 18
3 × 12
4 × 9
6 × 6      ← √36 = 6, 여기가 접히는 지점
9 × 4      ↑ 위에서 나온 짝이 뒤집혀서 반복됩니다
12 × 3
18 × 2
36 × 1

약수는 반드시 짝을 이루어 나옵니다. 그리고 그 짝에서 작은 쪽은 전부 √n 이하, 큰 쪽은 전부 √n 이상입니다. 그래서 1부터 √n까지만 확인하면 모든 짝을 한 번씩 만납니다. 작은 쪽(1, 2, 3, 4, 6)을 찾을 때마다 큰 쪽(36, 18, 12, 9, 6)은 확인하지 않아도 있는 것이 확실하니, 개수만 2씩 더하면 됩니다

count = 0
i = 1
while i * i <= num:
    if num % i == 0:
        if i == num // i:       # 짝이 자기 자신인 경우
            count += 1
        else:                   # 작은 쪽 i와 큰 쪽 num // i, 둘 다 센다
            count += 2
    i += 1

여기서 num // i는 i의 짝꿍입니다. i가 3이면 짝꿍은 12이고, 서로 다른 약수이므로 2를 더합니다

제곱수에서 한 번 걸렸습니다

i == num // i 분기가 왜 필요한지는 36에서 확인했습니다. i가 6일 때는 짝꿍도 6이라 자기 자신과 짝이 되는데, 이때 2를 더하면 6을 두 번 세게 됩니다

36의 약수: 1, 2, 3, 4, 6, 9, 12, 18, 36 → 9개

i = 1, 2, 3, 4에서 각각 2개씩 → 8개
i = 6에서 2개를 더하면 → 10개 ✗ (6을 두 번 셈)
i = 6에서 1개만 더하면 → 9개 ✓

제곱수만 약수의 개수가 홀수인 것도 같은 이유입니다. 가운데 짝이 자기 자신이라 혼자이기 때문입니다

확인한 경계값은 세 가지였습니다

int(num ** 0.5) 대신 i * i <= num

반복 조건을 쓰는 방법은 두 가지입니다

for i in range(1, int(num ** 0.5) + 1):   # 제곱근을 구해서 정수로 자른다
while i * i <= num:                        # 곱셈으로 비교한다

같은 범위를 돌지만 아래쪽이 더 안전합니다. ** 0.5는 소수를 만들기 때문입니다

√12 = 3.4641...처럼 대부분의 제곱근은 딱 떨어지지 않고, 컴퓨터는 이를 유한한 자리에서 끊어 저장합니다. 이때 생기는 미세한 오차가 하필 제곱수에서 문제가 됩니다

이상적:  √25 = 5.0       → int(5.0) = 5     → 5까지 확인 ✓
오차 시: √25 = 4.999...  → int(4.999) = 4   → 4까지만 확인 ✗ (5 × 5를 놓침)

int()는 버림이라 오차가 조금만 아래로 생겨도 경계값 하나를 통째로 놓칩니다. 반면 i * i <= num은 정수끼리의 곱셈이라 오차가 생길 자리가 없습니다

소수를 만들지 않으면 소수 오차도 없습니다. 나눗셈이나 제곱근을 곱셈으로 바꿀 수 있는지 먼저 보는 편이 낫습니다

얼마나 빨라졌나

같은 문제를 두 방식으로 로컬에서 재봤습니다

배율이 고정이 아닙니다. 10.3배에서 33.5배, 38.5배로 벌어집니다. 몇 배 빨라진 것이 아니라 늘어나는 속도 자체가 달라졌기 때문입니다. 10만은 개선 전 코드로 재는 걸 포기했습니다. 1만에서 1.777초였으니 10만이면 그 100배가 넘게 걸립니다

마치며

• 반복문이 몇 겹인지보다 제한사항의 최대 크기가 통과 여부를 정합니다. 3중 반복이 통과하고 2중 반복이 떨어질 수 있습니다
• 코드를 짜기 전에 제한 × 계산량이 1억을 넘는지 먼저 계산하게 됐습니다. 넘으면 그 방법은 버리고 다른 방법을 찾습니다
• 제한이 유난히 크면 단순하게 전체를 훑는 방법은 막혔다는 표시였습니다
• 약수는 √n을 기준으로 짝을 이루므로 √n까지만 확인하면 됐습니다. 단 제곱수는 가운데 짝이 자기 자신이라 한 번만 세야 했습니다
• 제곱근이나 나눗셈처럼 소수를 만드는 연산은 가능하면 정수 연산으로 바꿨습니다