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

Data Abstraction

Data Abstraction and ADTs

연산의 반환값과 상태 변화를 추적하고 요구사항에 맞는 ADT를 고른다.

문제 1

같은 값, 다른 삭제 의미

빈 스택과 빈 큐에 차례로 red, blue, green을 추가했다. 스택에서는 push, 큐에서는 enqueue를 사용했다.

  1. 스택에서 pop()이 반환할 값과 호출 뒤 상태를 적는다.
  2. 큐에서 dequeue()가 반환할 값과 호출 뒤 상태를 적는다.
  3. 두 구조에 저장된 값과 추가 순서가 같아도 서로 다른 ADT인 이유를 설명한다.
해설 펼치기
  1. 가장 나중에 추가한 green을 반환하고 상태는 [red, blue]가 된다.
  2. 가장 먼저 추가한 red를 반환하고 상태는 [blue, green]이 된다.
  3. ADT는 저장된 값만으로 정해지지 않는다. 어떤 연산을 허용하고 그 연산이 무엇을 반환하며 상태를 어떻게 바꾸는지가 다르므로 서로 다른 ADT다.
문제 2

덱의 양쪽 끝 추적

빈 덱에 다음 연산을 순서대로 적용한다.

add_last(b)
add_first(a)
add_last(c)
remove_last()
add_first(z)
remove_first()
  1. 각 삭제 연산의 반환값을 순서대로 적는다.
  2. 모든 연산 뒤 남은 덱의 상태를 앞쪽부터 적는다.
  3. 덱으로 스택과 같은 삭제 순서를 만들려면 추가와 삭제에 어느 끝을 쓰는지 적는다.
해설 펼치기
  1. 처음 세 연산 뒤 상태는 [a, b, c]다. remove_last()는 c를 반환해 [a, b]가 되고, add_first(z)로 [z, a, b]가 된 뒤 remove_first()는 z를 반환한다. 반환값은 차례로 c, z다.
  2. [a, b]다.
  3. 같은 끝에서 추가하고 삭제한다. 서로 다른 끝을 쓰면 큐와 같은 순서가 된다.
문제 3

불완전한 명세 고치기

누군가 큐 연산을 다음과 같이 적었다.

dequeue(): 원소를 꺼낸다.

이 문장만으로는 호출 결과를 정확히 판단할 수 없다. ADT 명세에 필요한 요소 가운데 이 설명에 빠졌거나 불분명한 것을 세 가지 이상 찾고, 각각 어떤 내용을 정해야 하는지 적는다.

해설 펼치기
  • 입력: dequeue()는 별도의 입력을 받지 않는다고 명시한다.
  • 반환값: 가장 먼저 추가된 원소를 반환한다고 정한다.
  • 적용 조건: 큐가 비어 있지 않을 때만 호출할 수 있는지 정한다.
  • 상태 변화: 반환한 원소가 큐에서 삭제되고 나머지의 순서는 유지된다고 정한다.

‘꺼낸다’만으로는 어느 원소인지, 반환하는지, 빈 상태에서 가능한지, 호출 뒤 무엇이 남는지 알 수 없다. 구현 코드가 아니라 호출에서 관찰 가능한 의미를 명세한다.

문제 4

조회, 변경, 적용 조건

스택의 현재 상태가 ["pen", 12]이고 오른쪽이 맨 위다. 각 호출은 이 상태에서 따로 시작한다.

  1. peek(), pop(), size()의 반환값과 호출 뒤 상태를 각각 적는다.
  2. 세 연산을 조회와 상태 변경으로 나눈다.
  3. pop()을 두 번 호출한 뒤 is_empty()와 pop()을 차례로 호출할 때 각각 명세에서 무엇을 확인해야 하는지 적는다.
해설 펼치기
  1. peek()은 12를 반환하고 상태 ["pen", 12]를 유지한다. pop()도 12를 반환하지만 호출 뒤 상태는 ["pen"]이다. size()는 2를 반환하고 상태를 유지한다.
  2. peek()과 size()는 조회, pop()은 상태 변경이다. 같은 반환값을 내도 호출 뒤 상태가 다르면 다른 연산이다.
  3. 두 번의 pop() 뒤 스택은 비어 있다. is_empty()는 True를 반환하고 상태를 유지한다. 빈 스택의 pop()은 적용 조건을 만족하지 않으므로 호출이 허용되는지를 명세에서 확인해야 한다. 어떤 오류를 내는지 같은 구체적 처리는 구현이 정할 수 있다.
문제 5

요구 연산에서 ADT 고르기

각 요구사항에 가장 직접적으로 맞는 ADT를 스택, 큐, 덱, 우선순위 큐, 리스트, USet, SSet 가운데 고르고, 결정에 사용한 연산 또는 삭제 기준을 적는다.

  1. 문서 편집기에서 가장 최근에 한 편집 하나를 취소한다.
  2. 고객센터에 접수된 문의를 접수 순서대로 처리한다.
  3. 도서관 회원 번호가 등록되어 있는지만 확인한다. 위치나 순서는 필요 없다.
  4. 예약 시각 목록에서 14:00 이후(14:00 포함) 첫 예약 시각을 찾는다.
  5. 재생 목록의 앞과 뒤 양쪽에서 곡을 추가하거나 뺀다.
  6. 수리 요청마다 긴급도(1이 가장 긴급)가 있고, 접수 순서와 관계없이 가장 긴급한 요청부터 처리한다.

마지막으로 6의 요청이 ‘일반 수리(긴급도 3)’, ‘누수(긴급도 1)’, ‘전등 교체(긴급도 2)’ 순서로 접수되었을 때 처리 순서를 적는다.

해설 펼치기
  1. 스택: 가장 최근에 추가한 항목을 pop()으로 먼저 삭제한다.
  2. 큐: 가장 먼저 접수한 항목을 dequeue()로 먼저 삭제한다.
  3. USet: find(x)가 같은 값이 있으면 그 값을, 없으면 None을 돌려주므로 등록 여부를 확인할 수 있다.
  4. SSet: find(14:00)이 14:00 이상인 가장 작은 값을, 없으면 None을 돌려준다.
  5. 덱: 앞과 뒤 모두에서 추가와 삭제 연산을 제공한다.
  6. 우선순위 큐: remove()가 우선순위가 가장 높은 원소를 삭제한다.

처리 순서는 누수, 전등 교체, 일반 수리다. 접수 순서가 아니라 우선순위가 삭제 순서를 정한다. 선택의 근거는 이름이나 익숙한 구현이 아니라 관찰해야 하는 연산이며, 이 단계에서는 구현 속도를 근거로 쓰지 않는다.