개념 확인: Dynamic Arrays

문제 1과 3의 동적 배열은 원소 수 n이 용량(capacity)과 같을 때 추가하려 하면 용량을 max(1, 2n)으로 늘리고, 삭제 뒤 capacity ≥ 3n이면 용량을 max(1, 2n)으로 줄인다.

용량 1인 빈 동적 배열의 끝에 원소 9개를 차례로 추가한다.

1. 재할당이 일어나는 추가가 몇 번째 호출인지, 그때 복사하는 원소 수와 새 용량을 모두 적는다.
2. 9번 추가한 뒤의 용량과 원소 수를 적는다.
3. 이어서 끝에서 원소를 하나씩 삭제할 때, 처음으로 용량이 줄어드는 삭제가 몇 번째인지와 줄어든 용량을 적는다.
4. 줄인 뒤에도 빈 칸을 남겨 두는 이유를 적는다.

전략 B에는 문제 1의 용량 증가 규칙을 쓰고, 전략 A에는 아래의 별도 증가 규칙을 쓴다.

용량 1인 빈 배열에 원소 12개를 추가한다. 늘릴 때마다 용량에 3을 더하는 전략 A와 용량을 두 배로 만드는 전략 B를 비교한다.

1. 전략 A와 B 각각의 재할당 뒤 용량을 순서대로 적는다.
2. 두 전략의 누적 복사 원소 수를 구한다.
3. 추가 횟수 m이 커질 때 두 전략의 총 복사량이 각각 어떻게 증가하는지 적고, A에서 늘리는 폭을 크게 잡아도 결론이 바뀌지 않는 이유를 설명한다.

문제 1의 동적 배열을 쓴다.

추가 한 번의 비용을 쓰기 1회와 그 호출에서 복사한 원소 수의 합으로 센다.

1. 문제 1의 9번 추가에서 총비용과 한 번당 비용을 구한다.
2. 추가 횟수 m에 관계없이 한 번당 상각 비용이 3보다 작은 이유를 적는다.
3. 다음 문장이 맞는지 판단하고 고친다. “상각 비용은 입력이 고르게 들어온다고 가정하고 구한 평균 경우의 비용이다.”
4. 끝에 추가하는 연산을 최악의 경우 Θ(n)만으로 설명하면 부족한 이유를 적는다.

한 컴퓨터에서 빈 목록에 append를 반복하며 sys.getsizeof를 기록했더니 원소 수 5~8에서 모두 120, 9~16에서 모두 184였다. 같은 컴퓨터에서 원소 200,000개를 append로 만드는 전체 시간은 9.6 ms였다.

1. 원소 수가 5에서 8로 늘 동안 메모리 크기가 그대로인 구간은 무엇을 뜻하는지 적는다.
2. append 한 번당 시간을 나노초(ns)로 구한다.
3. 이 두 측정만으로 CPython의 증가 배수가 정확히 두 배라고 단정할 수 없는 이유를 적는다.
4. insert(0, x)를 같은 횟수만큼 반복하면 append와 달리 비용이 어떻게 되는지 적는다.

용량 8인 원형 배열에서 첫 원소의 칸이 j = 6, 원소 수가 n = 4다. i번째 원소는 a[(j + i) mod 8]에 있다. 3과 4는 처음 상태에서 각각 따로 생각한다.

1. 네 원소가 들어 있는 실제 칸 번호를 순서대로 적는다.
2. get(2)가 읽는 실제 칸을 적는다.
3. 끝에 원소를 하나 추가하면 새 원소가 들어가는 실제 칸을 적는다.
4. 앞에서 원소를 하나 삭제하면 원소를 옮기는지 적고, 삭제 뒤의 j와 n을 적는다.
5. 원소 수가 용량 8에 도달해 재할당하면 새 배열에서 첫 원소의 칸과 j가 어떻게 되는지 적는다.