오늘 다룰 소재는 프로젝트에 집중하느라 글쓰기를 잠정적으로 중단하고 있는 나에게 다시금 글을 쓰게한 엄청난 녀석이다. 제목이 다소 파격적이다. 실제로 while문 + α때문에 엄청난 시간적 소모를 겪었기에 이렇게 지을 수 밖에 없었다. 무슨 일을 겪었고 앞으로 while문을 쓸 일은 없겠네.라 생각한 필자의 경험을 구구절절이 설명하려한다.

문제의 시발점

최근에 카카오 경력직 코딩 테스트를 치뤘다. 문제는 hackerrank에서 총 3개의 문제가 출제됐으며, 난이도가 썩 높진 않아 푸는데에 1시간30분정도 걸렸던 것 같다. 그런데 최종적으로 내가 맞춘 문제는 두 문제가 전부였다. 이유는 마지막 문제의 시간복잡도를 남은 2시간 30분동안 해결해지 못한 것이 원인인데, 이 때까지만 해도 그냥 내 잘못인줄만 알았다. 아니 사실 내 잘못이지. 누굴 탓해.

이후에 카카오 최종면접에서 광탈한 후, 다시 코딩 테스트를 준비해야했기때문에 친구의 추천으로 codility에서 문제를 풀고 있었다. 그리고 나는 다시 한 번 time complexity의 늪으로 빠져들었다.

N^2으로 푸셨네요 휴먼? 머리를 좀 더 써보시죠? 라고 한다.

그런데 내가 제출한 코드는 다음과 같았다.

def solution(A):
    result=1
    A=sorted(A)
    while A:
      a = A.pop(0)
      if a==result:
        result+=1
    return result

???

눈을 비비고 읽어보았다. sorted는 o(nlogn), while은 o(n). 어렸을 적 배운 덧셈을 통해 더해보면 o(nlogn + n)

알파고가 오답을 낸 순간을 목격했다

뭐 여튼 틀렸다고 하니까 새로운 답을 찾아나섰고 while문으로 계속 쉐도우복싱하다가 포기하고 인터넷에서 답안을 찾아보았다.

def solution(A):
    result=1
    A=sorted(A)
    for a in A:
      if a==result:
        result+=1
    return result

???

고작 다른 점은 while문에 for문으로 대체되었고, pop() 메소드가 새로 생긴 것뿐이였다. pop() 메소드는 python에서 O(1)로 동작한다고 알고 있었기에 사건은 점점 미궁으로 빠져들었다.

아니야 뭔가 다를거야 - 디스어셈블리

어딘가에 분명 문제가 존재했고 각각의 파이썬 코드의 bytecode를 디스어셈블리하였다. 어셈블리 변환에는 파이썬 내장 모듈 dis를 사용했다.

for문

  6          18 SETUP_LOOP              39 (to 60)
             21 LOAD_FAST                0 (A)
             24 GET_ITER
        >>   25 FOR_ITER                31 (to 59)
             28 STORE_FAST               2 (a)

while문

 14          18 SETUP_LOOP              50 (to 71)
        >>   21 LOAD_FAST                0 (A)
             24 POP_JUMP_IF_FALSE       70

 15          27 LOAD_FAST                0 (A)
             30 LOAD_ATTR                1 (pop)
             33 LOAD_CONST               2 (0)
             36 CALL_FUNCTION            1
             39 STORE_FAST               2 (a)

동일한 코드 부분은 생략한 어셈블리코드 모습이다. 간단히 첨언하자면 line 6는 for문의 동작으로 iterator을 가져와서 next를 해가며 loop을 하고, line14는 while의 동작으로 정적인 iterator가 아닌 동적으로 매번 loop마다 조건을 체크하는 것을 볼 수 있다.

그리고 line15는 A.pop(0)의 동작이다.

별다른 특이점은 찾지 못했다.

아니야 뭔가 다를거야 - timer

별 다른 소득이 없었던 어셈블리코드를 제쳐두고 실제 어느 부분이 심각하게 동작에 영향을 미치는지 시간을 체크해봤다.

함수 비교

지수적으로 배열의 길이를 증가시켜가며 for문으로 작성한 코드와 while문으로 작성한 코드의 시간소요를 체크해봤다. 배열 길이 리미트는 10,000,000으로 설정하였다. 결과는 충격적이다. 실제로 본 그래프 추출을 위한 러닝타임에 글을 전부 미리 다 써놓을 정도였다. 도대체 while문의 어디가 그렇게 잘못된 걸까.

코드 블록

내가 작성한 코드 내에서의 while문과 for문의 유일한 차이 A.pop(0)에 timer를 걸어보았다. 그리고 array size 1,000,000인 경우, 본 코드 블록에서 매 loop마다 80ms 정도의 시간을 소모하는 것을 확인했다.

범인 검거

| Operation | Example | Complexity Class | Notes | | — | — | — | —| |Pop | l.pop() | O(1) | same as l.pop(-1), popping at end | Pop | l.pop(i) | O(N)| O(N-i): l.pop(0):O(N) (see above)|

우리는 pop 실제 pop()는 o(1)로 동작하지만 실제 내부는 어떻게 동작하는지 확인하지 않았지만, 파라미터의 유무가 pop의 동작 시간에 차이를 발생시킨다.

결론

사실 while문을 탓할 건 아니였다. pop(0)에 대한

만약 파이썬으로 알고리즘을 푸는 사람이라면 본인이 자주 사용하는 오퍼레이션에 대해서 시간복잡도를 숙지해놓을 필요가 있을 것 같다. 다음은 UC 어바인에서 정리한 파이썬 오퍼레이션 시간 복잡도에 대한 글이다. 참고해보고 필자와 같은 실수를 하지 않았으면 좋겠다.