그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다.

그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

1. 깊이 우선 탐색 (DFS, Depth-First Search)

: 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

💡 깊이 우선 탐색의 개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에
해당 분기를 완벽하게 탐색하는 방식을 말한다.

예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가
더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있다.

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

2. 너비 우선 탐색 (BFS, Breadth-First Search)

: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

💡 너비 우선 탐색의 개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택합니다.

ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie사이에 존재하는 경로를 찾는 경우

• 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
• 너비 우선 탐색의 경우 - Sam과 가까운 관계부터 탐색

3. 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 비교

💡DFS와 BFS의 시간복잡도

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일합니다.
DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 됩니다.

N은 노드, E는 간선일 때

인접 리스트 : O(N+E)
인접 행렬 : O(N^2)

일반적으로 E(간선)의 크기가 N²에 비해 상대적으로 적기 때문에
인접 리스트 방식이 효율적이다.

3. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용

DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.

1) 그래프의 모든 정점을 방문하는 것이 주요한 문제
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.
둘 중 편한 것을 사용하시면 됩니다.

2) 경로의 특징을 저장해둬야 하는 문제
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)

3) 최단거리 구해야 하는 문제
미로 찾기 등 최단 거리를 구해야 할 경우, BFS가 유리합니다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

이밖에도

• 검색 대상 그래프가 정말 크다면 DFS를 고려
• 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

4. DFS와 BFS을 사용한 c++코드

DFS 알고리즘에 경우 두 가지 방법으로 풀 수 있는데,

첫 번째로 스택을 이용하는 것
두 번째로 재귀함수를재귀 함수를 이용하는 것인데, 재귀 함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성할 수 있다.
재귀 함수란 함수 내부에서 함수가 자기 자신을 또다시 호출하는 함수를 의미합니다.

이러한 재귀 호출은 자기가 자신을 계속해서 호출하므로, 끝없이 반복되기 때문에
함수 내에 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 합니다.

// DFS - Recursion
void dfs_recursion(int x, int y) {

    // 함수에 들어왔으면 -> 방문으로 표시
    visited[x][y] = true;
    // 해당 단지의 집의 수를 증가시킴
    groups[group_id]++;

    // 해당 위치의 주변을 확인
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 지도를 벗어나지 않고
        if(0 <= nx && nx < n && 0 <= ny && ny < n){
            // 집이면서 방문하지 않았다면 -> 방문
            if(map[nx][ny] == 1 && visited[nx][ny] == false){
                dfs_recursion(nx, ny);
            }
        }
    }
}

BFS 알고리즘은 큐(Queue)를 사용해서 문제를 해결하면 됩니다.

// BFS
void bfs(int x, int y){

    queue< pair<int,int> > q; // 이용할 큐, (x,y) -> (행, 열)
    q.push(make_pair(x,y)); // pair를 만들어서 queue에 넣습니다.

    // 처음 x,y를 방문 했기때문에
    visited[x][y] = true;
    groups[group_id]++;  

    while(!q.empty()){

        // 큐의 현재 원소를 꺼내기
        x = q.front().first;
        y = q.front().second;
        q.pop();

        // 해당 위치의 주변을 확인
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 지도를 벗어나지 않고
            if(0 <= nx && nx < n && 0 <= ny && ny < n){
                // 집이면서 방문하지 않았다면 -> 방문
                if(map[nx][ny] == 1 && visited[nx][ny] == false){
                    visited[nx][ny]=true;

                    // 해당 단지의 집의 수를 증가시킴
                    groups[group_id]++;

                    // 큐에 현재 nx,ny를 추가
                    q.push(make_pair(nx,ny));   
                }
            }
        }
    }
}

참고링크

• https://devuna.tistory.com/32

Heap이란

힙(Heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)다. 최악의 경우가 생겨도 힙은 완전 이진 트리이므로 항상 O(logN)의 시간에 해결될 수 있도록 해준다.

힙을 이용한다면 최댓값 혹은 최솟값을 O(logN)에 찾을 수 있다. (일반 배열 사용시 O(N))

최대 힙(Max Heap) / 최소 힙(Min Heap)

최대 힙은 완전 이진트리의 root 부분에 최댓값이 항상 존재하게 되고 최소 힙은 완전 이진트리의 root 부분에 최솟값이 항상 존재하게 된다.

• 최대 힙의 특성: 임의의 subtree에서 root 가 되는 노드를 잡으면 항상 subtree에서의 root 노드는 그 subtree에서 최댓값을 유지한다.
• 최소 힙의 특성 : 임의의 subtree에서 root가 되는 노드를 잡으면 항상 subtree에서의 root 노드는 그 subtree에서 최솟값을 유지한다.
• 주의해야 할 점 : '힙의 자식 노드에서 작은 것이 왼쪽, 큰 것이 오른쪽' 이런 것은 존재하지 않는다. ⇒ 즉, 왼쪽 오른쪽에 무슨 노드가 오던간에 해당하는 subtree에서 루트노드보다 큰 (minheap에서는 작은) 값이면 된다.

실제 구현 시, 최소 힙은 최대 힙에서 음수 값으로만 구현해주면 되기 때문에 최대 힙 구현만 알고 있으면 됨.

최대 힙 삽입 과정(push)

1. Insert 할 값을 힙의 마지막 위치에 삽입한다.
2. 부모 노드와 비교를 해서 Insert 할 값이 더 크다면 swap 해준다.
3. 2번 과정을 계속 반복한다.

최대 힙 삭제 과정(pop)

pop 이기 때문에 root 부터 삭제하면 된다고 이해하면 될듯.

1. 삭제할 값(root)를 빼낸다.
2. 힙에서 마지막에 있는 노드를 root 로 올린다.
3. root로 올린 노드와 그 자식들의 노드를 비교해서 swap 해준다.
4. 2~3번 과정을 반복한다.

이진 탐색 트리(Binary Search Tree) 와의 차이점

• 힙은 자식 노드가 부모 노드보다 크면 오른쪽으로 삽입, 작으면 왼쪽으로 삽입 과 같은 조건이 존재하지 않는다.
• 하지만 이진 탐색 트리에서의 노드 별 값 크기 순은 왼쪽 자식 < 부모 < 오른쪽 자식 순으로 된다.

보통 일반적으로 Heap 을 사용하기 위해서 C++ 에서는 Priority_queue 를 많이 사용한다.
이 때 코테에서 까먹지 않기 위해서는 일반적으로 선언해야 하는 메소드와 로직은 외우고 있어야 한다.

실제로 많이 쓰는

priority_queue<int , vector<int>, greater<int> > pq;

priority_queue<int , vector<int>, less<int> > pq;

priority_queue<int , vector<int>, compare > pq;

이 3가지 정도는 무조건 외우고 있어야 한다.

◆ 정리

• 우선순위 큐를 구현한 것.
• priority_queue container 는 vector, deque container 와 붙어서 사용 (list 불가능)
• 내부적으로는 <algorithm>에 있는 힙 관련 함수들을 사용하여 구현.
• 내부구조 default 는 vector container 기반으로 설정
• 정렬기준 default는 내림차순(less<>) 기반으로 설정

＃priority_queue container 생성자와 연산자

• 기본 생성자 형식 priority_queue < [Data Type] > [변수이름];ex) priority_queue<int> pq;
• 내부 컨테이너 변경 priority_queue < [Data Type], [Container Type] > [변수이름];ex) priority_queue<int, deque<int> > pq;
• 정렬 기준 변경 priority_queue < [Data Type], [Container Type], [정렬기준] > [변수이름];ex) priority_queue<int , vector<int>, greater<int> > pq;

＃priority_queue container 멤버 함수

• bool empty() const;→ check whether container is empty.→ 비어 있다는 것은 size가 0 이기도함.→ 비어있으면 true 반환
• size_type size() const;→ return size 원소의 개수를 반환합니다.
• const value_type& top() const;→ access top element 맨 위에있는 원소를 참조 및 반환 합니다.(삭제하는거 아님)
• void push (const value_type& val);→ insert element인자를 삽입합니다. 내부적으로는 push_back 함수를 이용하여 삽입이 됩니다.
• void pop();→ remove top element 맨 위에있는 인자를 삭제합니다.내부적으로는 pop_heap 알고리즘과 pop_back 함수가 이용되어 우선순위 큐 형태를 유지합니다.

priority_queue <T,vector<T>,compare> pq; 사용법!

struct Custom{
	int x;
	int y;
	int value;
	Custom(int value): x(0), y(0), value(value) {}
};


// 오름차순 정렬
struct cmp{
    bool operator()(Custom t, Custom u){
        return t.value > u.value;
    }
};
priority_queue <Custom, vector<Custom>, cmp> pq;

위의 코드와 같이 구조체를 선언하고, 해당 구조체에 대한 operator 를 선언해주어 사용할 수 있다. 코드를 잘 외우자!

데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력 받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 방법으로, 궁극의 탐색 알고리즘이다.

해시 테이블의 성능은 공간을 팔아 얻어낸 것이라고 생각하면 된다.

보통 테이블의 엔트리는 <Key, value> 로 나타내며 이 때 value 는 key 로 인한 hash function 의 아웃 풋이다.

해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다.

허나 해시를 이용하면 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존에 사용했던 자료 구조들은 탐색이나 삽입에 선형 시간이 걸리기도 했던 것에 비해, 해시를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더욱 빠른 속도로 처리할 수 있다.

→ Hash Table 은 bucket 들과 그 bucket 을 이루고 있는 slot 들로 구성되어있다.

※ 해쉬 함수의 요구조건

• 계산하기 쉬워야 한다.

• 충돌의 횟수를 최소화 해야 한다.

• 편향되지 않아야 한다.

◇1. Direct Addressing Table

Direct Addressing Table 은 key-value쌍의 데이터를 배열에 저장할, key 값을 직접적으로 배열의 인덱스로 사용하는 방법이다.

예를 들면 키 값이 400인 데이터가 있다면, 이는 배열의 인덱스가 400인 위치에 키 값을 저장하고 포인터로 데이터를 연결한다.

똑같은 키 값이 존재하지 않는다고 가정하면, 삽입 시에는, 각 키마다 자신의 공간이 존재하므로 그 위치에다가 저장을 하면 되고, 삭제 시에는 해당 키의 위치에 NULL 값을 넣어주면 된다. 탐색 시에는 해당 키의 위치를 그냥 찾아가서 참조하면 된다.

찾고자 하는 데이터의 key 만 알고 있으면 즉시 위치를 찾는 것이 가능하므로 탐색 저장, 삭제, 갱신은 모두 선형시간 인 O(1) 로 매우 빠른 속도로 처리가 가능하다.

다만 key값이 최대 크기만큼 배열이 할당되기 때문에, 크기는 매우 큰데, 저장하고자 하는 데이터가 적다면 공간을 많이 낭비할 수 있다는 단점이 있다.

◇2. Hash Table

Hash Table 은 key-value 쌍에서 key 값을 테이블에 저장할 때, Direct Addressing Table과 달리 Key 값을 함수를 이용해 계산을 수행한 후,

그 결과 값을 배열의 인덱스로 사용하여 저장하는 방식이다. 여기서 key 값을 계산하는 함수는 해쉬 함수(Hash Function) 이라고 부르며, 해쉬 함수는 입력으로 key를 받아, 0부터 배열의 크기 -1 사이의 값을 출력한다. 해쉬에 대한 첫 정의대로 임의의 숫자를 배열의 크기 만큼으로 변환시킨 것이다.

이 경우 k값이 h(k) 로 해쉬 되었다고 하며, h(k)는 k의 해쉬 값이라고 한다

2.1 충돌(Collusion)

하지만 해쉬 테이블은 '충돌'이 일어날 수 있다는 큰 문제점이 있다. 충돌이란, 다른 k값이 동일한 h(k)값을 가져 동일한 slot 에 저장되는 경우를 말한다.

예를 들자면 k1과 k12 을 해쉬하였더니 h(k1) = h(k12) 인 경우를 들 수 있다. Direcet Addressing Table 에서는 이를 방지하기 위해 모든 key 값이 다르다고 전제하였지만 해쉬 테이블에서는 key값이 달라도 해쉬의 결과가 같을 수 있기 때문에 이를 방지하기 위한 방법이 필요하다.

하지만 해쉬 함수를 아무리 잘 짜더라도 충돌을 '완전히' 방지한다는 것을 보장하기는 힘드므로, 충돌을 방지하기 위한 방법으로 충돌을 어느 정도 허용하되 이를 최소화 하는 방법도 사용하기도 한다.

Chaining 방법 - 충돌을 허용하되 최소화 하는 방법

충돌을 허용하지만 이를 최소화 하기 위한 방법 중 하나인 체이닝 방식이다. 체이닝이란 이름 그대로 데이터들을 포인터를 이용해 서로 체인 형태로 엮어 나가는 것을 뜻하며, 해쉬 테이블에선 동일한 해쉬 값이 출력 되어 충돌이 일어나면, 그 위치에 있던 데이터에 key 값을 포인터로 뒤이어 연결한다. (마치 Linked List 처럼)

따라서 최초로 h(k) 위치에 저장된 데이터를 시작으로 그 이후의 h(k) 값이 출력되는 데이터는 모두

의 형태를 취한다.

그렇기 때문에 최초의 위치를 탐색하는 해쉬 과정을 제외하고, 모든 탐색, 삽입, 삭제 과정은 연결리스트와 유사한 방식으로 진행한다.

Chaining 방법에서의 수행시간은 삽입 시에는 해쉬 값을 이용해 바로 slot 에 저장하면 되므로 상수 시간에 일어나고, 삭제는 연결리스트의 삭제와 동일하게 상수시간에, 탐색 시에는 견결 리스트를 따라가기 때문에 연결리스트의 길이 만큼 발생하지만, 최악의 경우, 즉 모든 데이터의 해쉬값이 일치하여 한 인덱스에 젖아됬을 경우엔 연결리스트의 탐색시간과 동일한 선형시간을 가지게 된다.

적재률

하지만 이 최악의 경우는 극단적인 예로써, 평균적인 경우엔 O(a+1)의 시간이 걸린다. a는 적재율을 뜻하며 적재율이란 현재 저장된 key값 갯수(K), 전체 테이블의 갯수(N)을 서로 나눈 값(K/N)이다. 즉 현재 저장된 데이터가 많으면 많아질수록 충돌 확률이 높아져 연결 리스트 탐색 확률도 증가하며, 적을수록 리스트 탐색 확률이 적어진다는 것이다.

Simple uniform hash

충돌을 최소화 하는 방법 중에 충돌이 적은 좋은 해쉬 함수를 만드는 방법도 있다. 좋은 해쉬 함수의 조건은 Simple uniform hash 함수를 만드는 것으로, 이 조건은 다음과 같다.

1. 계산된 해쉬 값들은 0부터 배열의 크기-1 사이의 범위를 '동일한 확률'로 골고루 나타날 것.

2. 각각의 해쉬 값들은 서로 연관성을 가지지 않고 독립적으로 생성될 것.

첫 번째 조건을 충족하면 충돌이 일어날 확률이 적어질 것이며, 두 번째 조건은 해쉬값들이 서로 연관이 있을 경우 연관성이 있으면 해당 해쉬 값이 등장하는 패턴이나 순서가 존재 할 수 있고, 이는 반복적인 충돌을 일으킬 확률이 있기 때문이다.

division method

해쉬 함수는 정말 다양하지만 대표적인 해쉬 함수로는 divison method가 있는데, modular 연산 방법을 이용하는 방법이다. 특정 key를 어떤 수로 나눈 나머지를 해쉬값으로 사용한다.

예를 들어 m=100이면 k mod m은 0부터 99까지의 범위를 가진다. 이 범위의 m은 해쉬 테이블의 성능을 크게 좌우하는데, m의 크기는 보통 키의 수의 3배가 적당하다고 한다. (적재율이 30%쯤까지 충돌이 거의 일어나지 않는다고 한다.)

그리고 m으로 2^p값을 사용하는 것엔 큰 주의를 요한다. 왜냐하면 m이 2^3이면, 2진수로 00001000이고, 4번째 이하의 숫자만 해쉬값에 영향을 끼치기 때문이다.

예를 들어 k1과 k2가 각각 10110100,10120100이면 둘 다 같은 해쉬값을 출력한다. 이를 방지하기 위해서 m은 보통 2^p에 근접한 소수를 선택한다고 한다.

◇ 정리

해시 알고리즘의 기초

• 인덱스를 사용하는 검색 알고리즘이다.
• 대용량의 데이터를 검색할 떄 주로 사용한다.
• 이진 검색 알고리즘과 병행해서 사용하면 빠른 검색 속도를 얻을 수 있다.
• 검색 성능 : O(1)
• 장점 : 데이터의 양에 관계 없이 빠른 성능을 기대할 수 있다.

해시 알고리즘에서 사용하는 몇 가지 용어

• 버킷 : 해시 주소 하나에 1개 이상의 데이터가 저장되는 전체 메모리 공간
• 슬롯 : 버킷에서 하나의 데이터가 저장되는 메모리 공간
• 충돌 : 서로 다른 데이터인데 같은 해시 주소를 갖게 되면 충돌이 발생한다.
• 오버플로 : 보통 충돌을 방지하기 위해 해시 주소 하나에 여러 슬록을 만들지만, 충돌이 계속해서 발생하여 데이터를 저장할 슬롯이 없어지는 상황

"오버플로" 해결방법

• 선형 조사 방법 : 해시 주소에 데잍어가 채워져 잇을 경우 옆자리를 확인하는 방법→ 데이터가 집중되는 현상 발생 (클러스터링)
• 링크드 리스트 사용 : 같은 해시 주소를 갖는 데이터를 배열이 아니라 링크드 리스트로 구성→ 클러스터링이 발생하면 링크드 리스트 내부에서 검색 작업이 발생해 순차 검색 해야 한다.
• 리해싱 : 다른 해시 함수를 사용해서 새로운 해시 주소를 생성하는 것→ 함수의 성능에 따라 알고리즘의 성능이 달라질 수 있다.

c++ 에서 해시 테이블을 구현하는 방법 중 대표적으로

unordered_map 이 있다.

코테보기 전에 이거 외우고 가자.

unordered_map 사용하기

• map보다 더 빠른 탐색을 하기 위한 자료구조이다.
• unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)이다.
• map은 Binary Search Tree로 탐색 시간 복잡도는 O(log n)이다.
• unordered_map을 사용하기 위해서는 #include< unordered_map > 을 선언해야 한다.
• unordered_map은 중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을 시 월등히 좋은 성능을 보인다.
• 하지만, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수도 있다.

함수

empty( )

• 맵이 비어있는지 확인하는 함수
• if unordered_map is empty, then return 1 else 0

size( )

• 맵의 크기를 확인하는 함수
• return size_type ( unsigned int )

operator [ ]

• 맵에서 key를 통해 value를 지정하는 operator
• map_name[key] = value

find( key )

• 맵에서 key에 해당하는 원소를 찾는 함수
• if key is contained, then iterator else map_name.end()

count( key )

• 맵에서 key에 해당하는 원소의 갯수를 반환하는 함수
• if key is contained, return 1 else 0

insert( )

• 맵에 pair<key,value> 를 추가하는 함수
• if key is contained, then not insert

erase( key )

• 맵에서 key에 해당하는 원소를 제거하는 함수
• erase 하는 방법 : 특정 position의 pair 삭제, key를 통해 삭제, 범위 삭제

clear( )

• 맵을 초기화하는 함수

operator =

• 대입연산자 가능

※ 주의할 점

unordered_map 을 통해 for 문을 돌 때, vector 와 약간 다르다는 것을 알고 있어야 한다.

for (auto i = MapPlayer.begin(); i != MapPlayer.end(); ++i) {      
	if (i->second) {          
    	iAnswer = i->first;          
        break;      
    } 
 }

위의 코드와 같은 방식으로 for 문을 돈다. 주의 할 점은 ++i 라는 것이다.

(또한 i→first , i→second 방식으로 원소를 뽑아낼 수 있다는 점을 알아둬야 할 듯.)

프로그래머스 문제

1. 해쉬 1번