1-2) DS 정리

C++

* : 참조 연산자

사용법 :

& : 주소 연산자

사용법 :

Swap functions 결과값 예측하기

Sorting 알고리즘과 시간 복잡도

ex) insertion sort

알고리즘 분석 2강 참고

step

프로그램 step은 프로그램의 구문적으로 의미 있는 부분을 말함

insertion의 step count 예시 :

3×(n-1)+2×((n-1)n/2) = n^2+3n-4

Asymptotic Complexity : 점근적 복잡도

→ 코드 주어지고 시간복잡도 구하는 문제 나옴(24)

증명 (답 제출 시 그대로 써야함)

Common Growth Rate Functions

1. 1 (constant): growth is independent of the problem size n.
2. log₂N (logarithmic): growth increases slowly compared to the problem size (binary search)
3. N (linear): directly proportional to the size of the problem.
4. N * log₂N (n log n): typical of some divide and conquer approaches (merge sort)
5. N² (quadratic): typical in nested loops
6. N³ (cubic): more nested loops
7. 2ⁿ (exponential): growth is extremely rapid and possibly impractical. → 시험에 단답형으로 나왔음(24)

Math Symbols

Recursive Functions

최댓값을 구한 뒤 그 값을 제외한 값 중 최댓값을 찾도록 재귀적으로 호출하는 함수

Binary Search

• 리스트의 중앙값을 확인하는데 𝚯(1)의 시간 소요
• 목표 값이 아닐 경우 나머지 절반을 탐색하므로 크기가 n에서 n-1/2로 줄어든다.

→ 이거 비슷하게 재귀식 주어지고 증명하는 문제 출제됨(24)

데이터 구조 개념

Data Object (데이터 객체)

• a set of instances or values
• 인스턴스(값)들의 집합
• 다양한 유형의 값을 가지고, 특정한 규칙이나 타입에 따라 정의됨

Data Structure (자료 구조)

• data object together with the relationships among instances and elements that comprise an instance
• 데이터 객체와 그 객체 내의 관계를 정의함
• 리스트, 스택, 큐, 트리 등이 있음

ADT (Abstract Data Type)

• is a collection of data and a set of operations that can be performed on the data
• 데이터의 집합과 그 데이터에 적용할 수 있는 연산들의 집합
• ex) stack ADT : push, pop, peek, isempty …

Linear List(선형 리스트)

• 선형 리스트는 데이터가 순차적으로 나열된 구조로, 인스턴스가 (e1, e2, …, en) 의 형태를 가짐
• e1은 리스트의 첫 번째 요소, en은 마지막 요소 n은 요소의 개수
• 리스트에 요소가 없을 경우 empty list

#include <iostream>
#include <stdexcept>
#include <string>

using namespace std;

class OutOfBounds : public std::exception {
public:
    // 예외 메시지를 저장하는 생성자
    explicit OutOfBounds(const std::string& message = "Index out of bounds") : msg(message) {}

    // 예외 메시지를 반환하는 메서드
    const char* what() const noexcept override {
        return msg.c_str();
    }

private:
    std::string msg;
};

class NoMem : public std::exception {
public:
    explicit NoMem(const std::string& message = "No memory available") : msg(message) {}
    const char* what() const noexcept override {
        return msg.c_str();
    }
private:
    std::string msg;
};

template <class T>  // 각 매서드가 템플릿을 사용하고 있음을 명시
class LinearList {
public:
    LinearList(int MaxListSize = 10);    // 생성자 : 처음 생성될 때 호출, 리스트 초기화
    ~LinearList() { delete [] element; } // 소멸자 : 객체 삭제될 때 호출, 할당된 메모리를 해제함
    bool isEmpty() const { return length == 0; }
    int Length() const { return length; }
    bool Find(int k, T& x) const;
    int Search(const T& x) const;
    LinearList<T>& Delete(int k, T& x);
    LinearList<T>& Insert(int k, const T& x);
    void Output(ostream& out) const;
private:
    int length; //
    int MaxSize;
    T *element;
};

template<class T>
LinearList<T>::LinearList(int MaxListSize)  //생성자 정의
{
    // 배열 기반 선형 리스트의 생성자
    MaxSize = MaxListSize;
    element = new T[MaxSize];
    length = 0;
}   //시간복잡도 : O(1)

template<class T>
bool LinearList<T>::Find(int k, T& x) const //find 정의
{
    // 리스트의 k번째 요소를 찾아 x에 저장하는 함수
    if (k < 1 || k > length)
        return false;

    x = element[k - 1];
    return true;
}   //시간복잡도 :  O(1)

template<class T>
int LinearList<T>::Search(const T& x) const //search 정의
{
    // x의 위치를 찾아 반환하는 함수
    for (int i = 0; i < length; i++)  // 리스트 전체를 순회
        if (element[i] == x)           // x와 일치하는 요소를 찾으면
            return ++i;                // 위치(i + 1)를 반환
    return 0;                          // 요소를 찾지 못한 경우 0 반환
}   //시간복잡도 : O(length)

template<class T>
LinearList<T>& LinearList<T>::Delete(int k, T& x)  //delete 정의
{
    // k번째 요소가 존재하면 삭제
    if (Find(k, x)) {                  // k번째 요소가 있는지 확인
        for (int i = k; i < length; i++)  // k 이후의 요소를 앞으로 이동
            element[i - 1] = element[i];
        length--;                      // 리스트 길이 감소
        return *this;                  // 자기 자신 반환
    }
    else throw OutOfBounds();          // k가 유효하지 않으면 예외 발생
}   //시간복잡도 : O((length-k)s)

template<class T>
LinearList<T>& LinearList<T>::Insert(int k, const T& x) //insert 정의
{
    // k번째 요소 이후에 x를 삽입하는 함수
    if (k < 0 || k > length) throw OutOfBounds(); // 유효한 범위 확인
    if (length == MaxSize) throw NoMem();         // 메모리 부족 시 예외 발생

    for (int i = length - 1; i >= k; i--)         // 요소들을 오른쪽으로 이동
        element[i + 1] = element[i];

    element[k] = x;                               // k번째 위치에 x 삽입
    length++;                                     // 리스트 길이 증가
    return *this;                                 // 자기 자신 반환 (체이닝 지원)
}   //시간복잡도 : O((length-k)s)

template<class T>
void LinearList<T>::Output(ostream& out) const  //output 정의    
{
    // 리스트의 요소들을 출력
    for (int i = 0; i < length; i++)       // 리스트 전체를 순회
        out << element[i] << " ";          // 각 요소를 출력하고 공백 추가
}   //O(length)

int main() {
    LinearList<int> intlist(5);
    LinearList<int> intlist2; //생성자 --> 설정하지 않으면 자동으로 크기가 10으로 됨
    LinearList<int>* intlist3 = new LinearList<int>(5); //동적 할당으로 생성

    cout<<intlist.isEmpty()<<endl;
    intlist.Insert(0,15); // insert 매서드
    intlist.Insert(1,20);
    cout<<intlist.isEmpty()<<endl;

    int temp;
    intlist.Find(20,temp); // find 매서드
    cout<<temp<<endl;

    intlist.Output(cout); // output 매서드

    delete intlist3; //소멸자 : 동적 할당된 리스트 소멸
}

→ find, search, delete, insert 중에 코드 빈칸 채워넣기 출제(24중간)

Linked Representation of Linear List (선형 리스트의 연결 표현)

• 각 요소는 셀이나 노드로 표현됨
• 각 노드는 다른 노드의 위치에 대한 정보를 저장하고 있음
• 다른 노드의 위치에 대한 정보는 링크 또는 포인터라고 불림

Singly Linked List (단일 연결 리스트)

• 각 요소 는 별도의 노드에 표현됨
• 각 노드는 다음 요소를 찾기 위한 링크 필드를 가지고 있음
• 마지막 노드는 다음 노드가 없기 때문에 링크 필드가 NULL이 됨

이러한 구조를 chain이라 부름

단일 연결 리스트는 다음 노드만 가리키고 있기 때문에 한 방향으로만 순차적으로 이동할 수 있음

▶

Class “Chain” 코드 설명

chain을 쓰기위해 먼저 Class “ChainNode”가 필요함

복사

c++

template <class T>
class ChainNode {
    friend Chain<T>; // Chain<T> 클래스를 friend로 선언하여 private 멤버 접근을 허용함

private:
    T data; //데이터 저장
    ChainNode<T> *link; //다음 노드를 가리키는 포인터
};

1. friend 선언 : friend class Chain<T>를 통해 Chain<T>가 ChainNode<T>의 private 멤버에 접근할 수 있게 했음
2. data : 노드가 저장하는 데이터, T 타입을 사용하여 다양한 형태의 데이터 타입을 저장할 수 있음
3. link : 다음 노드의 주소를 가리키는 포인터, 이를 통해 다른 노드와 연결됨

Class “Chain”

복사

c++

template <class T>
class Chain {
public: 
    Chain();                            // 생성자: 빈 체인을 생성
    ~Chain();                           // 소멸자: 체인을 해제
    bool isEmpty() const;               // 체인이 비어 있는지 확인
    int Length() const;                 // 체인의 길이를 반환
    bool Find(int k, T& x) const;       // k번째 요소를 찾고 x에 저장
    int Search(const T& x) const;       // 요소 x를 검색하여 인덱스를 반환
    Chain<T>& Delete(int k, T& x);      // k번째 요소를 삭제하고 x에 저장
    Chain<T>& Insert(int k, const T& x); // k번째 위치에 요소 x 삽입
    void Output(ostream& out) const;    // 체인의 내용을 출력

private: 
    ChainNode<T> *first;                // 첫 번째 노드에 대한 포인터
    int listSize;                       // 리스트의 요소 수를 저장
};

Operation “~Chain”

복사

c++

template <class T>
Chain<T>::~Chain() {
    // 체인의 길이 n에 비례하여 O(n) 시간 복잡도로 모든 노드를 삭제
    ChainNode<T> *next;
    while (first) {
        next = first->link;  // 현재 노드의 링크를 다음 노드로 설정
        delete first;         // 현재 노드를 삭제하여 메모리 해제
        first = next;         // 첫 번째 노드를 다음 노드로 이동
    }
}

Operation “Length”

복사

c++

template <class T>
int Chain<T>::Length() const {
    ChainNode<T> *current = first; // 리스트의 첫 번째 노드에서 시작
    int len = 0;                   // 리스트 길이를 저장할 변수 len 초기화
    while (current) {              // 현재 노드가 NULL이 아닐 때까지 반복
        len++;                     // 길이 증가
        current = current->link;   // 다음 노드로 이동
    }
    return len;                    // 리스트의 길이 반환
}

Operation “Find”

복사

c++

template <class T>
bool Chain<T>::Find(int k, T& x) const {
    // 리스트에 k번째 요소가 존재하면 x에 해당 값을 설정
    // 유효하지 않은 인덱스일 경우 예외를 발생시킴
    checkIndex(k); // k가 유효한 인덱스인지 확인하는 함수 (예외 처리 포함)
    
    // 원하는 노드로 이동
    ChainNode<T>* current = first;
    for (int i = 0; i < k; i++) {
        current = current->link; // k번째 노드로 이동
    }
    
    x = current->data; // 현재 노드의 데이터를 x에 할당
    return true;
}

find에 필요한 checkindex 구현

복사

c++

void Chain<T>::checkIndex(int Index) const {
    // Index가 0 이상 listSize-1 이하인지 확인
    if (Index < 0 || Index >= listSize) {
        std::ostringstream s;
        s << "index = " << Index << " size = " << listSize;
        throw illegalIndex(s.str()); // 예외를 발생시키며 인덱스 오류 메시지를 포함
    }
}

Operation “Search”

복사

c++

template <class T>
int Chain<T>::Search(const T& x) const {
    // x의 위치를 찾고, 찾으면 위치를 반환하고, 찾지 못하면 -1 반환
    ChainNode<T>* current = first;
    int index = 0; // 현재 노드의 인덱스

    // 리스트에서 x를 찾기 위한 탐색 루프
    while (current != NULL && current->data != x) {
        current = current->link; // 다음 노드로 이동
        index++; // 인덱스 증가
    }
    // 매칭되는 요소가 발견되었는지 확인
    if (current == NULL)
        return -1; // 요소를 찾지 못한 경우 -1 반환
    else
        return index; // 요소를 찾은 경우 인덱스 반환
}

Operation “Delete”

ex) 4번쨰 노드를 지우기 위해서는 3번째 노드의 포인터를 5번째 노드로 바꿔줘야함

복사

c++

template <class T>
void Chain<T>::erase(int theIndex) {
    // 인덱스가 유효한지 확인
    checkIndex(theIndex); // theIndex가 유효한지 확인하고 유효하지 않으면 예외를 던짐

    ChainNode<T>* deleteNode;

    if (theIndex == 0) {
        // 첫 번째 노드를 삭제하는 경우
        deleteNode = firstNode;
        firstNode = firstNode->next;
    } else {
        // 삭제할 노드의 이전 노드를 찾음
        ChainNode<T>* p = firstNode;
        for (int i = 0; i < theIndex - 1; i++) {
            p = p->next;
        }
        // 삭제할 노드 지정 및 체인에서 제거
        deleteNode = p->next;
        p->next = p->next->next;
    }

    listSize--; // 리스트 크기 감소
    delete deleteNode; // 노드 메모리 해제
}

→ Delete 함수에 빈칸 여러 개 뚫어놓고 채우기 출제(24 중간) (ex : p→next)

Circular List Representation(원형 리스트 표현)

팀섹 속도를 높이고, 단순화하기 위해 원형 리스트를 사용함

1. 단일 연결 원형 리스트로 표현

• 원형 리스트에서는 마지막 노드가 첫 번째 노드를 가리키도록 연결되어 리스트의 끝과 시작이 연결되며 원형 구조가 만들어짐
• 원형 리스트는 순환 패턴이 자주 사용되는 프로그램의 성능을 향상시킴

1. 헤드 노드 추가

• 리스트 앞에 별도의 헤드 노드를 추가하면 삽입이나 삭제 같은 연산을 일관되게 수행하여 프로그램의 구현이 단순해짐
• 헤드 노드는 데이터는 없고, 리스트의 첫 번째 요소로 가는 링크만 가짐

Doubly Linked List (이중 연결 리스트)

• 각 노드가 두 개의 포인터 (왼쪽과 오른쪽)를 가짐
• 왼쪽 포인터는 이전 노드를 가리킴
• 오른쪽 포인터는 다음 노드를 가리킴
• 주로 양방향 순회가 필요한 경우 사용됨

장점 :

• 양방향 탐색이 가능하여, 리스트의 중간에서 앞과 뒤로 이동이 용이함
• 삽입 및 삭제가 양쪽에서 이루어질 수 있어, 단일 연결 리스트보다 특정 작업에서 유리할 수 있음

template <class T>
class DoubleNode {
    friend class Double<T>; // Double<T> 클래스가 DoubleNode<T>의 private 멤버에 접근할 수 있도록 허용
private:
    T data;                  // 노드에 저장할 데이터
    DoubleNode<T> *left;     // 이전 노드를 가리키는 포인터
    DoubleNode<T> *right;    // 다음 노드를 가리키는 포인터
};

template <class T>
class Double {
public: 
    Double() { LeftEnd = RightEnd = nullptr; } // 생성자: 리스트를 비어 있는 상태로 초기화
    ~Double();                                 // 소멸자: 리스트의 모든 노드를 해제
    int Length() const;                        // 리스트의 길이를 반환
    bool Find(int k, T& x) const;              // k번째 요소를 찾아 x에 저장
    int Search(const T& x) const;              // 요소 x를 검색하여 인덱스를 반환
    Double<T>& Delete(int k, T& x);            // k번째 요소를 삭제하고 x에 저장
    Double<T>& Insert(int k, const T& x);      // k번째 위치에 요소 x를 삽입
    void Output(ostream& out) const;           // 리스트의 내용을 출력

private: 
    DoubleNode<T> *LeftEnd;                    // 리스트의 첫 번째 노드를 가리키는 포인터
    DoubleNode<T> *RightEnd;                   // 리스트의 마지막 노드를 가리키는 포인터
};

1차원 배열

C에서 했을거라 생각하고 넘어감

2차원 배열

row와 column이 있는 배열

2차원 배열이 int a[3][4]; 와 같이 선언된 경우 표 형태로 나타낼 수 있음

2차원 배열을 1차원 배열로 표현하기

이차원 배열 x가 다음과 같을 때

이 배열을 row 단위로 1차원 배열로 표현할 수 있음

x = [row0, row1, row2]
row0 = [a, b, c, d]
row1 = [e, f, g, h]
row2 = [I, j, k, l]

space overhead : 추가적인 메모리 소모

• 이러한 표현 방식을 array-of-arrays라고 함
• 4개의 1차원 배열에 각각 3, 4, 4, 4 크기의 연속된 메모리가 필요함
• 이 구조는 1개의 메모리 블록과 row 수만큼의 column 크기의 블록들로 구성됨

x를 1차원 배열 y로 변환하기

y[] = {a, b, c, d, e, f, g, h, i, j, k, l}

• r개의 행과 c개의 열이 있을 경우 x[i][j] 를 찾기 위해서는 1차원 배열의 i * c + j 번째 인덱스에 접근해야 함
• 따라서 y[ i * c + j ]라고 할 수 있음
• 행(row) 우선은 i * 열(column) 개수 + j로 계산 열(column) 우선은 i * 행(row) 개수 + j로 계산

→ 배열 90도 돌리는 알고리즘 생각해보기 (24중간)

Question 1. True or False

1) A private method may be invoked from outside of the class.

2) Public variable violate encapsulation.

3) Methods (or functions) must have unique names.

4) Methods (or functions) must have unique signatures.

Question 2. Short Answer

1) What is a data structure?

2) What is an abstract data type?

Question 3. Definition

1) Big-Oh (O) notation

2) Theta (θ) notation

Question 4. Frequency Analysis

1) Insertion Sort Frequency

Question 5. Growth Rate Hierarchy & Time Complexity

1) Growth Rate Hierarchy

2) Insertion sort worst-case time complexity

3) Binary Search worst-case time complexity

4) Given code time complexity

Question 6. Prove T(n) = n³ + 20n + 1 is not O(n²)

▶

답

Question 7. Chain Erase Function

Stack

1. 기본 개념

• 정의: 선형 리스트의 특수한 형태
• 구조:
  • 한쪽 끝은 top (삽입/삭제가 일어나는 곳)
  • 다른 끝은 bottom
• 특징: LIFO (Last-In, First-Out) - 마지막에 들어간 것이 먼저 나옴

2. 스택 ADT (Abstract Data Type)

empty() // 스택이 비어있는지 확인
size() // 스택의 원소 개수 반환
top() // 맨 위 원소 반환
pop() // 맨 위 원소 제거
push(x) // 맨 위에 원소 x 추가

3. 스택 구현 방법

배열 기반 구현 (Array-based)

• element[0] = bottom
• element[length-1] = top
• 장점: 간단한 구현
• 단점: 크기가 고정됨, 여러 스택 사용 시 공간 낭비

연결 리스트 구현 (Linked List)

• 중요: 체인의 왼쪽 끝을 top으로 사용 → O(1) 시간 복잡도 (start 앞에 새로운 노드 생성)
• 오른쪽 끝을 top으로 사용하면 → O(n) 시간 복잡도 (비효율적 : 새로운 값이 들어 올 때 마다 맨 뒤의 노드를 추적해야 함)

4. 상속과 파생 클래스

• Stack을 Linear List의 특수한 형태로 구현 가능
• private 상속으로 arrayList 기능 숨김
• public 상속으로 stack 인터페이스 제공

5. 응용 예제

1) 괄호 매칭 (Parenthesis Matching)

알고리즘:

1. 왼쪽에서 오른쪽으로 스캔
2. 여는 괄호 '(' 만나면 → 위치를 스택에 push
3. 닫는 괄호 ')' 만나면 → 스택에서 pop하여 매칭
   복사

   c++

   (((a+b)*c+d-e)/(f+g)-(h+j)*(k-1))/(m-n)

   

   여는 괄호 인덱스를 스택에 순서대로 저장

   닫는 괄호가 나오면 스택에서 방출

   

2) 하노이 탑 (Towers of Hanoi)

• 문제: n개의 디스크를 A탑에서 C탑으로 이동
• 제약:
  • 한 번에 하나씩만 이동
  • 큰 디스크는 작은 디스크 위에 올 수 없음

재귀적 해결법:

1. n-1개를 A → B로 이동 (C를 보조로 사용)
2. 가장 큰 디스크를 A → C로 이동
3. n-1개를 B → C로 이동 (A를 보조로 사용)

시간 복잡도:

• 최소 이동 횟수: 2ⁿ - 1

Queue

1. 기본 개념

• 정의: 선형 리스트의 특수한 형태 (스택과 유사하지만 동작 방식이 다름)
• 구조:
  • 한쪽 끝은 front (삭제가 일어나는 곳)
  • 다른 끝은 rear/back (삽입이 일어나는 곳)
• 특징: FIFO (First-In, First-Out) - 먼저 들어간 것이 먼저 나옴

2. 큐 ADT (Abstract Data Type)

empty() // 큐가 비어있는지 확인
size() // 큐의 원소 개수 반환
front() // 맨 앞 원소 반환
back() // 맨 뒤 원소 반환
pop() // 맨 앞 원소 제거 (dequeue)
push(x) // 맨 뒤에 원소 추가 (enqueue)

3. 큐 구현 방법

1) 단순 배열 구현의 문제점

• location(i) = i - 1 사용 시
• front = 0, rear = 마지막 원소 위치
• 문제: pop() 연산 시 모든 원소를 왼쪽으로 이동 → O(n) 시간!

2) 개선된 배열 구현

• location(i) = location(1) + i - 1
• front와 rear 포인터를 이동시켜 원소 이동 없이 구현
• 문제: rear가 배열 끝에 도달했을 때 처리 필요

3) 원형 큐 (Circular Queue)

가장 효율적인 배열 기반 구현:

location(i) = (location(1) + i - 1) % Maxsize

원형 큐의 특징:

• 배열을 원형으로 간주
• front: 첫 번째 원소의 한 칸 앞 위치
• rear: 마지막 원소의 위치
• 시계방향 이동: (index + 1) % arrayLength

빈 큐 vs 가득 찬 큐 구분 문제:

• 문제: front == rear일 때, 빈 큐인지 가득 찬 큐인지 구분 불가

해결 방법 :

1. 배열 크기를 동적으로 증가시키기
2. 2. boolean 변수 사용
3. 카운터 변수 사용

원형 큐에 대한 보충 자료이다.

핵심 내용

1. 배열 용량 증가 전략
   1. 상수 만큼 증가

      

      • array_capacity += c
      • 문제점 : n개 삽입 시 총 복사 횟수 = O(n²)
      • amortized : 각 push마다 O(n) 시간 소요
   2. 배로 증가

      

      • array_capacity *= 2
2. 배열 용량 증가 구현 (배로 증가
   복사

   c++

   void double_capacity() {
       // 1. 새 배열 할당
       Type *tmp_array = new Type[2*array_capacity];
       
       // 2. 기존 데이터 복사
       for (int i = 0; i < array_capacity; ++i) {
           tmp_array[i] = array[i];
       }
       
       // 3. 기존 배열 삭제
       delete [] array;
       
       // 4. 포인터 업데이트
       array = tmp_array;
       array_capacity *= 2;
   }

   Abstract Queue

   Also called a first-in–first-out (FIFO) data structure

   

   문제 상황 :

   

   배열이 가득 차지 않았는데 Back에 값을 더 이상 넣을 수 없어..

   해결책 : 원형 배열

   복사

   c++

   void push(T element) {
       back = (back + 1) % capacity;
       array[back] = element;
   }
   
   // 위 상황에서는 
   back = (15 + 1) % 16;

Hashing

Dictionary

Definition :

• ( key, value )의 집합
• 모든 키는 distinct 해야 함

Accessing Elements :

• Random Access : key로 직접 접근
• Sequential Access : key 순서대로 조회
  • begin(): 가장 작은 key
  • next(): 다음 원소

Dictionary 예시 :

Dictionary 구현 방법 :

• Linear List로 구현
  • L = (e1, e2, e3, …, en)
  • Each e is a pair (key, value)
• Array or chain representation
  • unsorted array: O(n) search time
  • sorted array: O(logn) search time
  • unsorted chain: O(n) search time
  • sorted chain: O(n) search time
• 문제점 : 모두 선형, 또는 로그 접근 시간

Hash Table

핵심 아이디어

"key를 배열 인덱스로 직접 변환하자"

key → hash function → index
80  →    f(k) % 8   →   0

이상적인 경우

pair (key, value) 저장 위치 = f(key)
→ 모든 연산이 O(1)

hashing example

Step 1 :

(22, a) 삽입

f(22) = 22 % 8 = 6
[0] [1] [2] [3] [4] [5] [6]   [7]
                        (22,a)
 
	 // 6번 bucket에 저장

…

결과

[0]    [1]   [2]   [3]   [4]   [5]   [6]   [7]
(72,e) (33,c)      (3,d)       (85,f) (22,a)

여기에 (25, g)를 넣어보자.

(33, c)의 자리에 들어가야 한다.

→ collision 발생

Hash Function

Step 1 : Key → Integer

Step 2 : Integer → Bucket Index

Binary Trees

개념

• Linear Lists : 순차적으로 정렬된 데이터
• Trees : 계층적으로 정렬된 데이터

정의

• Tree : 유한하고, 비어있지 않은 원소들의 집합
  • 하나의 원소 : root
  • 나머지 원소 : 트리들로 분할됨

용어

• Root: 계층 구조의 최상위 원소
• Children: 루트의 바로 아래 계층 원소들
• Leaves: 최하위 계층 원소들 (자식이 없는 노드)
• Level: 루트는 level 1, 그 자식들은 level 2...
• Height/Depth: 레벨의 수

Question 1. True or False

1) What is the difference between a queue and a priority queue?

2) What is the definition of a min tree?

3) What is the definition of a max heap?

Question 2. Prove

1) The drawing of every binary tree with n elements, n > 0, has exactly n-1 edges.

2) A binary tree of height h, h ≥ 0, has at least h and at most 2ʰ-1 elements in it.

증명 문제 → 연습문제와 거의 똑같이 나옴

트리 순회 결과값 작성 → 3가지 방식 모두 연습하기

허프만 코드 → 연습문제와 똑같이 (숫자만 바꿔서 나옴)

binary tree C++ 구현 코드 작성하는 문제

해싱 (키로 적합한 숫자가 뭐냐), 왜 적합한지 설명하기

원형 큐, 머리와 꼬리를 어디에 놓는게 좋은지 설명하기

mod 써서 해싱 직접 하는 문제 → 나눈 나머지 같은거끼리 정리

1. Question: Define a full (perfect) binary tree and a complete binary tree. How do they differ?
   ▶

   답

   Answer:

   A full (perfect) binary tree is one in which all internal nodes have exactly two children and all leaves are at the same level; such a tree of height ‘h’ has exactly 2ʰ - 1 nodes. A complete binary tree is one in which all levels are completely filled except possibly the last, and the last level has all nodes as far left as possible. The difference is that a full tree is perfectly balanced at every level, while a complete tree only requires all but the last level to be filled

2. Question: What is the effect of performing a left shift (<<) by k on an unsigned integer x? Describe its arithmetic effect. (result does not overflow.)
   ▶

   답

   Shifting an unsigned integer x left by k bits effectively multiplies x by 2ᵏ.

3. Question: Which tree traversal of a BST will list the keys in ascending order?
   ▶

   답

   An inorder traversal