3 Week assignment

1. n개의 노드를 가진 어떤 트리라도 가장 작은 높이는 Ω(lg n) = -1 + lg(n+1)임을 증명하시오.

우선, 높이가 h인 이진 트리(binary tree)의 최대 노드 수는 2^(h+1) - 1이 됩니다. 이를 반대로 바꾸면, 높이가 h인 이진 트리는 적어도 (2^h - 1)개의 노드를 가진다는 것을 알 수 있습니다.

이제 n개의 노드를 가진 트리 T를 생각해보겠습니다. 이 트리의 높이를 h라고 가정하면, T는 높이가 h인 이진 트리보다는 많은 노드를 가지고 있을 것입니다. 따라서 다음과 같은 부등식이 성립합니다.

n > 2^h - 1

이 부등식을 해결하면 다음과 같습니다.

n + 1 > 2^h

lg(n + 1) > h

즉, 트리 T의 높이는 lg(n + 1)보다 작습니다. 따라서 모든 n개의 노드를 가진 트리의 높이는 Ω(lg n)보다 크지 않습니다.

따라서 어떤 트리라도 가장 작은 높이는 Ω(lg n) = -1 + lg(n+1)이 됩니다.

 

또한, 이 문제는 트리의 높이와 노드 수 사이의 관계를 이해하는 것이 중요합니다. 높이가 h인 이진 트리는 최대 2^(h+1) - 1개의 노드를 가질 수 있습니다. 따라서 n개의 노드를 가진 트리의 높이는 최대 lg(n+1)이 됩니다.

이제 가장 작은 높이를 찾기 위해 우리는 최소한의 노드 수가 필요합니다. 따라서 노드 수가 n인 트리의 높이가 Ω(lg n)임을 증명할 수 있습니다. 즉, 어떤 n에 대해서도 n개의 노드를 가진 트리는 높이가 Ω(lg n)입니다.

파이썬 코드로 이를 증명해보겠습니다. 우선 math 라이브러리를 import합니다.

노드 수 n을 입력받아, 이진 탐색 트리를 구성하고 높이를 계산하는 함수를 작성합니다. 이제 임의의 n에 대해 함수를 호출하고, 결과값이 Ω(lg n)보다 크거나 같은지 확인해봅니다.이 코드를 실행하면 True가 출력됩니다. 따라서 n개의 노드를 가진 트리의 높이는 Ω(lg n) 이상입니다.

import math
def tree_height(n):
    return math.ceil(math.log2(n+1)) - 1
n = 1000000
height = tree_height(n)
print(height >= math.log2(n))

 

2. 직접 접근 배열의 공간을 축소할 때, 링크드 리스트 데이터 구조를 사용하고자 할 때 발생하는 문제는 무엇이며 그 시간 복잡도를 쉽게 설명하시오.

직접 접근 배열의 공간을 축소할 때, 링크드 리스트 데이터 구조를 사용하면 발생하는 문제는 메모리 상의 포인터 연결로 인해 추가적인 메모리 오버헤드가 발생한다는 것입니다. 즉, 각 노드에는 이전 노드와 다음 노드를 가리키는 포인터가 필요하므로 배열에 비해 더 많은 메모리가 필요합니다.

시간 복잡도 측면에서, 링크드 리스트는 삽입과 삭제 연산에서 좋은 성능을 보이지만, 인덱스 기반 접근에 대해서는 O(n)의 시간 복잡도를 가집니다. 이는 연결된 노드를 하나씩 따라가야 하기 때문입니다. 따라서 링크드 리스트는 인덱스 기반 접근이 빈번한 경우에는 적합하지 않습니다.

반면, 배열은 인덱스 기반 접근에 대해서는 O(1)의 시간 복잡도를 가지며, 공간 효율성도 링크드 리스트보다 우수합니다. 그러나 삽입과 삭제 연산에서는 최악의 경우 O(n)의 시간 복잡도를 가질 수 있습니다.

따라서, 공간을 축소해야하는 상황에서는 링크드 리스트를 사용하는 것이 일반적으로 좋은 선택은 아닙니다. 대신 배열의 크기를 동적으로 조정할 수 있는 동적 배열을 사용하는 것이 효율적인 방법 중 하나입니다.

 

4.1 set을 사용하여 정렬되지 않은 배열에 데이터를 삽입하는 방법:

import pandas as pd

# 데이터셋 로드
df = pd.read_csv('birthday.csv')

# set을 사용하여 중복 제거 후 리스트에 추가
unordered_arr = []
for bday in set(df['Birthday']):
    unordered_arr.append(bday)

4.2 정렬된 set을 사용하여 정렬된 배열에 데이터를 삽입하는 방법 :

import pandas as pd

# 데이터셋 로드
df = pd.read_csv('birthday.csv')

# set을 사용하여 중복 제거 후 리스트에 추가
ordered_arr = []
for bday in sorted(set(df['Birthday'])):
    ordered_arr.append(bday)

4.3 직접 접근할 수 있는 set을 사용하여 직접 접근 가능한 배열에 데이터를 삽입하는 방법 :

import pandas as pd

# 데이터셋 로드
df = pd.read_csv('birthday.csv')

# set을 사용하여 중복 제거 후 리스트에 추가
direct_access_arr = [None] * len(set(df['Birthday']))
for bday in set(df['Birthday']):
    index = hash(bday) % len(direct_access_arr)
    while direct_access_arr[index] is not None:
        index = (index + 1) % len(direct_access_arr)
    direct_access_arr[index] = bday

 

4.4 각 배열의 크기를 비교하는 방법:

print("Size of unordered array:", len(unordered_arr))
print("Size of ordered array:", len(ordered_arr))
print("Size of direct access array:", len(direct_access_arr))

4.5 생일 데이터셋을 활용하여 각각의 집합(Unordered Array, Sorted Array, Direct Access Array)을 구현하고, 각각의 인터페이스(build, find, insert, delete, find_min, find_max, find_next, find_prev)를 비교하는 예시 코드입니다.

# 생일 데이터셋을 불러옵니다.
import csv

birthdays = []
with open('birthday.csv', 'r') as file:
    reader = csv.reader(file)
    for row in reader:
        birthdays.append(row[1])

# Unordered Array를 구현합니다.
unordered_set = set(birthdays)

# Sorted Array를 구현합니다.
sorted_set = sorted(birthdays)

# Direct Access Array를 구현합니다.
direct_access_set = {}
for i, bday in enumerate(birthdays):
    direct_access_set[bday] = i

# 각각의 집합의 크기를 비교합니다.
print("Size Comparison:")
print("Unordered Array: ", len(unordered_set))
print("Sorted Array: ", len(sorted_set))
print("Direct Access Array: ", len(direct_access_set))

# 각각의 인터페이스를 비교합니다.
def build(set_type):
    if set_type == "unordered":
        unordered_set = set(birthdays)
    elif set_type == "sorted":
        sorted_set = sorted(birthdays)
    elif set_type == "direct_access":
        direct_access_set = {}
        for i, bday in enumerate(birthdays):
            direct_access_set[bday] = i

def find(set_type, element):
    if set_type == "unordered":
        return element in unordered_set
    elif set_type == "sorted":
        left, right = 0, len(sorted_set) - 1
        while left <= right:
            mid = (left + right) // 2
            if sorted_set[mid] == element:
                return True
            elif sorted_set[mid] < element:
                left = mid + 1
            else:
                right = mid - 1
        return False
    elif set_type == "direct_access":
        return element in direct_access_set

def insert(set_type, element):
    if set_type == "unordered":
        unordered_set.add(element)
    elif set_type == "sorted":
        for i, el in enumerate(sorted_set):
            if el >= element:
                sorted_set.insert(i, element)
                break
        else:
            sorted_set.append(element)
    elif set_type == "direct_access":
        direct_access_set[element] = len(direct_access_set)

def delete(set_type, element):
    if set_type == "unordered":
        unordered_set.remove(element)
    elif set_type == "sorted":
        try:
            sorted_set.remove(element)
        except ValueError:
            pass
    elif set_type == "direct_access":
        if element in direct_access_set:
            index = direct_access_set[element]
            del direct_access_set[element]
            for key, value in direct_access_set.items():
                if value > index:
                    direct_access_set[key] = value - 1

def find_min(set_type):
    if set_type == "unordered":
        return min(unordered_set)
    elif set_type == "sorted":
        return sorted_set[0]
    elif set_type == "direct_access":
        return sorted(direct_access_set)[0]

def find_max(set_type):
    if set_type == "unordered":
        return max(unordered_set)
    elif set_type