파이썬 슬라이싱이 O(N)인 이유 — 교과서랑 현실이 다른 이유 있었어요
코딩테스트 풀다가 이런 경험 한 번쯤 있지 않으세요?
분명히 이론상 시간복잡도가 O(N×length)인데, 슬라이싱 쓴 코드가 통과되는 거예요. 저도 처음엔 “그냥 테스트 케이스가 약한 건가?” 하고 넘겼어요. 근데 계속 그러니까 이건 아무래도 이유가 있겠다 싶어서 파봤거든요.
결론부터 말씀드리면, 파이썬 슬라이싱은 하드웨어 수준의 초고속 복사 덕분에 이론보다 훨씬 빠르게 작동해요. 그래서 코딩테스트 현장에서도 O(N)으로 쳐주는 게 맞아요. 오늘은 그 이유를 비전공자도 이해할 수 있게 풀어볼게요.
슬라이싱이 뭔지 잠깐 짚고 가요
python
arr = [1, 2, 3, 4, 5]
result = arr[1:4] # [2, 3, 4]
이게 슬라이싱이에요. 리스트나 문자열에서 원하는 구간을 잘라서 새로운 복사본을 만드는 거예요.
여기서 포인트가 “새로운 복사본”이에요. 원본에서 값을 읽어서 새 메모리에 담아요. 그러니까 당연히 잘라내는 길이(length)만큼 작업이 발생하죠.
이론적으로 보면, N개의 요소가 있는 배열에 슬라이싱을 N번 한다면 O(N×length)가 맞아요. 교과서에도 그렇게 나와 있고요.
슬라이싱은 복사본을 만드는 작업 — 여기까지는 이론이에요.
그러면 왜 실제로는 O(N)처럼 느껴지냐고요
여기서 파이썬의 정체를 알아야 해요.
파이썬은 사실 C언어로 만들어진 언어예요. 우리가 arr[1:4]라고 쓰면, 파이썬 인터프리터가 내부적으로 C언어 코드를 실행시켜요. 그 C언어 안에 memcpy라는 함수가 있어요.
memcpy를 쉽게 설명하면 “메모리 초고속 복사기”예요.
우리가 일반 복사기로 100장 복사할 때 한 장씩 누르는 것처럼, 단순 반복으로 요소를 하나씩 옮기면 느려요. 근데 memcpy는 달라요. CPU가 제공하는 메모리 블록 전송 명령어를 써서, 데이터를 한꺼번에 통째로 옮겨버려요. 마치 복사기 한 번 누르면 100장이 동시에 나오는 것처럼요.
파이썬 슬라이싱 = 내부에서 C언어 memcpy 실행 = 하드웨어가 직접 메모리를 통째로 복사
이론이랑 현실이 왜 다른 건지 이해가 안 될 수 있어요
조금 더 구체적으로 설명해볼게요.
알고리즘 시간복잡도를 계산할 때, 우리는 “연산 한 번 = 단위 시간 1″이라고 가정해요. 요소 하나 복사하면 1, 두 개 복사하면 2, 이런 식으로요. 이게 교과서 이론이에요.
근데 실제 컴퓨터는 달라요. CPU에는 SIMD(단일 명령 다중 데이터)라는 기능이 있어요. 이게 뭐냐면, 명령어 하나로 데이터 여러 개를 동시에 처리할 수 있는 거예요. memcpy는 바로 이 기능을 써요.
예를 들어 100개 짜리 배열을 복사할 때, 이론상 100번의 연산이 필요해요. 근데 SIMD를 쓰면 실제 하드웨어 명령은 훨씬 적게 실행돼요. 8개씩 묶어서 처리하면 약 13번이면 끝나거든요.
이론은 연산 횟수를 세고, 현실은 하드웨어가 실제로 걸리는 시간을 재요. 이 둘 사이의 간격이 바로 “왜 이론이랑 실제가 다르냐”의 답이에요.
교과서 이론 = 연산 횟수 기준 / 현실 = 하드웨어 최적화 기준 — 둘은 다른 이야기예요.
그래서 코딩테스트에선 어떻게 보는 게 맞아요?
코딩테스트에서는 파이썬 슬라이싱을 O(k)로 쳐요. 여기서 k는 잘라낸 길이예요.
예를 들어 길이 N짜리 배열에서 전체를 슬라이싱하면 arr[:]는 O(N)이에요. 절반을 자르면 O(N/2), 즉 O(N)이고요. 고정된 짧은 구간을 자르면 O(1)처럼 취급하기도 해요.
이게 왜 중요하냐면, 슬라이싱을 루프 안에 쓸 때예요.
# 이 코드의 시간복잡도는?
for i in range(N):
sub = arr[i:i+k] # 매번 길이 k만큼 슬라이싱
이론상 O(N×k)예요. 근데 k가 상수라면 O(N)으로 봐도 돼요. 실제로 memcpy가 k개를 그냥 쭉 밀어버리기 때문에, k가 작은 상수라면 상수 시간에 가깝거든요.
반대로 k가 N에 비례해서 커지는 상황이라면 이야기가 달라져요. 그때는 O(N²)에 가까워지고, 실제로도 느려져요.
슬라이싱은 O(k) — k가 상수면 O(1), k가 N이면 O(N)으로 계산하면 돼요.
비전공자 입장에서 직관적으로 이해하는 법
저도 처음에 “메모리 복사가 빠르다는 게 대체 무슨 말이야?” 싶었어요.
이렇게 생각해봤어요. 엑셀 파일에서 셀 100개를 복사할 때, 한 칸씩 Ctrl+C, Ctrl+V 100번 하는 것과 한 번에 드래그해서 복사하는 것 중 뭐가 빠를까요? 당연히 후자죠.
memcpy가 바로 그 “한 번에 드래그 복사”예요. 컴퓨터 메모리는 주소가 연속된 공간이에요. 파이썬 리스트나 문자열도 메모리에 연속으로 저장돼 있어요. 그래서 memcpy가 시작 주소에서 끝 주소까지 한 번의 블록 전송으로 처리할 수 있는 거예요.
이게 한 칸씩 옮기는 것보다 얼마나 빠르냐면, 캐시 히트율도 높고 CPU 파이프라인도 최적화되어 있어서 이론상 횟수 대비 몇 배에서 수십 배까지 차이 날 수 있어요.
직관: 한 칸씩 옮기기 vs 한 번에 블록 통째로 이동 — memcpy는 후자예요.
정리하면
오늘 이야기를 한 번에 정리해볼게요.
- 파이썬 슬라이싱은 내부적으로 C언어의
memcpy로 실행돼요 memcpy는 CPU의 하드웨어 최적화를 써서 메모리를 통째로 빠르게 복사해요- 이론(교과서)은 연산 횟수를 세고, 현실은 실제 하드웨어 실행 시간을 재요
- 그래서 이론상 O(N×length)지만, 실제로는 O(length), 즉 길이에만 비례하는 것처럼 작동해요
- 코딩테스트에서는 이 현실을 반영해서 슬라이싱을 O(k)로 쳐줘요
솔직히 저도 코딩테스트 문제 틀리고 나서야 이걸 파봤어요. 통과되는 게 신기해서 그냥 넘길 수도 있었는데, 이렇게 파고들면 파이썬이 왜 느리다고 알려진 언어인데 은근히 잘 버티는지도 이해가 되더라고요.
C언어로 만든 인터프리터 위에서 돌아가는 게 파이썬이라는 거, 이 한 가지만 기억해도 앞으로 “왜 이게 이렇게 작동하지?”를 만났을 때 실마리가 될 거예요.