드라이빙 인사이트

파이썬을 이용해서 알고리즘 문제를 풀다보면 언어 자체에서 지원하는 내장 메소드들을 사용하는 경우가 대부분이다. 이 때, 각 메소드들의 시간 복잡도를 정확하게 알고 사용해야 제대로된 알고리즘을 작성할 수 있다. 따라서 파이썬의 기본 타입들이 제공하는 메소드들과 그것들의 시간 복잡도를 정리하는 시간이 필요하다고 생각했다. 우선 변수 할당(바인딩, Binding)의 시간 복잡도는 O(1)이다. 즉, 'a = 1'이라는 할당문은 O(1)라는 시간복잡도를 갖는다. 여기에 산술연산, 값에 대한 비교 연산들 역시 모두 O(1)의 시간복잡도를 갖는다. list 타입의 메소드와 Big-O 리스트 타입의 내장 메소드들의 리스트와 그것들의 시간 복잡도에 대해서 알아보겠다. 소문자 L은 리스트 객체를 나타냈고 대문자 N은 리..