개념 확인: Arrays

한 칸이 8바이트인 배열의 첫 칸 주소가 3000이다. 주소는 addr(i) = base + i × size로 계산한다.

1. 인덱스 7인 칸의 주소를 구한다.
2. 주소가 3096인 칸의 인덱스를 구하고, 이 칸이 1부터 세면 몇 번째 칸인지 적는다.
3. 원소가 1,000개일 때와 1,000,000개일 때 인덱스로 주소를 구하는 계산량이 달라지는지 적는다.
4. Python list에 정수, 문자열, 목록을 섞어 담아도 이 주소 계산이 성립하는 이유를 적는다.

a = ["p", "y", "t", "h", "o", "n"]

1. a[5], a[-2], a[6], a[-7]의 결과를 각각 적는다.
2. 같은 원소를 담은 List 인터페이스의 get(i)에서 허용되는 i의 범위를 적는다.
3. get(-2)가 Python list의 a[-2]와 다르게 처리되는 이유를 적는다.

ArrayStack의 내부 배열 a가 [d, o, g, s, -, -]이고 원소 수가 n = 4다. -는 비어 있는 칸이다.

1. a.length를 적는다.
2. get(3)의 반환값을 적는다.
3. set(1, t)의 반환값과 호출 뒤 내부 배열을 적는다.
4. 내부 배열에 칸이 6개인데도 get(4)를 허용하지 않는 이유를 적는다.

원소 6개가 담긴 ArrayStack에 다음 연산을 차례로 실행한다. 용량은 충분해 내부 배열의 칸 수(a.length)는 바뀌지 않는다.

add(2, x) → add(7, y) → remove(3) → remove(6)

1. 각 호출 직전의 n과 옮긴 원소 수를 적는다.
2. 네 호출에서 옮긴 원소 수의 합을 구한다.
3. 3과 4는 원소 네 개가 든 [k, l, m, p, -, -]에서 각각 따로 시작한다. add(2, x)를 하며 a[3] = a[2]부터 실행하면 한 번 뒤 배열과 잃는 원소는 무엇인가? 올바른 복사 방향도 적는다.
4. 3의 원래 배열에서 remove(1)을 하며 a[2] = a[3]부터 실행하면 한 번 뒤 배열과 잃는 원소는 무엇인가? 올바른 복사 방향도 적는다.

1. 다음 요구마다 자주 부르는 연산과 배열에서의 비용을 적고 배열이 적합한지 판단한다. (가) 학번 순서로 저장한 점수를 번호로 조회한다. (나) 센서 측정값을 받은 순서대로 끝에 계속 붙인다. (다) 새 요청을 대기 목록의 맨 앞에 자주 끼워 넣는다.
2. add(i, x)의 최선·평균·최악의 경우가 어떤 삽입 위치이고 비용이 얼마인지 적는다.
3. 원소 30,000개를 한 칸씩 미는 데 반복문은 1.20 ms, 슬라이스 대입은 0.25 ms가 걸렸다. 두 방법이 모두 Θ(n)인데 시간이 약 4.8배 다른 이유를 적는다.