어림짐작을 의심하기

알고리즘 문제 해결에는 명시적인 자원 제한이 있다. 메모리와 시간. 너무 많은 메모리를 사용해서도 안 되고, 너무 오랜 시간이 걸려서도 안 된다.

 

이러한 자원 제한이 문제 해결에서만 중요한 것은 아니다. 오히려 실무에서 더욱 중요한 지점이지 싶다. 실무에서는 자원이 곧 비용이므로. 당연하게도 이러한 자원 소모를 미리 가늠하는 실력이 필요해진다.

 

지난달 중순경에 소수 구하기라는 문제를 풀었다. 잘 알려진 풀이는 다음과 같을 것이다:

m, n = map(int, input().split())

for i in range(m, n+1):
    if i == 1:
        continue
    for j in range(2, int(i**0.5)+1):
        if i%j == 0:
            break
    else:
        print(i)

 

약수는 쌍으로 이루어지므로 합성수임을 판단하기 위해서는 그 쌍 중 절반만 보면 되는데, 제곱근이 약수 쌍의 중앙값에 해당하기 때문에 제곱근 근처까지만 확인하면 된다는 것이 논리의 골자다.

 

나는 이 풀이의 흐름에서 아쉬운 지점이 있었다. 2로 나눠지지 않는 숫자를 2의 배수로도 나누는 시도를 하는 등의 부분이 있기 때문이다. 나는 따라서 다음과 같은 풀이를 제출하였다:

m, n = map(int, input().split())

prime = [2]
for i in range(3, n+1):
    for elem in prime:
        if i%elem == 0:
            break
    else:
        prime.append(i)
        if i >= m:
            print(i)

 

sqrt(n)보다 n 이하의 소수 갯수가 더 클 때는 i가 소수일 경우 두 번째 풀이의 반복문이 더 많이 돌지만, 큰 숫자일수록 합성수의 비율이 커지므로 나는 두 번째 풀이가 속도 측면에서 우월할 거라고 보았다. 단적인 예로 997을 가장 작은 약수로 갖는 숫자에 대해서 합성수임을 판단하기 위해 첫 번째 코드는 997번의 연산을 필요로 하지만 두 번째 코드는 168번의 연산만을 필요로 하므로.

 

결과는? 시간 초과.

 

'크~ 이런 풀이를 생각해내다니 기분이가 좋네~' 따위의 생각은 한순간에 박살이 났다. 수많은 물음표가 머릿속을 메웠다. '뭐지? 뭐가 잘못된 거지?'

 

당시의 나는 문제 해결 공부를 시작한 지 1달도 되지 않은 시점이었고(핑계 맞음ㅎ;), 'append와 list 참조에 드는 상수 시간이 커서 그런가 보다'라고만 생각하고 넘어갔었다. 그리고 인터넷을 떠돌다가 저 문제를 마주하게 되어 다시금 생각이 났다.

 

…정말로 두 번째 풀이가 우월할까?

 

나는 코드 중간에 1씩 증가하는 변수를 삽입하여 break가 걸리기 전까지의 연산 횟수를 세어보기로 했다. 입력값은 1 100000. 즉 1부터 100000 사이의 소수를 검증 및 출력하게 된다.

 

첫 번째 코드는 2,745,694. 두 번째 코드는 46,314,477.

단위가 다르다! 거의 20배 가까이 차이가 난다. 내 예상이 틀린 셈.

 

혹시 모른다. n이 크면 클수록 두 번째 풀이가 더 우월할지도. n을 변화시켜가며 연산 횟수를 측정하였다.

n	sqrt(n)	prime = []
10	8	12
100	236	411
1000	5288	15620
10000	117527	776631
100000	2745694	46314477
1000000	67740404	3085786713

 

오히려 증가폭이 훨씬 커지는 것을 확인할 수 있었다. 내 "어림짐작"은 택도 없이 틀렸던 것이다.

 

어째서 이런 일이 일어났을까? 이유는 2개라고 생각한다.

 

1) 소수의 갯수 증가속도가 sqrt(n)의 증가속도보다 지배적(dominant)이기 때문에. 나는 범위가 커질수록 소수의 비율이 많이 줄어들거라고 생각했는데, 실제로 살펴보니 소수는 적당히 큰 범위에서도(1e25 이하) 거의 선형적으로 증가했다. 하지만 sqrt(n)은 (당연하게도) sqrt(n)의 증가율을 따른다. 두 번째 코드가 열위에 있는 부분이 내 생각만큼 줄어들지 않았던 것이다.

 

2) 다른 부분에서 갖는 우위가 1번에 비해서 미미하기 때문에. 2의 배수는 997을 가장 작은 약수로 갖는 수보다 압도적으로 많다. 즉 두 번째 코드가 우위에 있는 부분이 내 생각만큼 많지 않다는 뜻이다. 고작 몇몇 케이스에 대해서 두 번째 코드가 우위를 가져봐야 지배적인 부분에 비해서는 미미한 수치였던 것.

 

물론 이 또한 정확한 접근은 아니다. 출력값을 가져다 시각화를 하는 편이 보다 명백할 것이다.

 

그럼에도 깨달은 점이 있었다. 예측(estimation)에서 중요한 것은, 빅오 표기법에 대해 배울 때 들었듯이, 지배적인 항의 동향이다. order of magnitude에 가장 큰 영향을 주는 부분…….

 

번뜩이는 아이디어는 물론 그 자체로 소중하다. 다만 섣부르게 판단하는 일이 위험하다. 가늠한 바에 대해서는 검증을 해야 한다.

 

어림짐작을 의심해야만 한다.