- n개의 노드에서 트리의 가장 작은 높이가 Ω(lg n) = - 1 + lg(n+1)임을 증명하라.
- 나의 풀이: n개 노드의 최소 높이는 완전이진트리를 통해 나온다고 생각을 하였다. 왜냐하면 노드가 최대한 빈공간 없이 압축되어야 최소높이가 나오게 되고, 그러한 트리는 완전이진트리이기 때문이다. 그래서 이진 트리 노드를 그려보면서 높이의 규칙을 찾아 해답을 찾아내려고 하였다. 예를 들어 노드개수가 1일 때는 높이가 0, 2~3일때는 높이가 1, 4~7일 때는 높이가 2, 8~15일 때는 높이가 3.. 이런식으로 규칙이 생긴다. 그러나 이 숫자들을 통해 Ω(lg n) = - 1 + lg(n+1) 의 수식은 추론하기 어려워 서치를 해보았다.
- 인터넷 해답: 트리의 노드 수가 n일 때 높이가 h 인 트리에서 가질 수 있는 노드의 최대 수는 2^h - 1 이 된다. 이 수식을 이용해본다면,
n <= 2^h-1
n+1 <= 2^h
h >= lg(n+1)
h - 1 >= lg(n+1) - 1
(여기서 h - 1은 n개의 노드를 가진 트리의 가장 작은 높이를 나타내)이렇게 수식을 전개하며 해답을 얻을 수 있었다.
- 직접 접근 배열(direct access array)의 공간을 축소해야 할 경우 linked list 데이터 구조를 사용할 수도 있는데 이때 어떤 문제가 발생하는지 시간 복잡도를 이용하여 설명하여라.
-> 그냥 배열을 이용하여 직접 접근 배열을 구현하게 되면, 시간 복잡도가 O(1)의 시간으로 해당 인덱스를 바로 접근할 수 있다. 그러나 연결리스트로 구현을 하게되면 바로 해당 인덱스에 접근할 수 없어(random access를 지원하지 않아) 시작점부터 시작하여 해당 인덱스까지 순회해야 한다. 따라서 최악의 경우 O(n)이 소요된다. 이처럼 원래보다 시간 복잡도가 훨씬 늘어나게 되는 성능 문제가 발생하게 된다.
- 서치를 통해 찾은 생각치 못한 부분: 메모리 오버헤드
링크드 리스트의 각 원소가 값과 함께 다음 노드에 대한 참조(reference)를 저장하는 개별 노드 객체를 필요로 하기 때문입니다. 이는 더 빈번한 메모리 할당 및 해제를 야기할 수 있으며, 프로그램의 성능을 저하시키고 메모리 단편화와 메모리 누수 위험을 증가시킬 수 있습니다.
- 이전에 활용했던 생일 데이터를 이용하여 다음 문제들을 풀어라.
3-1. 세트를 사용하여 정렬되지 않은 배열에 넣는다.import pandas as pd df = pd.read_csv('/Users/hansunkyoung/Projects/algorithm/BirthdayData.csv', encoding='UTF-8') birth_df = df.iloc[1:, 2:3] birth_df.fillna(0) _birth_lst = birth_df.values.tolist() birth_lst = [] for i in range(0, len(_birth_lst)): birth_lst.append(float(_birth_lst[i][0])) print(birth_lst)
3-2. 세트를 정렬된 배열 집합에 넣습니다.
import pandas as pd
df = pd.read_csv('/Users/hansunkyoung/Projects/algorithm/BirthdayData.csv', encoding='UTF-8')
birth_df = df.iloc[1:, 2:3]
birth_df.fillna(0)
_birth_lst = birth_df.values.tolist()
birth_lst = []
for i in range(0, len(_birth_lst)):
birth_lst.append(float(_birth_lst[i][0]))
print(sorted(birth_lst))3-3. 세트를 direct access array set에 넣어라.
(해당 문제는 방법을 찾기 힘들어 chatgpt의 도움을 받은 코드입니다.)
birth_arr = [None] * len(birth_lst)
for i in range(len(birth_lst)):
birth_arr[i] = birth_lst[i]
print(birth_arr)3-4. 사이즈를 비교하여라.
unordered array set, oredered array set, direct access array set 모두 사이즈 100이 나온다.
3-5. 인터페이스 비교: build, find, insert, delete, find_min, find_max, find_next, find_prev. (강의자료 참고)
대학생