부산대학교자료구조
Scientific Inference Lab

Same List, Different Costs

Arrays and Linked Lists

같은 List 연산이 내부 표현에 따라 하는 일과 비용을 비교한다.

문제 1

get(i)의 내부 작업

원소가 n = 12개인 ArrayStack, SLList, DLList에서 같은 호출을 실행한다.

  1. get(8)을 실행할 때 세 표현이 각각 하는 일과 이동 횟수를 적는다. DLList는 가까운 끝을 고른다.
  2. get(2)에서 SLList와 DLList의 이동 횟수를 적는다.
  3. 세 표현에서 원소 12개를 처음부터 끝까지 훑는 비용을 적고, 임의 접근의 차이가 이 비용을 바꾸지 않는 이유를 적는다.
해설 펼치기
  1. ArrayStack은 시작 주소에서 여덟 칸 떨어진 위치를 계산 1회로 구한다. SLList는 head에서 next를 8회 따라간다. DLList는 8 ≥ 12/2라 뒤쪽 센티널에서 prev를 12 − 8 = 4회 따라간다.
  2. 둘 다 앞에서 출발해 2회다.
  3. 세 표현 모두 모든 원소를 한 번씩 방문해 Θ(n)이다. 순회는 다음 원소로 한 걸음씩 가므로 한 위치에 바로 닿는 능력이 필요 없다.
문제 2

삽입과 삭제를 둘로 나누기

원소가 n = 10개이고 용량이 충분한 배열과 SLList가 있다. 각 호출은 처음 상태에서 따로 실행한다.

  1. add(0, x), add(5, x), remove(9)에서 배열이 옮기는 원소 수를 적는다.
  2. 같은 세 호출에서 SLList가 위치를 찾으려 순회하는 비용을 Θ 표기로 적는다.
  3. 각 표현에서 삽입 비용을 지배하는 작업을 한 문장으로 적는다.
  4. SLList에서 삭제할 노드의 참조를 알더라도 인덱스로 받은 삭제에 순회 비용이 남는 이유를 적는다.
해설 펼치기
  1. add(0, x)는 n − i = 10개, add(5, x)는 5개, remove(9)는 n − i − 1 = 0개다.
  2. add(0, x)는 Θ(1), add(5, x)는 Θ(i + 1), remove(9)는 Θ(i + 1)이다.
  3. 배열은 자리를 만들려고 원소를 옮기는 일이, 연결리스트는 위치를 찾는 순회가 비용을 지배한다.
  4. SLList는 삭제할 노드가 아니라 그 앞 노드의 next를 바꾸므로, 인덱스로 받았다면 앞 노드를 찾는 순회가 필요하다.
문제 3

배열 끝 삽입의 두 경우

  1. 용량 8인 배열에 원소가 5개일 때 add(5, x)의 비용을 적는다.
  2. 용량 8인 배열에 원소가 8개일 때 add(8, x)의 비용과 그 이유를 적는다.
  3. 끝 삽입을 연속으로 할 때 ‘상각 Θ(1)’이 뜻하는 것과 뜻하지 않는 것을 적는다.
  4. 원소가 이미 담긴 DLList에서 노드 참조를 가진 채 그 앞에 삽입하는 비용을 적는다.
해설 펼치기
  1. 용량에 여유가 있어 마지막 칸에 저장하므로 Θ(1)이다.
  2. 용량이 부족해 더 큰 배열로 재할당하고 원소 8개를 복사하므로 Θ(n)이다.
  3. 연속한 끝 삽입의 총비용을 나누면 한 번당 상수라는 뜻이다. 매번 Θ(1)이라는 뜻은 아니며, 재할당하는 호출은 Θ(n)이다.
  4. 위치를 다시 찾지 않고 참조만 바꾸므로 Θ(1)이다.
문제 4

공간은 어디에 드는가

원소 9개를 저장한다.

  1. 용량 16인 ArrayStack에서 사용하지 않는 칸 수를 적는다.
  2. SLList와 DLList가 값 이외에 저장하는 참조의 수를 각각 적는다.
  3. 배열과 연결리스트의 추가 공간이 생기는 곳을 한 문장씩 적는다.
해설 펼치기
  1. 16 − 9 = 7칸이다.
  2. SLList는 노드마다 next 1개로 9개, DLList는 prev와 next 2개로 18개다.
  3. 배열은 사용하지 않는 용량에서, 연결리스트는 노드마다 저장하는 참조에서 추가 공간이 생긴다. 연결리스트에는 남는 칸이 없다.
문제 5

자주 쓰는 연산으로 고르기

임의 접근 한 번의 비용을 배열 1, SLList n으로, 앞 삽입 한 번의 비용을 배열 n, SLList 1로 센다.

  1. 임의 접근 70회와 앞 삽입 30회를 할 때 두 표현의 비용식과 최고차항을 적고 더 알맞은 표현을 고른다.
  2. 임의 접근 20회와 앞 삽입 80회일 때 같은 방식으로 고른다.
  3. 값이 정렬된 목록에서 특정 값을 찾을 때 배열과 연결리스트의 차이를 적는다.
해설 펼치기
  1. 배열 70·1 + 30·n, 최고차항 30n. SLList 70·n + 30·1, 최고차항 70n. 최고차항이 작은 배열이 알맞다.
  2. 배열 20·1 + 80·n, 최고차항 80n. SLList 20·n + 80·1, 최고차항 20n. SLList가 알맞다.
  3. 정렬 배열은 가운데 칸을 바로 읽어 범위를 절반씩 좁힐 수 있지만, 정렬 연결리스트는 가운데로 바로 갈 수 없어 연결을 차례로 따라간다.

판정 기준: 같은 n에서도 연산별 호출 횟수가 바뀌면 선택이 달라진다.