자료구조

• 데이터를 효율적으로 조직하는 방법
• 프로그램의 성능이 수십, 수백배 차이날 수 있다.

-연산

> 읽기 / 검색 / 삽입 / 삭제

• 선형자료구조

    > 리스트 : 순서를 갖고 있는 자료구조
        > 선형 리스트
            > 검색 : O(n)
            > 읽기 : O(1) 임의 접근이 가능 연속적으로 있기에 주소연산을 통해 원하는 값을 바로 찾아갈 수 있다.
            > 삭제 / 삽입 : 맨 뒤 O(1), 그 이외 O(n)
        > 연결 리스트
            > 단일연결리스트 : 한방향으로 연결되어있음
            > 원형연결리스트 : 시작과 끝이 연결되어있음
            > 이중연결리스트 : 양방향으로 연결되어있음
            > 검색 : O(n)
            > 읽기 : O(n)
            > 삭제 / 삽입 : 위치를 알면 O(1)
    > 스택 : LIFO
    > 큐 : FIFO
- 비선형자료구조
    > 그래프 : 관계를 나타내는 자료구조
        > 순회 : 한 정점에서 그래프의 모든 정점을 방문하는 것
            > DFS : 스택 / 재귀
            > BFS : 큐
    > 트리 : 그래프의 일종으로 방향이 있고 사이클이 없는 **계층형 자료구조** (상하 관계가 있을 때 사용하면 좋다)
        > 노드 : 데이터가 저장되어있는곳
        > 간선 : 노드 간 관계

        > 루트(Root) 노드 : 트리의 시작지점
        > 단말(Leaf) 노드 : 트리의 끝에있는 노드

        > 부모(Parent) 노드 : 두 연결되어 있는 노드 중 부모격 노드
        > 자손(Child) 노드 : 두 연결되어 있는 노드 중 자손격 노드
        > 형제(Sub) 노드 : 같은 레벨에 있는 노드

        > 조상(Ancestor) 노드 : 한 노드에서 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드까지
        > 자손(Descendant) 노드 : 조상 노드의 반대
        > 차수(Degree) : 한 노드가 가지는 서브 트리의 수. 노드의 차수 중 최댓값을 트리의 차수라 한다.
        > 내부(Internal) 노드 : 단말 노드를 제외한 나머지 노드
        > 포레스트(Forest) : 트리의 집합

        > 순회
            > 전위 순회 : 루트노드를 먼저 방문하고 자식 노드를 순서대로 방문. 보통 왼쪽부터 간다. 깊이 우선탐색(DFS)과 같다.
            > 중위 순회 : 자기 자신을 중간에 방문(왼쪽을 돌았으면 나를 방문 후 오른쪽으로 간다.)
            > 후위 순회 : 맨 뒤에 루트노드가 방문된다.(왼쪽에 있는 자식노드를 먼저방문 후 오른쪽에 있는 자식노드를 방문 후 본인노드를 방문)
            > 레벨 순회 : 너비 우선 탐색과 같다(BFS)

        > 이진 검색 트리 : 한 노드(본인)를 기준으로 왼쪽서브 드리는 모두 그 노드(본인)보다 작은 값을 가지고 있으며, 오른쪽 서브 트리는 모두 그 노드(본인)보다 큰 값을 가지고 있는 이진 트리(트리의 차수가 2 이하) 이다.
        STL에 구현되있는 모든 트리 컨테이너는 모두 이진 검색 트리다.
        이진 검색 트리를 중위 순회하면 정렬된 데이터를 얻을 수 있다.

        > 힙 : 트리의 일종 (완전 이진 트리) 배열로 구현한다.
            > 마지막 노드를 제외하고 모든 레벨이 완전히 채워져있는 트리
            > 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해 만든 자료구조

                > 최대 힙 : 가장 큰 노드를 찾기 위한 힙
                > 최소 힙 : 가장 작은 노드를 찾기 위한 힙(우선순의 큐 라고도 한다)

            > 힙의 불변성 : 최대 / 최소 원소에 즉각적으로 접근이 가능해야 한다. 그래서 최대 / 최소 원소는 항상 트리의 루트에 존재해야 함.
            부모 노드가 두 자식 노드보다 항상 크거나 작아야 한다.

            > 연산
                > 검색 및 읽기 : 최대 / 최소 원소에 대해서만 가능하며 O(1) 이다.
                > 삽입 : 완전 이진 트리이기 때문에 O(logN) 이다.
                > 삭제 : 최대 / 최소 원소에 대해서만 가능하며 O(logN) 이다.

            > 연결자료구조로 접근
                > int p = 1; // 루트 노드는 1번에 저장
                p = p * 2 // 왼쪽 자식 접근
                p = p * 2 + 1 // 오른쪽 자식 접근

    > 해시 테이블 : 검색만을 위한 자료구조 (해싱과 선형 자료구조의 특징을 이용해 가져옴)unordered
        > 선형리스트의 읽기 연산은 O(1) 이다. 그리고 해싱을 이용해 구하자.

        > 해싱 : 어떤 입력이 주어지든 고정된 길이의 출력으로 바꾸는 것
        입력의 크기에 상관 없이 일정 크기의 값으로 변환하는 것. 
        이에 사용되는 함수를 해시 함수라고 한다.
            > 균일성 : 충돌이 적은 것을 의미한다.
                > 충돌 : 서로 다른 값이 같은 해시 값을 생성한 것
            > 효율성 : 계산하기 쉬워야 한다.
            > 결정적 : 같은 입력에는 같은 값을 내놓아야 한다.
        > 해시 테이블 : 해싱을 활용해 데이터를 저장하는 검색을 위한 자료구조. 
        연관 배열 이라고도 한다. **해시값을 테이블의 인덱스로 활용한다.**
        > 충돌 처리 
            > 체이닝 : 충돌이 나면 리스트로 여러 값을 저장하게 한다.f
            > 선형 개방 주소법 or 선형 조사법 : 충돌이 나면 빈 곳을 찾아서 넣는다.

        > 연산
            > 검색, 삽입, 삭제, 읽기 : O(1) 이지만 검색만을 위해 쓰인다.

        #include <unordered_map>
        #include <string>
        #include <iostream>

        enum Gender { MALE, FEMALE };

        struct Student
        {
            bool IsOnGlasses;
            Gender Gender;
            bool IsCodingGosu;
            int Age;
        };

        using namespace std;

        ostream& operator<<(ostream& oss, const Student& student)
        {
            oss << "----------------------------------\n";
            if (student.IsOnGlasses)
            {
                oss << "이 학생은 안경을 썼습니다.\n";
            }
            else
            {
                oss << "이 학생은 안경을 쓰지 않았습니다.\n";
            }

            if (student.Gender == MALE)
            {
                oss << "이 학생은 남자입니다.\n";
            }
            else
            {
                oss << "이 학생은 여자입니다.\n";
            }

            if (student.IsCodingGosu)
            {
                oss << "이 학생은 코딩 고수입니다.\n";
            }
            else
            {
                oss << "이 학생은 코딩 하수입니다.\n";
            }

            oss << "이 학생의 나이는 " << student.Age << "살 입니다.\n";
            oss << "----------------------------------\n";
            
            return oss;
        }

        int main()
        {
            unordered_map<string, Student> hashTable;

            hashTable["최서연"] = { false, FEMALE, true, 22 };
            hashTable["김동현"] = { true, MALE, false, 28 };
            
            cout << hashTable["최서연"];
            cout << "\n";
            cout << hashTable["김동현"];

        }