[C++] Hash Table, Greedy Algorithm, Heap, Dynamic Programming, DFS, BFS

2023.10.20 TIL

Hash Table

키(key)와 해시 테이블(hash table)이 서로 mapping되는 자료구조

C++ STL에서의 hash table

• std::map → O(logN)
  • 주로 binary search tree로 구현됨
• std::unordered_map → O(1)
  • hash table로 구현됨

std::unordered_map 사용법

#include <unordered_map>
using namespace std;

unordered_map<string, int> d;

cout << d["leo"] << endl;  // key에 의한 value의 접근
d["leo"] = 3;  // 특정 key에 대한 value 업데이트

for(auto& i : d)
	cout << **i.first** << " : " << **i.second** << endl;

→ i.first 로 key, i.second 로 value를 얻을 수 있음

Greedy Algorithm

알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택

체육복 문제 :
n명의 학생, 체육복은 앞이나 뒤 사람한테만 빌려주기 가능
체육복 두개 있는 학생과 체육복이 없는 학생의 번호가 주어질 때 몇명 수업 가능?

for(int i = 1; i <= n; i++) {
   if(uniform[i - 1] == 0 && uniform[i] == 2) // 앞사람에게 빌려주기
       uniform[i - 1] = uniform[i] = 1;
   else if(uniform[i] == 2 && uniform[i + 1] == 0)  // 뒷사람에게 빌려주기
       uniform[i] = uniform[i + 1] = 1;
}

• 1번학생은 자신의 앞번호가, n번학생은 자신의 뒷번호가 없음
  • 그래서 학생 배열을 0 ~ n-1 로 만들 경우 index out of range 발생
  • 해결 → 학생 배열을 0 ~ n+1 로 잡고, 실제로 1 ~ n 을 번호로 사용하면 됨!
  • 0번과 n+1번의 값은 1로 놓으면 아무런 영향 X

Heap

: 최대/최소 원소를 빠르게 찾을 수 있음

#include <queue>

// 자료형, container 종류, less(maxheap)/greater(minheap)
priority_queue<int, vector<int>, greater<int>> q;

m = q.top();  // 최소값
q.pop();  // 최소값 삭제
q.push(x);  // x 삽입
cout << q.empty() << endl;  // false

• Min heap : 가장 작은 원소를 빠르게 찾을 수 O
• Max heap : 가장 큰 원소를 빠르게 찾을 수 O

연산

• heapify : O(NlogN) . 빈 heap에 N개 원소 삽입
• insert : O(logN)
• delete : O(logN)

구현

• complete binary tree

응용

• heapsort
• priority queue

Dynamic Programming

: 알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있음

Knapsack Problem

가장 높은 값을 가지도록 물건들을 골라 배낭에 담으시오

unordered_set : 중복을 허용하지 않는 자료구조

#include <unordered_set>

unordered_set<int> s[5];

s[i].insert(num);  // i번째에 num 삽입

// s에 number가 들어있는지 확인하는법
if(s[i].count(number) > 0)

DFS, BFS

DFS
스택을 이용해 어느 노드에서 DFS를 하고있는지 기억하고 돌아감

BFS
큐를 이용해 어느 노드에서 BFS를 해야하는지 기록하고 진행함

unordered_map 사용법

#include <unordered_map>

unordered_map<string, vector<string>> routes;

routes[i].push_back(tickets[i]);

routes.find(airport);  // routes에 airport key가 없다면 routes.end() 를 반환

routes[airport].size();  // airport key의 value의 size 반환

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    sort(tickets.begin(), tickets.end(), greater<vector<string>>());
    
    unordered_map<string, vector<string>> routes;
    
    for(int i = 0; i < tickets.size(); i++)
        routes[tickets[i][0]].push_back(tickets[i][1]);
    
    vector<string> s = vector<string> {"ICN"};
    while(!s.empty()) {
        string airport = s.back();
        
        if(routes.find(airport) == routes.end() || routes[airport].size() == 0) {
            answer.push_back(airport);
            s.pop_back();
        } else {
            s.push_back(routes[airport].back());
            routes[airport].pop_back();
        }
    }
    
        
    reverse(answer.begin(), answer.end());
    return answer;
}

🌾🌾

상황별로 어떤 기능을 신박하게 구현하는 코드들을 많이 배우게 되었다.
여전히 알고리즘에서 인덱스 다루는건 넘 어렵다 ㅠㅠ