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

Interfaces

Interfaces and Implementations

클라이언트가 보는 연산 의미와 구현이 수행하는 내부 작업을 분리한다.

문제 1

공개 계약과 내부 결정

배열로 리스트를 구현한 설명에 다음 문장이 있다. 각 문장을 ‘인터페이스·명세가 정하는 내용’과 ‘구현이 정하는 내용’으로 나누고 이유를 적는다.

  1. get(i)는 위치 i의 값을 반환하고 리스트를 바꾸지 않는다.
  2. 원소는 연속된 배열 칸에 저장한다.
  3. remove(i) 호출 뒤 기존 위치 i보다 뒤에 있던 원소의 인덱스가 하나씩 작아진다.
  4. 삭제할 때 배열 원소를 앞에서부터 왼쪽으로 당긴다.
해설 펼치기

1과 3은 인터페이스·명세가 정한다. 반환값과 상태 변화, 원소의 논리적 위치는 클라이언트가 호출 결과로 관찰한다.

2와 4는 구현이 정한다. 연속 배열을 쓸지, 칸을 어떤 순서로 옮길지는 같은 연산 의미를 실현하기 위한 내부 표현과 작업이다. 인터페이스는 결과를 정하지만 그 결과를 만드는 저장 방식까지 고정하지 않는다.

문제 2

리스트 연산과 인덱스

초기 리스트가 [p, q, r, s]일 때 다음 연산을 순서대로 적용한다.

get(2)
set(0, x)
add(2, y)
remove(3)
  1. 각 연산의 반환값과 호출 뒤 상태를 적는다.
  2. 초기 상태에서 add(4, z)와 get(4) 가운데 허용되는 호출을 고르고, 인덱스 범위로 설명한다.
해설 펼치기
연산반환값호출 뒤 상태
get(2)r[p, q, r, s]
set(0, x)p[x, q, r, s]
add(2, y)없음[x, q, y, r, s]
remove(3)r[x, q, y, s]

초기 원소 수는 n = 4다. 삽입은 0 ≤ i ≤ n이므로 add(4, z)는 끝에 추가하는 호출로 허용된다. 조회는 0 ≤ i < n이므로 get(4)는 허용되지 않는다. set은 바꾸기 전의 값을 반환한다.

문제 3

배열 이동의 오류 찾기

칸이 6개인 배열이 a b c d e _ (원소 5개)이다. 위치 2에 x를 넣으려고, 한 구현이 위치 3부터 오른쪽으로 진행하며 a[3] = a[2], a[4] = a[3], a[5] = a[4]를 실행한 뒤 a[2] = x를 실행했다.

  1. 각 대입 뒤의 배열을 적고, 최종 결과에서 사라진 값을 적는다.
  2. 원래 값을 보존하려면 대입을 어떤 순서로 실행해야 하는지 적고 올바른 결과를 적는다.
  3. 올바른 결과에서 위치 1의 값을 삭제할 때, 반환할 값을 언제 보관하고 원소를 어느 방향으로 옮기는지 적는다.
해설 펼치기
  1. a b c c e _ → a b c c c _ → a b c c c c → a b x c c c다. 앞선 대입이 아직 복사하지 않은 값을 덮어써 d와 e가 사라졌다.
  2. 뒤에서부터 a[5] = a[4], a[4] = a[3], a[3] = a[2]를 실행한 뒤 a[2] = x를 넣는다. 결과는 a b x c d e다.
  3. 이동 전에 a[1]의 b를 별도 변수에 보관한다. 그 뒤 오른쪽 원소를 왼쪽으로 한 칸씩 차례로 당겨 빈 칸을 메우면 a x c d e _가 되고 보관한 b를 반환한다.
문제 4

객체, 별칭, self

다음 Python 코드를 실행한다.

a = [1, 2]
b = a
b.append(3)
c = list(a)
b = [1, 2, 3]
  1. 실행 뒤 a, b, c의 값을 적고 a is b, a == b, a is c, a == c의 결과를 적는다.
  2. 이어서 c.append(4)를 실행하면 a가 바뀌는지 적고 이유를 적는다.
  3. b.append(3)과 마지막 b = [1, 2, 3]이 객체 관계에 준 차이를 적는다.
  4. 다음 코드를 실행한 뒤 p.value, q.value, r.value와 r is p를 적고, self가 무엇을 가리키는지 설명한다.
class Counter:
    def __init__(self):
        self.value = 0
    def up(self):
        self.value += 1

p = Counter()
q = Counter()
r = p
p.up()
r.up()
q.up()
해설 펼치기
  1. a, b, c 모두 [1, 2, 3]이다. a is b는 False, a == b는 True, a is c는 False, a == c는 True다.
  2. 바뀌지 않는다. list(a)는 새 리스트 객체를 만들었으므로 c의 변경은 a에 보이지 않는다.
  3. append는 a와 b가 공유하던 객체를 변경해 a에서도 보였다. 마지막 재대입에서는 b만 새 리스트를 가리키게 됐다. is는 같은 객체인지, ==는 값이 같은지를 묻는다.
  4. p.value = 2, q.value = 1, r.value = 2, r is p는 True다. self는 메서드가 호출된 인스턴스 객체를 가리키므로 p.up()과 r.up()은 같은 객체를, q.up()은 다른 객체의 상태를 바꾼다.
문제 5

다른 내부 순서, 같은 스택

두 스택 구현이 있다. EndStack은 리스트 뒤쪽을, FrontStack은 리스트 앞쪽을 맨 위로 사용한다. 빈 스택에 다음 연산을 차례로 호출한다.

push(1)
push(2)
pop()
push(3)
  1. 각 호출 뒤 두 구현의 내부 리스트와 pop()의 반환값을 적는다.
  2. 이어서 pop()을 두 번 더 호출할 때 두 구현의 반환값을 적는다.
  3. 내부 리스트의 순서가 다른데도 같은 스택 인터페이스를 만족한다고 말할 수 있는 이유와, assert 하나로 이를 모두 보장하지 못하는 이유를 적는다.
해설 펼치기
호출EndStack 내부FrontStack 내부
push(1)[1][1]
push(2)[1, 2][2, 1]
pop()[1], 반환값 2[1], 반환값 2
push(3)[1, 3][3, 1]
  1. 위 표와 같다.
  2. 두 구현 모두 3, 1을 차례로 반환한다.
  3. 클라이언트는 push와 pop의 반환값과 상태 변화를 관찰한다. 어느 끝을 맨 위로 쓸지는 구현의 결정이며, 같은 호출에 같은 관찰 결과를 내면 같은 인터페이스를 만족한다. assert 하나는 한 호출 열만 확인하므로, 모든 호출 열에서 명세와 같은 결과를 내야 한다는 점까지 보장하지는 못한다.