해시 테이블

• KEY를 5로 나누면 0인데, 이미 테이블의 위치가 0인 값이 이미 들어있다. -> 충돌
• 체이닝 방법으로 해시 충돌을 해결
  

체이닝

• 충돌이 일어나면 각 주오세 있는 LinkedList에 삽입하여 해결
  
• 리스트는 순차 탐색이라 O(n) 의 수행 시간을 갖는데, 이를 개선하기 위해 이진 탐색을 사용하는 방법이 있다.

예제

#include <iostream>
#include <vector>
#include <unordered_map> //해시테이블
using namespace std;

int main()
{
    unordered_map<string, int> hash = unordered_map<string, int>(); //Key : string . Value : int

    //성과 키를 매칭 
    hash["Park"] = 166;
    hash["Kim"] = 162;

    //해시 테이블에 데이터 추가
    hash.insert(make_pair("Son", 180)); // Son이라는 Key에 Value 180 추가.

    cout << "@@@@@@@@@@@데이터 가져오기@@@@@@@@@@@ " << endl;
    //해시 테이블에 데이터 가져오기
    for (auto it = hash.begin(); it != hash.end(); it++)
    {
        cout << it->first << endl; //키 가져오기
        //Park , Kim , Son이 해시테이블에 저장되어 있고, first에 의미는 각 Key를 의미한다. 
    }

    //체이닝 방식
    cout << "@@@@@@@@@@@체이닝 방식@@@@@@@@@@@ " << endl;
    unordered_map<string, vector<string>> chaning = unordered_map < string, vector<string>>();

    chaning["country"].push_back("서울");
    chaning["country"].push_back("도쿄");
    chaning["country"].push_back("베이징");

    for (auto it = hash.begin(); it != hash.end(); it++)
    {
        cout << it->first << endl;
    }


}

프로그래머스 예제 1

https://school.programmers.co.kr/learn/courses/30/lessons/42578?language=cpp

프로그래머스 예제 2

https://school.programmers.co.kr/learn/courses/30/lessons/42577?language=cpp

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

using namespace std;

    
    //폰북을 해시테이블의 키값으로
    //hash["1 2"] = 1;
    //hash["1 2 3"] = 1;
    //hash["1 2 3 5"] = 1; 
    //대칭
    //hash = {"1 2"} : 1
    //hash = {"1 2 3"} : 1
     //hash = {"1 2 3 5 "} : 1
    
    //hash["1"] = false
    //hash["1 2"] = true;
    //hash["1 2 3"] = true;

bool solution(vector<string> phone_book) 
{
    bool answer = true;
    
    unordered_map<string,int> hash;
    
    //폰북을 해시에 저장. "12" , "123" , "1235" .... 
    //hash[phone_book[0]] = 1; 
    //hash[phone_book[1]] = 1; 
    //hash[phone_book[1]] = 1; 
    for(int i = 0; i < phone_book.size(); i++)
    {
        hash[phone_book[i]] = 1;
    }
    
    string number = "";
    string tmp = "";
    for(int i = 0; i < phone_book.size(); i++)
    {
         tmp = phone_book[i];
         number = "";
        
        for(int j = 0; j < tmp.size(); j++)
        {
            number += tmp[j];
        
            if(hash[number] == 1 && tmp != number) 
            {
                answer = false;
            }
        }
    
    }
    //tmp = phone_book[2]; //1235
    
    //number + tmp[0] //1
    //number + tmp[1] //2
    

    
    
    
    return answer;
}

깃허브 코드 cpp파일 주관식

• 4장 -> 전화번호부,의상.
• 3장 -> 캐시 1개
• 2장 -> 2-1에서는 야구,김서방 찾기
• 2장 -> 2-2에서는 버블정렬 , 과일장수(버전1~2) , 예산

ppt 파일 객관식

-> ot파일의 알고리즘과 자료구조는 어떤 관계가 있는지. ppt 내용은 객관식.(힙연산 , 큐에 대한 설명 옳지 않은 것)