리스트는 구조상 메모리에 연속적으로 배치된 값입니다. 컴퓨터의 메모리는 마치 숫자가 적힐 수 있는 칸이 일렬로 쭉 나열되어 있는 형태라고 보시면 되는데, 리스트는 이중 일부 연속된 구간을 차지하고 있다고 보시면 되는 겁니다.
이러한 리스트의 중간에 원소를 삽입한다고 생각해봅시다. 리스트는 메모리상에서 연속된 곳에 위치해야 하기 때문에, 특정 위치에 원소를 삽입하려면 그 뒤에 원소를 일일이 한 칸씩 뒤로 옮긴 다음에 그 위치에 원소를 삽입하게 됩니다.
따라서 리스트의 원소의 개수가 N개일 때, 리스트의 insert 메서드(함수)는 시간복잡도가 최악의 경우 O(N)입니다. 평균도 O(N)이므로 그냥 O(N)이라고 알고 계시면 됩니다.
제시하신 코드에서 op 리스트는 루프를 돌 때마다 원소가 1~3개 늘어나므로 리스트의 길이가 대략 O(i)입니다. 각 루프마다 이 리스트에 insert 메서드를 최소 1~3회 시행하므로, 전체 루프의 시간복잡도는 O(N^2)입니다. N이 최대 10^6이기 때문에 제곱하면 10^12로, 시간 제한 안에 절대 해결할 수 없는 계산 시간입니다. 그래서 시간초과가 발생하는 겁니다.
기타 파이썬 자료형 메서드의 시간복잡도는 https://wiki.python.org/moin/T... 에서 확인하실 수 있습니다. Amortized worst case가 최악의 경우 나오는 평균 시간복잡도라고 보시면 됩니다.
hio 2년 전
아래 코드로 제출했더니 바로 시간초과가 뜨더라구요. 퍼센테이지도 안떴습니다.
디버그 해보니 for 문 돌 때마다 insert가 되어서 op[]에서 불필요하게 메모리를 많이 사용하더라구요.
그래서 주석처럼 수정해보니 맞았습니다가 나왔습니다.
시간초과가 뜨는 이유를 제가 유추해본 바로는 op[]에서 insert를 사용함으로써 불필요하게 메모리를 사용해서인 것 같더라구요.
그럼 시간초과가 아니라 메모리 초과가 나와야 하는 거 아닌가요??
(혹시 insert()를 사용하는 거랑 인덱스로 접근하는 거랑도 시간 차이가 있을까 해서 해봤는데 둘 다 맞았습니다 나왔어요..)
시간 초과가 뜬 이유가 뭔지 궁금합니다. 알아내려고 조금씩 수정해가면서 계속 해봤는데도 도저히 감이 안잡히네요ㅠㅠ 도와주세요ㅠㅠ