CS 과제

1. Python List method의 시간복잡도

기능	설명	시간복잡도
a.append(value)	마지막에 요소 추가	O(1)
a.count(value)	리스트에 있는 value의 개수 반환	O(n)
a.remove(value)	리스트에서 가장 먼저 등장하는 value 삭제	O(n)
a.extend(b)	리스트 a에 리스트 b를 연장	O(k)
a.reverse()	리스트 a의 요소들의 순서를 거꾸로 바꿔줌	O(n)

 

 

2. CircularQueue 구현해보기

import numpy as np
# circular queue, 원형큐

class CircularQueue:
    def __init__(self, size):
        self.buffer = np.zeros(size, dtype=int)
        self.max_size = size
        self.size = 0
        self.front = 0
        self.rear = 0

    def __str__(self):
        _str = f"size: {self.size}, max_size: {self.max_size}, [" 
        idx = self.front
        for _ in range(self.size):
            _str += str(self.buffer[idx]) + " "
            idx = (idx + 1) % self.max_size
        _str += "]"
        return _str
            
        
    def enqueue(self, data):
        if self.is_full():
            return False
            
        self.buffer[self.rear] = data
        self.rear = (self.rear + 1) % self.max_size

        self.size += 1
        return True
    
    def dequeue(self):
        if self.is_empty():
            return None

        data = self.buffer[self.front]
        self.front = (self.front + 1) % self.max_size
        
        self.size -= 1
        return data
    
    def is_empty(self):
        return self.size == 0
        
    def is_full(self):
        return self.size == self.max_size

# 실제 사용 예시
cq = CircularQueue(5)
# enqueue 10 ~ 60 [10,20,30,40,50]
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)
cq.enqueue(50)
cq.enqueue(60)
print(cq)

# dequeue 10, 20 [30,40,50]
print(cq.dequeue())
print(cq.dequeue())
print(cq)

# enqueue 60, 70 [30,40,50,60,70]
cq.enqueue(60)
cq.enqueue(70)
print(cq)

while not cq.is_empty():
    print(cq.dequeue())
print(cq)

cq.dequeue()
print(cq)

출력:

size: 5, max_size: 5, [10 20 30 40 50 ]
10
20
size: 3, max_size: 5, [30 40 50 ]
size: 5, max_size: 5, [30 40 50 60 70 ]
30
40
50
60
70
size: 0, max_size: 5, []
size: 0, max_size: 5, []

 

3. Hash Collision을 극복하는 방법에 Separate Chaining과 Open Addressing이 있습니다. 이 중에 Python dictionary에서는 Open Addressing을 사용하고 있습니다. Open Addressing의 여러 방법을 조사하고 Python dictionary의 구현 방식을 이해해보려고 합니다.

 

Open Addressing의 대표적인 방법 3가지가 있습니다. 아래 3가지 방식이 어떻게 동작하는지 최대한 자세하게 기술하세요.

1. Linear Probing
2. Quadratic Probing
3. Double Hashing

 

CPython의 dictionary 구현체를 찾아서, 어떤 방식으로 Open Addressing을 구현했는지 방법론에 대해서 정리해보세요.

 

Linear Probing (선형 탐사법)

해시 충돌이 발생한 위치부터 순차적으로 다음 위치를 탐색하여 비어있는 공간의 새로운 인덱스를 찾아 데이터를 저장

 

장점

구현이 비교적 간단하다

순차적으로 메모리에 접근하기 때문에 캐시 효율이 높다 (space complexity)

 

단점

Clustering (군집화) : 연속된 공간에 데이터가 몰리는 현상이 발생하여 탐색시간이 증가할 수 있다

클러스터링으로 인해 데이터를 탐색하는 시간이 증가할 수 있다. 특히 테이블이 거의 가득 찼을 때 심각해진다

삭제 문제 : 데이터를 단순히 삭제하면 탐색시 문제가 발생할 수 있다. 삭제된 위치를 표시하거나(tombstone) 재해싱하는 등의 추가적인 작업이 필요하다

 

적합한 상황

해시 테이블의 크기가 충분히 크고, 데이터의 개수가 적을 때

구현의 단순성이 중요한 경우

 

참고

https://youtu.be/Bj4pd9rJp5c

 

Quadratic Probing

해시 충돌 발생시 제곱수만큼 떨어진 인덱스를 탐색하여 빈 슬롯을 찾는 방법

초기위치가 h(k) 이고 충돌발생시, 다음 탐색 위치는 h(k) + 1^2, h(k) + 2^2, h(k) + 3^2 ...

Linear의 경우는 충돌위치 +1, +2, +3, +4 ... 라면, Quadratic은 +1, +4, +9, +16 ...

 

장점

클러스터링 감소 : 선형 탐사(Linear Probing)에 비해 클러스터링 현상을 줄여준다

 

단점

2차 클러스터링(Secondary Clustering) 발생 가능성 : 초기 해시 값이 같은 키들은 동일한 탐사 순서를 갖게 되어 2차 클러스터링이 발생할 수 있다

테이블 크기가 소수가 아닌 경우 빈 슬롯을 찾지 못할 수 있다

예 1) 테이블 크기가 16인 경우

i = 1: h(k) + 1

i = 2: h(k) + 4

i = 3: h(k) + 9

i = 4: h(k) + 16 = h(k) (mod 16)

i = 5: h(k) + 25 = h(k) + 9 (mod 16)

i = 6: h(k) + 36 = h(k) + 4 (mod 16)

i = 7: h(k) + 49 = h(k) + 1 (mod 16)

....

 

예 2) 테이블 크기가 8이고 해시 값이 2인 경우

i = 1: 2 + 1 = 3

i = 2: 2 + 4 = 6

i = 3: 2 + 9 = 3 (mod 8)

i = 4: 2 + 16 = 2 (mod 8)

i = 5: 2 + 25 = 3 (mod 8)

i = 6: 2 + 36 = 6 (mod 8)

i = 7: 2 + 49 = 3 (mod 8)

3, 6, 3, 2 의 반복

 

 

Double Hashing

두 개의 해시 함수를 사용해서 탐사 간격을 계산하는 기법

 

동작방식 :

1. 키를 이용하여 첫 번째 해시 함수 h1(k) 를 통해 초기 해시 값을 계산하고, 두 번째 해시 함수 h2(k) 를 통해 탐사 간격을 계산한다

2. h2(k) 는 0이 되지 않도록 설계하며, 일반적으로 테이블 크기보다 작은 소수를 사용한다

3. 해시 충돌 발생시 (h1(k) + i * h2(k)) % 테이블 크기 규칙에 따라 빈 슬롯을 탐색한다. (i는 0부터 시작해서 1씩 증가)

 

예시)

테이블 크기: 13

h1(k) = k % 13

h2(k) = 7 - (k % 7)

키 : 14

1. h1(14) = 14 % 13 = 1 >> 인덱스 1에 충돌 발생

2. h2(14) = 7 - (14 % 7) = 7 >> 탐사 간격 7

3. 다음 탐색 위치 : (1 + 1 * 7) % 13 = 8 >> 인덱스 8 확인

4. 인덱스 8에 빈 슬롯이 있다면 데이터를 저장하고, 그렇지 않다면 i를 2로 증가시켜 (1 + 2 * 7) % 13 = 2 를 계산하여 인덱스 2를 확인하는 방식으로 탐색을 계속한다

 

장점

- 클러스터링 감소 : Quadratic Probing에 비해 클러스터링 현상을 더 효과적으로 줄일 수 있다. 초기 해시 값이 같은 키들이라도 서로 다른 순서로 슬롯을 탐색하게 된다.

- 균등한 데이터 분포 : 데이터를 테이블에 보다 균등하게 분포시켜 탐색 효율을 높인다

 

단점

- 구현이 조금 더 복잡해지고 두 번의 해시 함수 계산이 필요하므로 해시 함수의 성능이 좋지 않으면 오히려 탐색 속도가 느려질 수 있다.

 

 

4. 주어진 3개의 numpy array에 대해서 Binary Search Tree를 만들고, 각 Tree에서 10번의 search를 수행했을 때의 평균 검색 속도를 측정하세요.

import numpy as np
import time

np.random.seed(0xC0FFEE)

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = TreeNode(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left:
                self._insert_recursive(node.left, value)
            else:
                node.left = TreeNode(value)
        else:
            if node.right:
                self._insert_recursive(node.right, value)
            else:
                node.right = TreeNode(value)

    def search(self, value):
        return self._search_recursive(self.root, value)

    def _search_recursive(self, node, value):
        if node is None:
            return False
        elif node.value == value:
            return True
        elif value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)

# 배열 크기 설정
array_sizes = [1000, 10000, 100000]

# NumPy 배열 생성
arrays = [np.random.randint(0, 1000000, size) for size in array_sizes]

# 3개의 array에 대해서 구현된 Binary Search Tree로 탐색을 했을 때의 시간을 측정하는 코드를 만들어보세요.

import time

bst_array = [BinarySearchTree() for i in range(len(arrays))]

for i in range(len(arrays)):
  for num in arrays[i]:
    bst_array[i].insert(num)

np.random.seed(1000)


for i in range(len(arrays)):
  elapsed_time = 0
  
  for _ in range(10):
    rand_index = np.random.randint(len(arrays[i]))
    start_time = time.perf_counter()
    bst_array[i].search(arrays[i][rand_index])
    end_time = time.perf_counter()
    elapsed_time += end_time - start_time

  print(f"sum: {elapsed_time * 1000000} us, avg: {elapsed_time * 1000000 / 10} us") # us 마이크로초

sum: 61.256000662979204 us, avg: 6.12560006629792 us
sum: 146.58400050393539 us, avg: 14.658400050393539 us
sum: 133.2100018771598 us, avg: 13.321000187715981 us

 

 

5. DFS를 이용하여 다음 주어진 그래프를 탐색하는 순서를 출력하는 코드를 완성하세요. DFS 구현은 stack을 사용하는 iteration 구현과 recursion을 사용하는 2가지 방식을 모두 포함하세요.

# 그래프를 adjacency list로 표현 (undirected graph)
## (0 : [1, 2, 3]은 vertex0에 vertex1, 2, 3이 연결되어 있다는 의미)
graph = {
    0: [1, 2, 3],
    1: [0, 4, 5],
    2: [0, 6],
    3: [0, 7],
    4: [1, 8],
    5: [1, 8, 9],
    6: [2, 9],
    7: [3, 10, 11],
    8: [4, 5, 12],
    9: [5, 6, 12],
    10: [7, 13],
    11: [7, 13],
    12: [8, 9, 14],
    13: [10, 11, 14],
    14: [12, 13]
}


def dfs_recursive(graph, node, visited):
  visited.add(node)
  print(node, end=' ')

  for graph_node in graph[node]:
    if graph_node not in visited:
      dfs_recursive(graph, graph_node, visited)


def dfs_iterative(graph, start):
  stack = [start]
  visited = set()

  while stack:
    node = stack.pop()
    if node in visited:
      continue
    
    visited.add(node)
    print(node, end=' ')

    neighbors = graph[node]
    for neighbor in reversed(neighbors):
      if neighbor not in visited:
        stack.append(neighbor)
		

## Example.
print("Recursion : ")
visited_recursive = set()
dfs_recursive(graph, 0, visited_recursive)

print("\n\nIteration : ")
# 반복 DFS 실행
dfs_iterative(graph, 0)

Recursion : 
0 1 4 8 5 9 6 2 12 14 13 10 7 3 11 

Iteration : 
0 1 4 8 5 9 6 2 12 14 13 10 7 3 11