yeolyi.com성열의 컴퓨터공학

줄 맨 앞에 끼어들기

배열

할 일 1,000개를 이어진 주소에 담아 두었다고 합시다. 이렇게 담으면 무엇이 빠르고 무엇이 느릴까요?

배열

배열 인덱스 글에서 본 C의 배열처럼, 값을 빈틈없이 차례로 놓는 방식을 자료구조에서도 배열(array)이라 합니다. 파이썬의 리스트도 내부적으로는 배열로 구현되어 있습니다.

시작 주소가 100이면 인덱스 3의 값은 103번 주소에 있습니다. 메모리는 주소만 알면 어느 칸이든 곧바로 읽으니, 인덱스 1000의 값도 덧셈 한 번으로 찾아갑니다.

끼워 넣기

대신 끼워 넣을 때는 그 뒤의 값을 한 칸씩 밀어야 합니다.

10203040

맨 앞에 5를 넣습니다.

파이썬 리스트의 insert(0, x)도 내부적으로 이렇게 값을 모두 한 칸씩 밉니다. 값 10만 개를 하나씩 다 읽는 일과 맨 앞에 1,000번 넣는 일을 해 봅시다.

하나씩 다 읽기
1a = [0] * 100_000
2for i in range(len(a)):
3 x = a[i]

실행을 눌러 봅시다.

맨 앞에 넣기
1a = [0] * 100_000
2for _ in range(1000):
3 a.insert(0, 0)

실행을 눌러 봅시다.

10만 번을 읽어도 금방 끝나지만, 맨 앞에 넣기는 1,000번에도 오래 걸립니다. 넣을 때마다 값 10만 개를 밀기 때문입니다. 빼낼 때도 그 뒤의 값을 한 칸씩 당겨야 하니 마찬가지입니다.

도전 문제

빈 배열에 값 10개를 하나씩 넣습니다. 넣을 때마다 그때 값이 n개라면 인덱스 n // 2 자리, 곧 가운데에 넣어서 그 뒤의 값을 한 칸씩 밉니다. 10개를 다 넣을 때까지 값을 모두 몇 번 옮길까요? 숫자로 답하세요.