Table of Contents
할 일
교수님이 이 부분을 읽을지 안 읽을지 모르겠지만 문제 좀만 더 자세하고 뚜렷하게 써주면 좋겠다. 1번 문제에서 (n + 1)이 2의 거듭제곱이 아닐 때 소수점은 어떻게 하는거고(내가 모르는 것일 수도 있음), 코드는 파이썬으로 보여주면서 unordered set 라이브러리는 파이썬에 없는데 이걸 이름만 말해줄 거면 어떤 언어에 있는 라이브러리인지 구분 좀 해주고(C++에 있는거 찾았음), 생일 데이터셋을 각 데이터 구조에 넣어보는건 알겠는데 무엇의 크기를 비교하라는 건지도 모르겠다. 아니 지난 학기에 다른 과목 과제 낼 때는 이렇게 문제 못알아보게 안 냈잖아요 한 학기 사이에 무슨 일이 있었던 거임
수업 진행 상황을 고려하여 몇 가지 숙제 문제는 제외되었습니다.
8장 읽기. → 아직 다 안읽었음
- n 노드에 있는 모든 트리의 가장 작은 높이는 Ω(lg n) = -1 + lg(n+1)임을 증명합니다.
- 직접 액세스 배열의 공간을 축소할 때, 링크드 리스트 데이터 구조를 사용하고 싶을 수 있습니다. 연결된 목록을 사용하면 어떤 문제가 발생할까요? 시간 복잡성을 설명하면서 답을 보여주세요.
- 해시 패밀리 함수에서 a는 0과 같지 않아야 하는데, 왜 그럴까요? 간단한 답(한 문장)을 제시해 주세요.
- 생일 데이터셋을 사용하여 다음을 수행하십시오:
- set을 사용하여 정렬되지 않은 배열에 넣습니다. (unordered set 라이브러리)
- 정렬된 배열 set에 넣습니다.
- 직접 액세스 배열 set에 넣습니다.
- 해시 테이블 set에 넣습니다.
- 크기를 비교합니다.
- build, find, insert, delete, find_min, find_max, find_next, find_prev 등 인터페이스를 비교합니다.
트리의 최소 높이
문제: n 노드에 있는 모든 트리의 가장 작은 높이는 Ω(lg n) = -1 + lg(n+1)임을 증명합니다.
문제에는 안 써있지만 설마 밑이 10인 로그일 리는 없고 이진트리 말하는 거겠지? 한쪽으로 몰린 트리 그리면 의미 없으니까 거의완전이진트리 말하는 거겠지? 내가 할 줄 아는 건 숫자 넣어보고 규칙 찾는 거밖에 없으니 그걸로 해보겠다.
그리고 (n + 1)이 2의 거듭제곱이 아니면 소수가 나올텐데 소수점은 어떻게 하는지도 안 써있는데 이건 내가 모르는 거냐 아님 문제가 뭔가 부족한 거냐
n = 1: 노드가 1개면 루트와 리프가 같지. log(n+1) - 1 = 0이니까 트리의 높이는 0부터 세는 것 같네. (이산수학 배울 때 트리의 높이는 1부터 세는 것으로 배웠으나 간혹 0부터 세기도 한다고 했음)n = 2: 노드가 2개이고, 이진트리라면 루트 1개, 리프 1개로 이루어진 트리일 거야.
그럼 최소 높이는 1 아니냐?(아님)
chatGPT한테 트리 높이 어떻게 세냐고 물었더니 루트에서 리프로 가는 거리니까 루트가 리프랑 같은 노드라고 간주해서 최소 높이가 0이래. log(2+1)은 1보다 크고 2보다 작으니까 log(3) - 1 = 0.XX이므로 소수점은 버린다고 생각하면 성립하긴 하지.2 ≤ n < 3:1 < log(n + 1) < 2가 되므로 Ω(log n)은 0과 1 사이이다. 자세한 내용은 2번과 겹친다.3 ≤ n < 7: 높이마다 들어가는 노드의 수는 1, 2, 4, … 순서대로 2의 거듭제곱이므로 이 범위의 n이라면 완전이진트리라고 할 때, 높이는 1에서 2이다. 식에 대입하면2 ≤ log(n + 1) < 3이므로 Ω(log n)은 1 이상 2 미만이다. 성립.2^k - 1 ≤ n < 2^(k+1) - 1(k는 0 이상의 정수): 층마다 들어가는 노드의 개수는 초항이 1이고 공비가 2인 등비수열로 볼 수 있다. 트리의 높이를 h라고 할 때, 트리의 높이에 따른 노드의 개수 범위는 등비수열의 합 공식을 이용해 다음과 같이 나타낼 수 있다.
1*(2^(h - 1) - 1)/(2 - 1) < n ≤ 1*(2^h - 1)/(2 - 1)
이제 이 식을 정리해 h를 구하면 된다.
식에 영향을 주지 않는 1을 다 없애면 식은2^(h - 1) - 1 < n ≤ 2^h - 1이 되고, 앞뒤의-1을 이항하면2^(h - 1) < n + 1 ≤ 2^h가 된다. 여기에 log를 취하면h - 1 < log(n + 1) ≤ h가 된다. 이제 이 식을 h로 다시 정리하면log(n + 1) ≤ h < log(n + 1) + 1이 된다.- 식이 대충 답이랑 비슷하게 오긴 했는데 저게 어떻게
log(n+1) - 1이 되는지는 모르겠다.
chatGPT 풀이
* chatGPT 답변 일부 발췌
노드 수가 n인 이진 트리의 최소 높이를 찾기 위해서는, 먼저 가능한 한 최대한 많은 노드가 리프 노드가 되도록 만들어야 합니다. 이진 트리의 높이가 작을수록, 즉 리프 노드로부터 루트 노드까지 거리가 짧을수록, 노드 수가 적은 상태에서도 많은 수의 리프 노드를 만들 수 있습니다.
노드 수가 n인 이진 트리의 높이를 H라고 하면, 리프 노드의 개수는 최소 1개부터 최대 2^H개까지 가능합니다. 따라서, n개의 노드를 가진 이진 트리의 높이 H는 다음과 같은 식으로 표현할 수 있습니다.
1
2
n ≤ 1 + 2 + 4 + ... + 2^H
= 2^(H+1) - 1
이를 H에 대해 풀어서 정리하면,
1
H ≥ log(n+1) - 1
따라서, 이진 트리의 높이와 노드 수 사이의 관계는 H = Ω(lg n)이 됩니다. 따라서, 노드 수가 n인 이진 트리의 최소 높이는 Ω(lg n)입니다.
연결 리스트의 문제
문제: 직접 액세스 배열(direct access array)의 공간을 축소할 때, 링크드 리스트 데이터 구조를 사용하고 싶을 수 있습니다. 연결된 목록을 사용하면 어떤 문제가 발생할까요? 시간 복잡성을 설명하면서 답을 보여주세요.
direct access array가 뭔지부터 알아야 문제를 풀겠다. 구글에 검색하면 Direct Access Table만 나오는데, 간단히 요약하면 숫자로 된 키와 데이터를 담는 값으로 이루어진 테이블인데, 키가 곧 배열의 인덱스로 사용되는 것이다.
연결 리스트로 공간을 축소한다는 말이 예를 들면 100칸 배열을 각 칸이 10개씩 연결 리스트를 갖는 10칸 배열로 축소하겠다는 뜻이라면 공간을 축소했다고 할 리는 없고, 배열에 들어간 요소들을 모두 연결 리스트에 넣겠다는 뜻이겠지?(chatGPT에게 공간 축소가 무슨 뜻이냐고 물어봤음)
직접 액세스 배열과 연결 리스트의 가장 큰 차이는 인덱스 사용 여부이다. 직접 액세스 배열은 메모리를 포기하고 시간을 확보하는 방식으로 삽입, 삭제, 검색 연산이 모두 O(1)이다. 연결 리스트는 이와 달리 인덱스를 사용할 수 없어 삽입, 삭제 연산을 할 때에도 검색 연산을 먼저 해야 하고, 검색 연산은 선형으로 데이터를 순회하므로 O(n)이다. 삽입과 삭제 연산은 포인터만 이동하면 되므로 O(1)이라 O(n)에 영향을 주지 않는다.
정리하면 메모리는 절약할 수 있지만 검색을 비롯한 각종 연산의 시간이 O(1)에서 O(n)으로 늘어난다. 넓은 범위의 소수 데이터라면 메모리를 절약하는 게 낫지만 좁은 범위의 대량 데이터라면 손해다.
생일 데이터 집합 활용
생일 데이터셋을 사용하여 다음을 수행하십시오:
- set을 사용하여 정렬되지 않은 배열에 넣습니다. (C++ unordered set 라이브러리)
- 정렬된 배열 set에 넣습니다.
- 직접 액세스 배열 set에 넣습니다.
- 해시 테이블 set에 넣습니다.
- 크기를 비교합니다. (X) -> 뭘 하라는건지 몰라서 안 함
- build, find, insert, delete, find_min, find_max, find_next, find_prev 등 인터페이스를 비교합니다.
| 데이터 구조 | build | find | insert | delete |
|---|---|---|---|---|
| unordered array using set | O(n) | O(n) | O(1) | O(1) |
| sorted array set | O(n log n) | O(log n) | O(log n) | O(log n) |
| direct access array | O(n) | O(1) | O(1) | O(1) |
| 데이터 구조 | find_min | find_max | find_next | find_prev | 특이사항 |
|---|---|---|---|---|---|
| unordered array using set | O(n) | O(n) | ? | ? | rehash O(n) |
| sorted array set | O(1) / O(n) | O(n) / O(1) | O(log n) | O(log n) | |
| direct access array | O(1) ~ O(n) | O(1) ~ O(n) | O(1) ~ O(n) | O(1) ~ O(n) |
unordered array using set
참고 자료 [4]에 의하면 unordered set은 해시로 구현되었기 때문에 삽입과 검색 연산이 평균적으로 O(1)로 수행된다. 물론 우연히 해시가 겹치면 O(n)이 될 수도 있긴 하다고 한다.
그리고 삽입되는 요소의 수에 따라 공간을 더 크게 할당해 모든 원소를 다시 정리하는 rehash 연산도 필요할 때가 있는데, 이 연산은 O(n)만큼 걸린다.
최댓값이나 최솟값을 찾고자 할 때는 모든 요소를 순회해야 하기 때문에 O(n)이다. 그리고 해시로 구현되었으므로 바로 앞 요소나 뒤 요소를 찾는 방법은 나도 모르겠다. chatGPT에게도 물어봤는데 해시로 구현된 컨테이너에서 앞뒤 원소를 찾는 것은 어렵다는 답변이 왔다.
sorted array set
참고 자료 [4]에 의하면 sorted set은 트리로 구현되었다. 그러므로 삽입, 검색 연산 등은 트리의 연산 수행 시간을 따라간다. 중복을 허용하는 multiset도 트리로 구현되는 것은 마찬가지라고 한다. [참고 자료 5]
최댓값이나 최솟값은 트리의 정렬 기준에 따라 각각 O(1)과 O(n)으로 수행 가능하고, 특정 원소의 바로 앞이나 뒤를 찾는 연산은 검색 연산과 같다.
direct access array
참고 자료 [3]에 의하면 직접 액세스 배열은 키가 곧 배열의 인덱스가 되는 자료구조이다. 그러므로 중복을 허용하지 않는다는 전제 하에 삽입과 삭제, 검색 연산이 모두 O(1)이다.
그러나 chatGPT의 설명에 따르면 이름 그대로 직접 접근하는 것이 아닌 연산은 데이터의 크기에 따라 비효율적으로 하게 될 수 있다. 배열의 길이가 길지 않고, 요소가 충분히 채워져 있다면 최댓값이나 최솟값은 O(1)에도 가능하지만, 배열의 크기가 크고, 빈 칸이 많다면 모든 원소를 확인해야 하므로 O(n)이다.
짐작해보건대, 특정 원소의 바로 앞이나 뒤 원소를 찾는 연산도 마찬가지로 O(1) ~ O(n)일 거라고 생각했는데, chatGPT가 직접 액세스 배열로 이진 탐색을 수행하면 된다고 했다. 그럼 O(log n)이다. 다만 이것은 요소가 정렬되었다는 것을 전제로 하기 때문에, 삽입과 삭제 연산을 O(1)로 수행하는 직접 액세스 배열이라면 내 생각이 맞을 것 같다.
참고 자료
- chatGPT와 대화하기, https://chat.openai.com/chat
- 등비수열의 합, 등비수열의 합 공식, https://mathbang.net/612#gsc.tab=0
- Direct Access Table과 Hash Table, https://dttmmit.tistory.com/85
- 씹어먹는 C++ - <10 - 2. C++ STL - 셋(set), 맵(map), unordered_set, unordered_map>, https://modoocode.com/224
- [C++ STL] Set, Multiset, https://dobby-the-house-elf.tistory.com/10