쉽게 배우는 자료구조 문제풀이

중간고사 범위: 기본, 리스트, 스택, 큐, 트리, 해시테이블 chap2-3, 5-8, 10-12

토: 개념 전부 훑기 + chap2-3/5-8 문풀 일: chap10-12 문풀 + quiz + ppt 점검 + 전날못한것

Chapter 2

---

01 | 다음 수열의 n번째 항을 구하는 재귀 알고리즘을 작성하시오.

a_n = 5a_{n-1} + 3, a_1 = 0

Answer

func(n):
	if (n = 1) return 0
	else return 5 * func(n - 1) + 3

02 | 본문에서 소개한 다음 알고리즘에서 양의 정수 n에 대해 함수 seq()는 총 몇 회 호출되는가? 이때 최초의 호출 seq(n)도 포함하여 센다.

seq(n):
	if (n = 1) return 1
	else return seq(n - 1) + 3

Answer 각 k에 대해 seq(k)가 한 번씩 호출되는 것으로 recursion이 성립하기 때문에, 총 n회 호출된다.

03 | 다음 피보나치 수열을 구하는 재귀 알고리즘에서 5번째 피보나치 수를 구하는 fib(5)를 수행하면 함수 fib()는 총 몇 회 호출되는가? 이때 최초의 호출 fib(5)도 포함하여 센다. (이 문제는 fib()가 매우 불필요한 중복 호출이 심하다는 것을 느껴보려는 것이다.)

fib(n):
	if (n = 1 or n = 2) return 1
	else return fib(n - 1) + fib(n - 2)

Answer fib(n)은 fib(n - 1)과 fib(n - 2)를 호출하므로 fib(n)의 호출수를 $c_n$이라고 하면 $c_n=c_{n-1}+c_{n-2}+1$이 성립한다. 이때 1은 자기 자신을 호출하기 때문에 추가된다. $c_1=c_2=1$이므로 계산하면 $c_5=9$이고, 따라서 총 9회 호출된다.

04 | 다음 하노이 탑 재귀 알고리즘에 대해 5개의 원반을 옮기고자 move(5, a, b, c)를 수행하면 함수 move()는 총 몇 회 호출되는가? 이때 최초의 호출 move(5, a, b, c)도 포함하여 센다. 원반을 옮기는 횟수와 move()가 호출되는 횟수는 같지 않다. (03번 문제처럼 피해 갈 수 있는데도 재귀를 통해 중복 호출을 하는 예도 있다. 이번 문제는 피해 갈 수 없지만 호출이 지수함수적으로 증가하는 하노이 탑 문제의 호출 횟수를 느껴보려는 것이다.)

move(n, a, b, c):
	if (n > 0)
		move(n - 1, a, c, b)
		① a에 있는 원반을 b로 옮긴다
		move(n - 1, c, b, a)

Answer Symmetry에 의해 move(n - 1, a, b, c)와 move(n - 1, c, b, a)의 하위 호출 횟수는 같을 것이며, 나아가 n만 같다면 호출 횟수는 같아야 한다. 따라서 move(n, a, b, c)의 호출 횟수를 $c_n$이라고 하면 하위 단계에서 $2c_{n-1}$회의 호출을 하므로 $c_n=2c_{n-1}+1$이 성립한다. 또한, 경계조건은 아무런 호출도 하지 않는 $n=0$의 1회이다. 따라서 계산하면 63회의 호출을 한다.

05 | 04번 문제에서 함수 move()의 호출 함수 대신 ①의 원반을 옮기는 행위의 총 횟수를 세어보시오. 이 횟수와 move()의 호출 횟수는 어떤 관계가 있는지 생각해보시오.

Answer $c_n=2c_{n-1}+1$ 관계는 그대로이며, 첫 항이 0이고 두 번째 항이 1인 것이 04번 문항과 다르다. 따라서 ①의 호출 횟수는 move()의 호출 횟수를 한 단계 늦게 따라가게 되어 답은 31이다.

06 | 04번 문제에서 다음처럼 경계 조건이 빠진 채 알고리즘이 수행되면 어떻게 되는가?

move(n, a, b, c):
	move(n - 1, a, c, b)
	a에 있는 원반을 b로 옮긴다
	move(n - 1, c, b, a)

Answer 첫 recursion 단계에서부터 $n<0$구간까지 계속 진행되어 b와 c의 교환만이 일어나면서 n이 음의 무한대로 발산한다.

07 | [알고리즘 2-6]의 선택 정렬 알고리즘에서 임의의 양의 정수 n에 대해 selectionSort(A, n)을 수행하면 함수 selectionSort()는 총 몇 회 수행되는가? 이때 최초의 호출 selectionSort(A, n)도 포함하여 센다.

selectionSort(A[], n):
	if (n > 1)
		A[0...n-1] 중 가장 큰 수 A[k]를 찾는다.
		A[k] ↔ A[n-1]
		selectionSort(A, n-1)

Answer n=1일 때가 마지막 호출이며 n부터 1까지 순차적으로 호출되므로 총 n회 수행된다.

08 | 다음의 재귀적 표현에서 <T>는 무엇을 표현한 것인가?

<T> = <숫자> | <T><숫자>
<숫자> = 0 | 1 | ... | 9

Answer 부호(+/-) 등 단항 전위표현 연산자

Chapter 3

---

01 | 다음 주장의 참/거짓을 말하시오. ① $n^2=O(n^2)$ ② $n=\Omega (n^2)$ ③ $n^2=O(n^3)$ ④ $2n^2-100n=\Omega (n^2)$ ⑤ $3n^2+\log n=O(n^2)$ ⑥ $n^2=O(n^{100})$ ⑦ $7\log n=O(n^2)$ ⑧ $5n^2+7n-3=\Theta (n^2)$ ⑨ $5n^2+7n-3=\Omega (n\log n)$ ⑩ $7n-3=\Theta (n^2)$

Answer TFTTT TTTTF

02 | 입력의 크기가 n일 때 다음 알고리즘의 수행 시간은 n에 관한 어떤 차수에 비례하는가?

sample(A[], n):
	sum ← 0
	for i ← 0 to n-1
		sum ← sum + A[i]
	return sum

Answer 1차

03 | 입력의 크기가 n일 때 다음 알고리즘의 수행 시간을 $O$—, $\Omega$—, $\Theta$—표기법으로 각각 나타내시오.

sample(A[], n):
	sum ← 0
	for i ← 0 to n-1
		for j ← 0 to n-1
			sum ← sum + A[i] * A[j]
	return sum

Answer sample() = $\Theta (n^2)$ $O$—로는 2차 이상의 모든 값, $\Omega$—로는 2차 이하의 모든 값이 가능.

04 | 입력의 크기가 n일 때 다음 알고리즘의 수행 시간을 $\Theta$—표기법으로 나타내시오.

matrixMult(A[][], B[][], M[][], n):
	for i ← 1 to n
		for j ← 1 to n
			M[i, j] ← 0
			for k ← 1 to n
				M[i, j] ← M[i, j] + A[i, k] * B[k, j]

Answer sample() = $\Theta (n^3)$

05 | 입력의 크기가 n일 때 다음 알고리즘의 점근적 수행 시간을 $O$—, $\Omega$—표기법으로 각각 나타내시오. 단, random(1, 100)은 1부터 100까지의 정수 중 하나를 임의로 리턴한다. (함수 sample()이 하는 일은 의미 없는 일이니 개의치 말고 복잡도만 신경 쓴다.)

sample(A[], n):
	for i ← 1 to n
		if (random(1, 100) ≤ 50)
			sum ← 0
			for i ← 1 to n
				sum ← sum + A[i]

Answer $O(n^2)$, $\Omega (n)$

06 | 입력의 크기가 n일 때 다음 알고리즘의 점근적 수행 시간을 $O$—, $\Omega$—표기법으로 각각 나타내시오. 단, random(1, 100)은 1부터 100까지의 정수 중 하나를 임의로 리턴한다. (함수 sample()이 하는 일은 의미 없는 일이니 개의치 말고 복잡도만 신경 쓴다.)

sample(A[], n):
	if (n = 1) return 1
	else if (random(1, 100) ≤ 50)
		sum ← 0
		for i ← 1 to n
			sum ← sum + A[i]
	sample(A, n - 1)

Answer $O(n^2)$, $\Omega (n)$

07 | 입력 크기가 n일 때 다음 알고리즘의 점근적 수행 시간은 얼마인가? (체계적인 방법을 배우면 쉽게 답할 수 있으나 본문에서 배운 것만으로는 어려울 수 있으니 함수의 로직을 생각하면서 상상력을 발휘한다.)

sample(A[], n):
	if (n = 1) return 1
	sum ← 0
	for i ← 1 to n
		sum ← sum + A[i]
	tmp ← sum + sample(A, n - 1)
	return tmp

Answer $c_n=n+c_{n-1}$이므로, 답은 $\Theta (n^2)$.

Chapter 5

---

01 | 연결 리스트 구현 시 더미 헤드를 사용하는 장단점을 말해보시오.

Answer 연결 리스트를 관리하고 활용하는 알고리즘에는 특정 node의 previous node를 가리키는 상황이 많이 나오는데, 리스트의 맨 앞 원소에도 이러한 알고리즘을 일관적으로 적용하기 위해서는 맨 앞 원소의 previous node가 필요하며 dummy head는 이 역할을 한다. 또한, dummy head는 비어 있는 리스트에서도 class의 구조를 안정적으로 유지할 수 있도록 한다. 반면, dummy head가 있으면 메모리 공간을 추가로 차지하게 되는 것이 단점이다.

02 | 때로는 원소 x가 존재하는지 체크해주는 메서드 contains()도 요구한다. 이것은 본문에서 소개한 메서드 index(x)를 호출해서 간단히 해결할 수 있다. 다음 ① 부분을 완성하시오.

def contains(self, x) bool:
	①

Answer

	return (0 <= self.index(x) < self.__numItems)

03 | 3절의 연결 리스트에서 i~j번 원소(첫 원소는 0번 원소라 부른다)를 프린트하는 메서드 printInterval()을 작성하시오. [코드 5-15]의 클래스 LinkedListBasic에 메서드 printInterval()을 더하는 방식으로 하고 다음 ① 부분을 완성하시오.

def printInterval(self, i:int, j:int):
	①

Answer

	curr = self.__head.next
	idx = 0
	while curr != None:
		if i <= idx < j:
			print(curr.item, end = ' ')
		curr = curr.next
		idx += 1
	print()

04 | 03번 문제와 똑같은 작업을 [코드 5-22]의 CircularLinkedList에서 하시오. 역시 클래스 CircularDoublyLinkedList에 메서드를 더하는 방식으로 하고 다음 ① 부분을 완성하시오.

def printInterval(self, i:int, j:int):
	①

Answer

05 | 다음은 연결 리스트를 구현한 예다. 본문과 달리, 리스트의 원소 수를 확인하기 위해 변수 __numItems를 두지 않고 대신 비현실적이지만 메서드 numItems()로 구현했다고 가정한다. 다음 ① 부분에 메서드 numItems()를 구현하되 두 가지 방법으로 구현하시오.

class LinkedList:
	def __init__(self):
		self.__head = ListNode('dummy', None)
		self.__numItems = 0
		
	def insert(self, i:int, newItem):
		...
	def append(self, x):
		...
	...
	①
	...

① 재귀를 사용하지 않는 알고리즘으로 구현하시오. ② 재귀 알고리즘으로 구현하시오.

Answer ①

	def numItems(self):
		curr = self.__head.next
		numItems = 0
		while curr != None:
			numItems += 1
			curr = curr.next
		return numItems

②

	def numItems(self, first=None):
		if first == None:
			first = self.__head.next
		if first.next = None:
			return 1
		return 1 + self.numItems(first=first.next)

06 | 교재 참조

07 | 다음은 5절의 양방향 연결 리스트를 파이썬으로 구현한 코드다. 이 리스트에서는 int 타입의 원소들이 오름차순으로 정렬된 형태로 유지된다. 이 양방향 연결 리스트에 임의의 정수 x를 삽입하는 메서드인 add()를 작성해보시오. 다음 ① 부분을 채워 넣으면 된다.

class CircularDoublyLinkedList:
	def __init__(self):
		self.__head = BidirectNode("dummy", None, None)
		self.__head.prev = self.__head
		self.__head.next = self.__head
		self.__numItems = 0
		
	def add(self, x) -> None:
		①

Answer

		# TODO: consider n = 0 case
		
		curr = self.__head.next
		curr_val = curr.item
		while curr_val < x:
			curr = curr.next
			# If n = 0 or x is the greatest
			if curr = self.__head.next:
				break
		next = curr
		prev = curr.prev
		
		curr = BidirectNode(x, prev, next)
		prev.next = curr
		next.prev = curr
		
		self.__numItems += 1

08 | 두 노드의 레퍼런스 node1과 node2가 있다. 이들은 [코드 5-15]의 클래스 LinkedListBasic의 노드들인데 두 노드가 같은 연결 리스트에 속하는지는 모른다. 이들이 같은 연결 리스트에 속하는지 확인하는 코드를 작성하시오.

Answer

def isInSameList(node1: ListNode, node2: ListNode) -> bool:
	curr = node1
	while curr != None:
		if curr == node2:
			return True
		curr = curr.next
	curr = node2
	while curr != None:
		if curr == node1:
			return True
		curr = curr.next
	
	return False		

09 | 리스트에서 원소 x를 찾되 맨 마지막에 있는 x의 위치를 요구하는 메서드 lastIndexOf(x)가 필요하다. [코드 5-15]의 클래스 LinkedListBasic에 다음 메서드를 추가하시오. 다음 ① 부분을 완성하면 된다.

def lastIndexOf(self, x):
	①

Answer

	last_index = -12345
	curr = self.__head.next
	for index in range(self.__numItems):
		if curr.item == x:
			last_index = index
		curr = curr.next
	return last_index

10 | 09번의 메서드 lastIndexOf(self, x)를 [코드 5-25]의 클래스 CircularLinkedList에 추가하시오.

Answer

---

Chapter 6

01 | 다음 후위 표현법의 식을 스택을 이용해 계산하는 과정에서 스택의 상태 변화를 설명해보시오. (단, 15와 25는 각각 한 번에 정수로 읽어들인다고 가정한다.)

15 25 + 10 2 * -

Answer 15 → 15 25 → 40 → 40 10 → 40 10 2 → 40 20 → 20

02 | 본문에서 파이썬 내장 리스트를 사용하는 스택을 구현할 때 리스트의 맨 뒤를 스택의 탑으로 간주했다. 반대로 리스트의 맨 앞을 스택의 탑으로 간주하여 다음 클래스 listStack 코드로 바꾸어보시오.

class ListStack:
	def __init__(self):
		self.__stack = []
	
	def push(self, x):
		self.__stack.append(x)
		
	def pop(self):
		return self.__stack.pop()
		
	def top(self):
		if self.isEmpty():
			print("No element in stack")
			return None
		else:
			return self.__stack[-1]
	
	def isEmpty(self) -> bool:
		return not bool(self.__stack)
		#return len(self.__stack)==0
		
	def popAll(self):
		self.__stack.clear()
		
	def printStack(self):
		print("Stack:")
		for i in range(len(self.__stack)):
			print('stack[', i, ']:', self.__stack[i])

Answer

03 | 입력으로 들어온 문자열이 다음 집합의 원소인지 체크하는 코드를 스택을 이용해서 작성하시오. { w$w${}^R$ | w: 문자열, w${}^R$: w의 순서를 뒤집어 놓은 것 }

04 | linkedStack 타입의 객체 a의 내용을 그대로 또 다른 linkedStack 타입의 객체 b로 복사하는 코드를 작성하시오. (a의 레퍼런스 값을 b로 복사하여 두 변수가 같은 레퍼런스를 가져 내용이 같아지도록 하라는 것이 아니라 내용 복사를 요구하는 것이다.)

05 | 문자열을 받아 괄호 ’(’, ’)‘의 좌우 균형이 맞는지 체크해서 균형이 맞으면 True, 맞지 않으면 False를 리턴하는 파이썬 함수 parenBalance()를 스택을 사용해서 작성하시오. ① 부분을 채워 넣으면 된다. 문자열은 영문 소문자, 숫자, 괄호 ’(‘와 ’)‘로만 구성된다.

def parenBalance(s:String) -> bool:
	①

06 | 05번 문제는 단순히 한 종류의 괄호만 대상으로 하였다. 여러 종류의 괄호 균형이 다 맞는지 확인하려고 한다면 로직이 더 복잡해지는가? (예, ’(’, ’[’, ’{’ 3종류의 괄호가 균형이 맞는지 확인하는 경우)

07 | 프로그램이 수행될 때 끝나지 않은 함수는 시스템의 스택 영역에 저장된다. 함수 A과 함수 B를 호출하고, 함수 B가 함수 C를 호출하면, 스택에서는 아래에서부터 함수 A, 함수 B, 함수 C 관련 정보가 저장된다. 이 상태에서 함수 C가 끝나면 함수 C에 관한 정보는 지워지고 함수 B에 관한 정보가 스택 탑에 있게 된다. 다음은 n 팩토리얼을 구하는 재귀 함수다. factorial(100)의 수행 시작부터 끝나는 과정까지 스택에는 최대 몇 개의 factorial() 호출이 저장되는가? (최초의 호출인 factorial(100) 정보가 제일 먼저 스택에 저장된다.)

factorial(n):
	if n = 0
		return 1
	else
		return n * factorial(n-1)

08 | 다음은 피보나치 수열의 값을 구하는 함수다. 07번과 같은 질문이다. fib(50)의 수행은 시작부터 끝나는 과정까지 스택에는 최대 몇 개의 fib() 호출이 저장되는가?

fib(n):
	if (n = 1 or n = 2)
		return 1
	else
		return fib(n-1) + fib(n-2)

Chapter 7

---

01 | 본문에서 파이썬 내장 리스트를 사용하는 큐를 구현할 때 리스트의 맨 앞을 큐의 front로, 리스트의 맨 끝을 큐의 tail로 간주했다. 반대로 리스트의 맨 끝을 큐의 front로, 리스트의 맨 앞을 큐의 tail로 간주하여 다음 listQueue.py 코드를 바꾸어보시오.

class ListQueue:
	def __init__(self):
		self.__queue = []
		
	def enqueue(self, x):
		self.__queue.append(x)
		
	def dequeue(self):
		return self.__queue.pop(0)
		
	def front(self):
		return self.__queue[0]
		
	def isEmpty(self) -> bool:
		return len(self.__queue) == 0
		
	def dequeueAll(self):
		self.__queue.clear()

02 | 입력으로 들어온 문자열이 다음 집합의 원소인지 체크하는 코드를 큐를 이용해서 작성하시오.

{w$w | w: 문자열}

03 | LinkedQueue 타입의 객체 a의 내용을 그대로 또 다른 LinkedQueue 타입의 객체 b로 복사하는 코드를 작성하시오. (a의 레퍼런스 값을 b로 복사해 두 변수가 같은 레퍼런스를 가져 내용이 같아지게 하라는 것이 아니라 내용이 같아지도록 복사를 요구하는 것이다.)

04 | 비효율적이지만 2개의 큐를 사용하여 스택의 push()와 pop() 알고리즘을 작성하시오.

05 | 역시 비효율적이지만 2개의 스택을 사용하여 큐의 enqueue()와 dequeue() 알고리즘을 작성하시오.

06 | 이 장에서 배운 큐에서 enqueue()는 항상 큐의 맨 뒤에, dequeue()는 항상 큐의 맨 앞에서 이루어진다. Deque는 이의 변형으로 enqueue()와 dequeue()가 큐의 맨 앞과 맨 뒤에서 다 가능하다. [코드 7-13]의 클래스 환경에서 이를 가장 효율적으로 구현한다고 하자. 큐의 사이즈가 n일 때, enqueue()와 dequeue()의 수행 시간은 각각 어떻게 되겠는가?

07 | 06번 문제의 deque를 원형 연결 리스트가 아닌 [코드 5-15]의 LinkedListBasic 객체를 사용한다면 enqueue()와 dequeue()의 수행 시간은 각각 어떻게 되겠는가?

08 | 다음은 클래스 ListQueue의 파이썬 코드다. 이를 06번 문제의 자료구조 Deque를 구현하는 클래스 Deque로 바꾸어 보시오. 필요한 메서드를 추가하시오.

class ListQueue:
	def __init__(self):
		self.__queue = []
		
	def enqueue(self, x):
		self.__queue.append(x)
		
	def dequeue(self):
		return self.__queue.pop(0)
		
	def front(self):
		return self.__queue[0]
		
	def isEmpty(self) -> bool:
		return len(self.__queue) == 0
		
	def dequeueAll(self):
		self.__queue.clear()
		
	def printQueue(self):
		print("Queue from front:", end = ' ')
		for i in range(len(self.__queue)):
			print(self.__queue[i], end = ' ')
		print()

Chapter 8

---

01 | 최대 힙에서는 가장 큰 원소가 항상 루트에 있다. 즉, 루트의 깊이가 가장 얕다. 임의의 최대 힙에서 더 얕은 곳에 있는 원소가 더 깊은 곳에 있는 원소보다 더 작은 값을 가질 수 있는가?

Answer 그렇다. 최대 힙에서의 대소관계 제한은 부모-자식 노드의 지역적 관계에만 한하기 때문이다.

02 | 최대 힙 A[0...n-1]에서 A[0]은 항상 가장 큰 값을 갖고 있다. 반대로 마지막 원소인 A[n-1]은 항상 가장 작은 값을 갖는가?

Answer 항상 그런 것은 아니다. 당장 두 자식 노드 중 왼쪽에 있는 노드가 더 작은 값을 가지는 경우도 가능하다.

03 | 임의의 리스트 A[0...n-1]을 힙으로 만드는 buildHeap() 알고리즘에서 총 n개의 원소 중 루트의 자격으로 스며내리기를 할지 알아보지 않고 그냥 넘어가는 원소(힙의 노드) 수는 정확하게 몇 개인가?

Answer 검사를 해야 하는, 즉 자식이 있는 노드의 개수가 $[\frac{n}{2}-1]$개이므로 나머지인 $n-[\frac{n}{2}-1]$개가 모두 그냥 넘어가는 노드의 수에 해당한다.

04 | 리스트 A[0...n-1]을 대상으로 하는 스며내리기 알고리즘에서 최악의 경우에 해당하는 시간과 최선의 경우에 해당하는 시간은 어떻게 되는가? $\Theta$—표기로 나타내시오.

Answer $\Theta (\log n)$, $\Theta (1)$

05 | 힙인 상태에서 원소 삭제는 루트 노드만 대상으로 한다. 다른 경우는 존재하지 않는다. 테스트 목적으로 힙의 맨 마지막 원소를 삭제하는 작업을 요구한다면 간단한 일인가?

Answer 힙 성질은 recursive하게 만족하므로 맨 마지막 원소를 지워도 그대로 힙이기에 테스트 목적이라면 간단한 일이지만, 힙의 맨 마지막 원소라고 하여 가장 작은 원소인 것은 아니므로 무의미하다.

06 | 어떤 학생이 다음과 같은 질문을 했다. “buildHeap() 알고리즘에서는 아래쪽에서부터 시작해서 스며내리기를 반복하는데 만약 반대 방향으로 하면 어떤가요?(즉, 위쪽에서부터 시작해서 스며오르기를 반복)” 이렇게 해도 힙이 만들어진다. 이 방법은 본문에 제시한 방법에 비해 더 효율적인가? 점근적 시간으로 말하시오.

Answer 아래에서부터의 스며내리기를 통한 힙 생성 방법은 $O(n)$만큼의 시간복잡도를 가짐이 알려져 있다. 이 시간복잡도는 단순 스며내리기의 $O(\log n)$과 스며내리기를 시작하는 노드의 개수인 $n/2$를 단순히 곱한 것이 아닌, 스며내리기 높이가 낮은 하위 노드들의 개수가 많은 것을 고려하여 계산하면 $O(n)$만큼으로 줄어든 결과이다. 반면 위에서부터의 스며오르기의 경우 작업을 생략해도 되는 노드가 루트 노드 단 하나뿐이며, 최대 높이의 스며오르기를 해야 하는 하위 노드들의 개수가 많은 것이 두 시간 복잡도를 단순 곱에 가깝게 하여 $O(n\log n)$의 시간복잡도를 갖게 한다. 따라서 이는 본문의 알고리즘보다 비효율적이다.

07 | n개의 원소로 이루어진 최대 힙에서 임의의 원소 값이 증가했을 때 O(log n) 시간에 이를 반영해서 힙을 수선할 수 있다. 어떻게 하면 되는지 그 과정을 기술하시오.

Answer 해당 노드를 제거하는 연산(스며 오르기, $O(\log n)$)과 다시 증가한 값을 삽입하는 연산(스며 내리기, $O(\log n)$)을 연달아 하는 것으로 간단히 해결된다.

Chapter 10

---

01 | 다음 이진 검색 트리에 대해 답하시오.

        40
   10       55
 7   20    x  70
x x 17 x  x x x x

① 이 이진 검색 트리의 리프 노드는 총 몇 개인가? ② 현재 높이 4를 유지하면서 키를 추가한다면 가능한 리프 노드의 최대 개수는 몇 개인가? ③ 높이 4인 이진 검색 트리가 포화 이진 트리의 모양이 되면 리프 노드와 리프 노드를 제외한 나머지 노드(내부 노드라 한다)의 수는 몇 개나 차이가 나는가? ④ 위 ③의 성질은 높이가 h(h는 양의 정수)인 모든 포화 이진 트리에 대해 성립하는가?

Answer ① 3개 ② 8개 ③ 1개 ④ 그렇다.

02 | 임의의 완전 이진 트리에 대한 다음 물음에 답하시오. ① 트리의 총 노드 수가 n이면 리프 노드의 수는 몇 개인가? ② 위 ①에서 리프 노드의 수와 내부 노드의 수는 어떤 관계인가?

Answer ① $[(n+1)/2]$ ② 왼쪽 자식이 생기면 내부 노드의 수가 늘어나고, 리프 노드의 수는 그대로다. 반면 오른쪽 자식이 생기면 내부 노드의 수가 그대로이며 리프 노드의 수가 늘어난다.

03 | 다음 이진 검색 트리에 대해 답하시오.

       5
   3       8
 1   x   7   9
x x x x 6 x x x

① 이 검색 트리를 전위 순회 방식으로 순회할 때 노드의 방문 순서를 나열하시오. 순서는 노드에 있는 킷값으로 적으시오. ② 이 검색 트리를 중위 순회 방식으로 순회할 때 노드의 방문 순서를 나열하시오. ③ 이 검색 트리를 후위 순회 방식으로 순회할 때 노드의 방문 순서를 나열하시오. ④ 중위 순회는 모든 이진 검색 트리에 대해 항상 키를 정렬된 순서로 방문한다는 사실을 증명하시오.

Answer ① 5318769 ② 1356789 ③ 1367985 ④ 중위 순회의 알고리즘을 보면 왼쪽 자식을 순회하는 재귀 호출, 루트 노드 호출, 오른쪽 자식을 순회하는 재귀 호출이 순서대로 발생한다. 그런데 이때 왼쪽 자식 노드들은 모두 반드시 루트 노드 값보다 작고, 오른쪽 자식 노드들은 모두 반드시 루트 노드 값보다 크므로 알고리즘 수준에서 정렬이 깨질 수 있는 여지가 존재하지 않는다. 그리고 이는 자명하게도 모든 하위 재귀 호출에서 일반적으로 성립한다.

04 | 다음 이진 검색 트리에서 키 30을 검색하는 과정을 순서대로 설명하시오.

               55
       15              60
   8       28       x      90
 3   x   18  30   x   x   x   x
x x x x x x x 48 x x x x x x x x

Answer 첫 번째 노드에서 30 < 55이므로 왼쪽으로 간다. 두 번째 노드에서 15 < 30이므로 오른쪽으로 간다. 세 번째 노드에서 28 < 30이므로 오른쪽으로 간다. 네 번째 노드에서 30 = 30이므로 이 노드를 반환하고 검색이 종료된다.

05 | 04번 문제의 이진 검색 트리에서 키 16이 삽입된 후의 모양을 그리시오.

Answer

                55
       15               60
   8        28       x      90
 3   x   18   30   x   x   x   x
x x x x 16 x x 48 x x x x x x x x

06 | 다음 이진 검색 트리에서 키 38을 삭제한 후의 모양을 그리시오.

               55
       15              60
   8       28       x      90
 3   x   x   30   x   x   x   x
x x x x x x x 48 x x x x x x x x
        ... 38  50
      ... 33  x x x
    ... 32  36

Answer

               55
       15              60
   8       28       x      90
 3   x   x   30   x   x   x   x
x x x x x x x 48 x x x x x x x x
            33  50
          32  36 x x

07 | 06번 문제에서 주어진 이진 검색 트리에서 키 3을 삭제한 후의 모양을 그리시오.

Answer

               55
       15              60
   8       28       x      90
 x   x   x   30   x   x   x   x
x x x x x x x 48 x x x x x x x x
        ... 38  50
      ... 33  x x x
    ... 32  36

08 | 06번 문제에서 주어진 이진 검색 트리에서 키 15를 삭제한 후의 모양을 그리시오.

Answer 15를 대체할 가장 작은 원소를 15의 오른쪽에서 찾아야 한다. 이는 28이다. 28을 지우는 것은 자식이 하나인 노드를 지우는 것이므로 아래와 같이 쉽게 할 수 있다.

               55
       28              60
   8       30       x      90
 3   x   x   48   x   x   x   x
x x x x x x 38 50 x x x x x x x x
       ... 33 x x x
     ... 32  36

09 | n개의 원소로 구성되는 이진 검색 트리의 가능한 최대 높이와 최소 높이는 어떻게 되는가?

Answer 포화 이진 트리(또는 완전 이진 트리)의 경우가 가장 높이가 작은 경우에 해당한다. 이 트리의 높이가 $h$라고 할 때, $2^{h-1}-1<n\le 2^h-1$ 이므로 $h-1<\log (n+1)\le h$이고, 따라서 높이는 $\lceil \log (n+1)\rceil$ 이 된다. 반면 가장 높은 트리가 되는 경우는 모두 한쪽 방향 자식만 가지는 경우로, 높이가 n이다.

Chapter 12

---

01 | 해시 테이블 크기를 1,024로 잡고 해시 함수로 h(x)=x%1024를 사용하였다. 어떤 결점이 있는가?

Answer 하위 10개 비트수가 가까우면 해시 테이블에서의 위치도 가까워져 독립성을 위반한다.

02 | 한 학생이 “다음과 같이 해시 함수를 만들면 확률적으로 고른 분포를 보이는 좋은 함수가 되지 않을까요?”라고 물었다. 단, random(0,10)은 0보다 크고 10 이하인 임의의 실수를 생성한다.

h(x) = x * random(0,10) % m

이것은 해시 함수가 될 수 없다. 이유를 설명하시오.

Answer 매번 다른 값을 생성하여 searching이 성립할 수 없다.

03 | 해시 테이블 크기가 10,000이다. 해시 테이블에 들어갈 키 $x\in \{0,1,\cdots ,10000\}$이다. 해시 함수를 다음과 같이 만들면 어떨지 의견을 말하시오. 단, random(x, 0, 1)은 0 이상 1 미만의 실수를 생성하되 x값이 같으면 같은 값을 생성한다.

h(x) = x * random(x, 0, 1)

Answer 우선 실수값이라는 점이 가장 큰 문제인데, 이를 가우스를 씌워 해결한다고 해도

04 | 크기가 13인 해시 테이블이 해시 함수로 h(x) = x % 13을 사용한다. 충돌 해결은 개방 주소 방법의 선형 탐색 h_i(x)=(h(x)+i)%13, i=0,1,2,...을 택한다. 키 10, 20, 30, 40, 33, 46, 50, 60이 차례로 저장된 후 해시 테이블의 모양은 어떻게 되는가?

Answer 10 → 10 20 → 7 30 → 4 40 → 1 33 → 7 → 8 46 → 7 → 8 → 9 50 → 11 60 → 8 → 9 → 10 → 11 → 12

⇒ x 40 x x 30 x x 20 33 46 10 50 60

05 | 04번 문제에서 선형 탐색 대신 해시 함수 h_i(x)=(x+i^2)%13을 사용하는 이차원 탐색을 택할 경우 최종적인 해시 테이블 모양은 어떻게 되는가?

Answer 10 → 10 20 → 7 30 → 4 40 → 1 33 → 7 → 8 46 → 7 → 8 → 11 50 → 11 → 12 60 → 8 → 9 → 12 → 4 → 11 → 7 → 5

⇒ x 40 x x 30 60 x 20 33 x 10 46 50

06 | 04번 문제에서 선형 탐색 대신 더블 해싱 h_i(x)=(h(x)+i*f(x))%13을 사용할 때 최종적인 해시 테이블 모양은 어떻게 되는가? (단, h(x)=x%13, f(x)=1+(x%11))

Answer 10 → 10 20 → 7 30 → 4 40 → 1 33 → 7 → 8 46 → 7 → 10 → 0 50 → 11 60 → 8 → 1 → 7 → 0 → 6

⇒ 46 40 x x 30 x 60 20 33 x 10 50 x

07 | 체이닝을 사용하는 충돌 해결 방법에서 각 연결 리스트에 새로운 키가 삽입될 때 리스트의 맨 앞에 삽입하지 않고 맨 뒤에 삽입한다면 효율성 면에서 어떤 변화가 생기는가?

Answer 연결 리스트로 연결된 해당 해시값의 체인 맨 끝까지 타고 가서 삽입해야 하므로 중심 알고리즘과는 무관한 체이닝 길이에 비례하는 시간복잡도가 발생한다.

08 | 체이닝을 사용하는 충돌 해결 방법에서 각 연결 리스트를 정렬된 형태로 유지한다면 효율성 면에서 어떤 변화가 생기는가? (삽입, 삭제, 성공적인 검색, 실패하는 검색의 경우로 나누어 생각하시오.)

Answer 체인의 길이를 $l$이라고 하면, 기존에는 삽입에 $O(1)$, 삭제와 성공적인 검색은 원소가 체인의 어디에 있을지 모르니까 $O(l)$, 실패하는 검색은 반드시 $l$만큼의 시간이 걸린다. 반면 리스트를 정렬한 상태로 유지하면 특정 원소가 있다면 정확히 어디에 있을지 알고 있기 때문에 삽입, 삭제, 성공적인 검색, 실패하는 검색 모두 $O(l)$의 시간이 걸리며 이때 실패하는 검색에 드는 시간은 반드시 감소한다.

09 | 더블 해싱에서 두 번째 해시 함숫값 f(x)와 해시 테이블 크기 m이 1보다 큰 최소공약수 d를 가지면 x의 자리를 찾기 위해 해시 테이블 전체 중에 기껏해야 1/d밖에 보지 못하게 되는 이유를 설명하시오.

Answer 선형 탐색의 간격이 주기성을 띠게 되기 때문이다.

10 | 좋지 않은 선택이지만 문제를 만들기 위해 해시 테이블 크기를 100이라 하고, 해시 함수 h(x) = x%100을 사용한다. 충돌 해결은 선형 탐색을 사용한다. 키 50개가 다음 순서로 저장되었다면 나중에 이들을 검색할 때 각 키당 평균 몇 번의 탐색이 필요한가?

100,200,...,1000,101,201,...,1001,102,202,...,
1002,103,203,...,1003,104,204,...,1004

Answer