[99클럽 코테 스터디 5일차 TIL] #해시

이제 매일 1문제씩 풀고 TIL 쓰는 게 점점 몸에 익숙해지기 시작한 것 같다. 계속 꾸준히 하며 실력을 길러보자!

 

문제 설명

---

문자열이 들어오는 횟수 정수 N이 주어지면,

N 개의 문자열을 모스부호로 받고, 이에 해당하는 문자를 출력해 문장을 만드는 문제입니다.

https://www.acmicpc.net/problem/29701

 

생각 흐름

---

우선, 문제를 보았을 때, 또 문자열 문제구나 싶어서 우선 문자열을 다루는 함수를 떠올리며 문자열로 접근하려고 했다.

 

음.. 이 많은 모스부호를 어떻게 비교하지 생각하다가 결국은 고민하지 말고 손으로 직접 써보기로 했다.

 

이중 벡터를 선언해서 각각의 문자마다의 모스부호를 적어주고 문자열이 들어왔을 때 이를 for문으로 비교하는 구문을 작성해 보았다.

 

손이 좀 고생했지만 결괏값은 잘 나와서 좋았던 것 같다.

 

#include <bits/stdc++.h>
using namespace std;

vector <vector <string>> v = {{"A",".-"},{"B", "-..."}, {"C","-.-."}, {"D","-.."},{"E", "."}, {"F","..-."}, {"G","--."},{"H","...."}, {
    "I",".."}, {"J", ".---"}, {"K", "-.-"}, {"L",".-.."}, {"M", "--"}, {"N","-."}, {"O", "---"}, {"P", ".--."}, {"Q", "--.-"}, {"R",".-."}, {"S", "..."}, {"T","-"}, {"U", "..-"},
    {"V", "...-"}, {"W", ".--"}, {"X", "-..-"}, {"Y","-.--"}, {"Z","--.."}, {"1",".----"}, {"2", "..---"}
    ,{"3","...--"}, {"4","....-"}, {"5","....."},{"6", "-...."}, {"7","--..."}, {"8","---.."}, {"9","----."}, {"0","-----"}, {",","--..--"}, {".",".-.-.-"}, {"?","..--.."}, {":","---..."},
    {"-","-....-"}, {"@",".--.-."}};
vector <string> result;

int main () {
    int n; // 문자열의 길이 n
    cin >> n;
    
    string s;

    for (int i = 0; i < n; i++) {
        cin >> s;
        for (int j = 0; j < v.size(); j++) {
            if (s == v[j][1]) {
                result.push_back(v[j][0]);
            }
        }
    }
    
    for (auto i : result) cout << i;

}

 

이렇게 풀고 문제 힌트를 보니 #해시라는 새로운 단어가 쓰여 있었다.

 

난 당연히 또 문자열문제인 줄 알았는데 해시(?)라는 단어가 쓰여져 있으니 당황스러웠다.

 

구글링을 해봐야겠다는 생각을 했다. 

 

은근 해시 (Hash)라는 놈이 유명한 놈이었다. 너무 유명한 자료구조라나..

하지만 처음 단어를 접했던 나는 일단 공부해 보기로 했다.

 

공부한 내용 정리

---

1. 해시(Hash Function) 함수란?

• Hash Function: 해시 함수는 임의의 길이의 문자열을 받아서 고정 문자열로 바꾸어주는 함수이다. 이때 함수를 구현하는 방법에 따라서 해당 서로 다른 임의의 문자열이 같은 고정 문자열로 되기도 하며 이러한 부분을 충돌이라고 한다. (H(s1) == H(s2))
• 아래 사진의 경우에는 좌측에 파란색들이 key이며 각 key들이 해시 함수의 결과를 오른쪽 우측에 숫자로 바뀌었음을 보여준다. 나중에 해시테이블에서는 이 key을 해시한 결과를 배열의 인덱스로 사용한다.
• 해시 함수를 H()라고 했을 때 H(John Smith) == 02

해시 함수설명

 

2. 해시 충돌 (Hash Collision)

• 서로 다른 문자열을 해시한 결과가 동일한 경우
• 해시 함수를 H()라고 했을 때 서로 다른 문자열 s1과 s2에 대해서 H(s1) == H(s2)인 경우
• 해시 테이블을 구현할 때 해시 충돌이 일어나게 되면 Chaining 혹은 Open Addressing을 통해서 해결해야 한다.

 

3. 해시 테이블 (Hash Table)

• key와 value로 된 쌍을 저장하는 자료구조이다.
• 아래 사진처럼 Lisa Smith라는 key로 521-8976의 value를 저장할 수 있도록 설계된 자료구조이다.
• C++에서는 map 그리고 python에서는 dictionary를 통해 보다 쉽게 이용할 수 있다.
• 성능이 좋을 때는 O(c)에 접근을 할 수 있기 때문에 공간을 소비해서 접근속도를 늘리고 싶을 때 이용한다. 물론 O(c)도 해시 테이블의 용량이 엄청 크고 해시 함수도 충돌이 일어나지 않는다는 가정이 있을 때 가능하다.
• 해시 테이블을 구현할 때 해시 충돌이 일어나게 되면 Chaining 혹은 Open Addressing을 통해서 해결해야 한다.
•  

  

  쉽게 생각해 보자면, 데이터를 효율적으로 관리하기 위해 구현된 방법으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 것이라고 한다.

충돌이 일어나지 않는 상황에서는 좋은 것 같다. 

 

충돌 해결 1.  Chaining

• 각 인덱스마다 연결리스트를 하나씩 둔다.

충돌 해결 2. Open Addressing

• 충돌 발생 시 다른 공간 탐색 

 

4. map 자료구조

해시 함수의 충돌까지는 모르겠지만 해시 함수의 대표적인 C++ 자료구조에는 map 자료구조가 있는 것 같아 이를 공부해보려고 한다.

 

1) map 이란?

map은 각 노드가 key와 value 쌍으로 이루어진 트리입니다. 특히 중복을 허용하지 않습니다.

따라서 map은 first, second가 있는 pair 객체로 저장되는 데 first - key로 second - value로 저장됩니다.

C++의 map은 내부 구현은 검색, 삽입, 삭제가 O(logN)인 레드블랙트리로 구성되어 있습니다.

 

2) map 기본 형태

map<key, value> map1;

 

3) map 정렬

map은 자료를 저장할 때 내부에서 자동으로 정렬합니다.

map은 key를 기준으로 정렬하며 오름차순으로 정렬합니다.

 

만약 내림차순으로 정렬하고 싶은 경우, 다음과 같이 사용하면 됩니다.

map <int, int, greater> map1;

 

만약 다른 방법으로 int 데이터를 내림차순으로 정렬하고 싶은 경우,데이터에 (-) 마이너스를 붙여 삽입하여 처리하면 내림차순으로 정렬됩니다.

 

4) map 사용방법

 

  (1) 헤더 포함

  --> map을 사용하려면 헤더에 #include <map> 처리를 해야 합니다.

 

  (2) map 선언하기

  --> map의 기본 구조는 map <key type, value type> 이름입니다.

map <string, int> m;

 

  (3) map에서 찾고자 하는 데이터가 있는지 확인하기 (search)

 

  --> map에서 데이터를 찾을 때는 iterator을 사용합니다.  --> 데이터를 끝까지 찾지 못했을 경우, iterator는 map.end()를 반환합니다.

if (m.find("Alice") != m.end()) {
	cout << "find" << "\n";
}
else {
	cout << "not find" << "\n";
}

 

  (4) map에 데이터 삽입

 

  -->  map은 중복을 허용하지 않습니다. insert를 수행할 때, key가 중복되면 insert가 수행되지 않습니다. 중복되면 그것은 key의 역할을 제대로 하지 않습니다.

m.insert({"Cam", 300});

 

 

  (5) 반복문 데이터 접근 (first, second)

 

• 인덱스 기반 반복문 활용한 예제

: 인덱스 기반은 iterator을 활용하여 begin()부터 end()까지 찾습니다.

// 인덱스 기반
for (auto iter = m.begin(); iter != m.end(); iter++) {
	cout << iter->first << " " << iter->second << "\n";
}
cout << "\n";

 

• 범위 기반 반복문 활용한 예제

for (auto iter : m) {
	cout << iter.first << " " << iter.second << "\n";
}

 

 

  (6) map에서 삭제하기

 

  --> map에서 데이터를 삭제하기 위해서 활용할 함수는 erase와 clear입니다.

 

  * 특정 위치의 요소 삭제

m.erase(m.begin()+2);

  

  * key 값을 기준으로 요소 삭제

m.erase("Alice");

 

  * map의 모든 요소 삭제

m.erase(m.begin(), m.end());

 

  * clear 함수로 모든 요소 삭제하기

m.clear();

 

 

  (7) map 사용 구문 (삽입, 찾기, 반복문 구현)

 

#include <iostream>
#include <map>
using namespace std;
map <string, int> mapset;

int main () {
    mapset.insert({"Alice", 100});
    mapset.insert({"Bob", 200});

    if (mapset.find("Alice") != mapset.end()) {
        cout << "find" << "\n";
    }
    else {
        cout << "not find" << "\n";
    }

    // 인덱스 기반
    for (auto iter = mapset.begin(); iter != mapset.end(); iter++) {
        cout << iter->first << " " << iter->second << "\n";
    }

    cout << "\n";

    // 범위 기반
    for (auto iter : mapset) {
        cout << iter.first << " " << iter.second << "\n";
    }

    cout << "\n";

    return 0;
}