반응형

* Hashing (해싱)

해싱은 임의의 길이의 데이터(키, Key)를 고정된 길이의 데이터(해시값, Hash value)로 변환해 작은 크기의 해시 테이블로 대응(Mapping)시켜 식별하는 하나의 기법입니다. 해시 테이블은 M개의 버킷으로 이루어져 있으며, 이 글에서 다루는 해시값은 해당 키가 저장될 버킷의 번호(해시 테이블의 인덱스)를 나타냅니다.

키에서 해시값을 추출하는 일련의 과정을 해시 함수(Hash function)라고 합니다. 해시 함수는 같은 키에 대해서는 동일한 해시값을, 다른 키에 대해서는 다른 해시값을 추출해야 합니다. 하지만 일반적으로 해싱에서 해시값의 범위(M)는 키의 범위보다 작기 때문에 어떤 이상적인 해시 함수라도 비둘기집의 원리에 의해 서로 다른 두 키가 같은 해시값을 가질 수 있습니다. 이런 경우를 충돌(Collision)이라고 합니다.

해싱이 사용되는 예로 문자열(Key)을 정숫값(Hash value)으로 치환하여 문제를 해결하는 방법이 있습니다. 이에 사용되는 가장 대표적인 해시 함수는 진법을 이용하는 것입니다. "SCPC"이라는 단어가 있다고 하면, 아래와 같이 진법을 이용한 해시 함수를 만들 수 있습니다.

f(key) = ((((key[0]) * 26 + key[1]) * 26 + key[2])) * 26 … key[l – 1])
f("SCPC") = 19 * 26^3 + 3 * 26^2 + 16 * 26^1 + 3 * 26^0 = 336391

해시 함수의 시간 복잡도를 O(H)라고 할 때 해시값의 중복이 없는 이상적인 해싱에서 키의 검색, 삽입, 삭제에는 모두 O(H)의 시간이 걸립니다.
하지만 앞서 말했듯 해시값의 범위가 키의 범위보다 작을 때에는 충돌이 발생할 수밖에 없습니다.
예를 들어 위와 같은 진법 변환을 해시 함수로 사용할 때에는 문자열이 길어지면 해시값이 너무 커지므로 적당히 큰 수로 나머지 연산한 값, 이 글에서는 해시 테이블의 크기 M으로 나머지 연산한 값을 해시값으로 쓸 수 있습니다.
이때 해시값의 M에 대한 나머지가 같은 키끼리는 충돌이 발생합니다.

해시 함수와 마찬가지로 충돌을 제어하는 방법도 다양합니다. 여기에서는 대표적인 충돌 제어 방법 중 하나인 체이닝(Chaining)에 대해서 설명하겠습니다. 
체이닝은 충돌한 키들을 보존하기 위해 각 버킷을 리스트 형태로 구현합니다. 최초의 버킷은 모두 원소가 0개인 리스트의 헤더이며, 해당 버킷에 데이터가 추가될 때마다 노드를 추가합니다. 
이때 어떤 키가 해시 테이블에 존재하는지 검사하기 위해서는 해당 키의 해시값에 해당하는 버킷이 가진 노드를 모두 순회해야 합니다. 
이는 리스트에서 원소를 찾는 연산과 동일하며 이에 기반한 삭제 연산도 같은 선형 시간이 걸립니다. 
이때 몇 개의 버킷에만 데이터가 편중되는 최악의 경우 각 연산의 시간 복잡도는 O(H + N)이 됩니다.

이런 상황을 최소한으로 하기 위해서는 해시값의 추출 과정, 즉 해시 함수를 어떻게 구성할 것인지가 핵심이 됩니다.
좋은 해시 함수란 해시값을 추출하는 연산이 빠르되 충돌이 적고 해시 테이블의 영역을 고르게 사용할 수 있어야 합니다.
예를 들어 위에서 다룬 A * pow(B) mod M 형태의 진법 변환을 사용할 때 A의 값을 0이 아닌 1부터 시작하는 것이 좋습니다.
0을 사용하게 되면 "A"와 "AAA"의 해시값이 같아지기 때문입니다. 또한 B와 M이 서로소인 것이 충돌 확률이 낮아 더 좋은 해시 함수가 될 수 있습니다.

해시 함수의 구현과 충돌 제어 방법, 좋은 해시 함수의 조건에 관해서는 굉장히 많은 자료가 있으므로 보다 깊은 이해를 위해 직접 찾아보시기 바랍니다.

글의 첫 부분에서 말했듯 해싱의 핵심은 값의 식별입니다. 그렇기에 원소의 중복을 허용하지 않는 Set이나 Key:Value쌍에서 중복된 Key가 존재하면 안 되는 Map과 같은 자료구조를 구현하는 데에 사용되기도 합니다.


* 출처 & 참고 링크

Samsung CodeGround

반응형
저작자표시 비영리 변경금지

'∙Data Structure' 카테고리의 다른 글

[Data Structure] Graph (그래프)  (0) 2019.01.17
[Data Structure] Tree (트리)  (0) 2019.01.17
[Data Structure] Heap (힙)  (0) 2019.01.17
[Data Structure] Stack (스텍)  (0) 2019.01.17
반응형

* Heap (힙)

힙(heap) 은 최댓값 또는 최솟값을 빠르게 찾아낼 수 있는 트리형 자료구조입니다.

힙은 완전이진트리 형식을 따르며 모든 부모 노드의 값이 자식 노드들의 값과 일정한 대소 관계를 가지게 되는 규칙을 가지고 있습니다.

또한 자식노드 사이의 상관관계는 없으므로 유의하여야 합니다.

부모 노드의 값이 자식 노드의 값보다 크다면 최대 힙(Max Heap), 부모 노드의 값이 자식 노드의 값보다 작다면 최소 힙(Min Heap) 으로 부릅니다.

힙의 규칙에 따라 트리의 가장 상단에는 최댓값 또는 최솟값이 있는 것이 자명하기 때문에, O(1) 만에 최댓값과 최솟값을 찾을 수 있습니다.

<최소 힙의 예>

힙의 삽입은 트리의 가장 마지막 부분에 데이터를 삽입한 후, 부모 노드와 삽입 부분 노드의 대소 관계를 확인하여 힙의 규칙에 맞도록 부모 노드를 탐색, 스왑하는 과정으로 이루어져 있습니다.

트리의 마지막에 추가

부모노드와 비교하여 스왑

힙의 조건을 만족함

힙의 삭제는 삭제할 원소를 삭제 한 후 트리의 가장 마지막 원소를 삭제된 원소의 위치에 넣어준 후 힙의 조건을 만족하는 적절한 위치에 이를 수 있도록 조정해주면 됩니다.

제일 마지막 원소를 삭제된 원소의 자리로 옮긴다.

힙의 규칙에 맞도록 부모와 자식노드를 바꾸어 준다.

삭제가 완료된 힙

힙의 삽입과 삭제의 시간 복잡도는 최악의 경우 최하단 노드로부터 최상단 노드까지 스왑이 필요하게 됩니다. 따라서 O(log N)의 시간 복잡도를 가집니다.

완전이진트리를 사용하기 때문에 최대 사이즈의 배열로 선언 후 쉽게 구현하실 수 있습니다.


* 출처 & 참고 링크

Samsung CodeGround

Stack & Queue & PriorityQueue

반응형
저작자표시 비영리 변경금지

'∙Data Structure' 카테고리의 다른 글

[Data Structure] Tree (트리)  (0) 2019.01.17
[Data Structure] Hashing (해싱)  (0) 2019.01.17
[Data Structure] Stack (스텍)  (0) 2019.01.17
[Data Structure] Queue (큐)  (0) 2019.01.17
반응형

* Stack (스텍)

스택은 선형 구조이며, 마지막으로 삽입된 값이 가장 먼저 나오는 LIFO(Last in First Out)으로 되어 있습니다. 이 때 삽입하는 과정을 push라고 하며 값을 빼내는 과정을 pop이라고 합니다. 예를 들면 a, b, c 순서로 push하고 스택에 있는 값들을 모두 pop하면 c, b, a 순서로 나오게 되는 것입니다. 또한 스택에는 size, top, empty라는 함수가 있으며 size는 스택에 들어있는 값들의 수를 반환하는 함수이고, top은 마지막으로 삽입된 값을 반환하는 함수, empty는 스택이 비어 있는지 여부를 반환하는 함수입니다.

아래의 두 그림은 stack의 push, pop 과정을 보여주는 그림입니다.

(A) stack push

<그림 1> stack push

(B) stack pop

<그림 2> stack pop

그리고 이러한 스택을 만드는 방법에는 2가지 방법이 있습니다. 하나는 배열을 이용한 방법이고, 다른 하나는 링크드 리스트를 이용한 방법입니다.

1) 배열을 이용한 방법에서는 삽입될 위치인 스택의 마지막 부분을 저장하는 변수 top이 필요합니다. 이 변수를 이용하여 스택의 크기(스택에 들어있는 요소의 수)를 빠르게 알 수 있습니다. 또한 스택의 크기가 0일 경우 스택이 비어 있는 것이므로 비어 있는지 여부도 쉽게 알 수 있습니다. 따라서 배열로 구현하기 위해서는 값들을 담을 배열과 스택의 마지막 위치(삽입될 위치)를 저장하는 변수가 필요합니다.

배열로 구현한 스택의 push 와 pop 과정

<그림 3> stack implemented as an array

2) 링크드 리스트를 이용한 방법에서는 값과 다음 노드의 위치를 저장하는 스택 노드들을 이용할 것이며 마지막으로 삽입된 노드의 위치를 저장하는 노드형 포인터 top과 노드들의 수를 저장하는 변수 size가 필요합니다. Head 초기화 시 처음에 널 값을 넣어주고, push할 경우 새로 삽입되는 노드의 next가 이전의 top이 되고, NewNode가 top이 됩니다.

링크드 리스트로 구현한 스택의 push 와 pop 과정

<그림 4> stack implemented as linked list



* 출처 & 참고 링크

Samsung CodeGround

Stack & Queue & PriorityQueue

반응형
저작자표시 비영리 변경금지

'∙Data Structure' 카테고리의 다른 글

[Data Structure] Hashing (해싱)  (0) 2019.01.17
[Data Structure] Heap (힙)  (0) 2019.01.17
[Data Structure] Queue (큐)  (0) 2019.01.17
[Data Structure] LinkedList (연결리스트)  (0) 2019.01.17
반응형

* Queue (큐)

큐는 선형 구조이며, 삽입된 순서대로 값이 나오는 FIFO(First in First Out)로 되어 있습니다. 이때 삽입하는 과정을 enqueue라고 하며 값을 빼내는 과정을 dequeue라고 합니다.
예를 들면 a, b, c 순서로 enqueue하고 큐에 있는 값들을 모두 dequeue하면 a, b, c 순서로 나오게 됩니다.
또한 큐에는 size, front, empty라는 함수가 있으며 size는 큐에 들어있는 값들의 수를 반환하는 함수이고, front은 큐에서 가장 먼저 삽입된 값을 반환하는 함수, empty는 큐가 비어 있는지 여부를 반환하는 함수입니다.

<그림 1> enqueue

<그림 2> dequeue

그리고 이러한 큐를 만드는 방법에는 2가지 방법이 있습니다. 하나는 배열을 이용한 방법이고, 다른 하나는 링크드 리스트를 이용한 방법입니다.

1) 배열을 이용한 방법에서는 삽입될 위치인 큐의 마지막 부분을 저장하는 변수 rear와 큐의 처음 부분을 저장하는 변수 front가 필요합니다. 또한 큐의 데이터 개수를 저장하는 변수 size를 이용하여 큐의 크기(큐에 들어있는 요소의 수)를 빠르게 알 수 있습니다. 또한 큐의 크기가 0일 경우 큐가 비어 있는 것이므로 비어 있는지 여부도 쉽게 알 수 있습니다. 따라서 배열로 구현하기 위해서는 값들을 담을 배열과 큐의 처음 위치와 마지막 위치(삽입될 위치)를 저장하는 변수가 필요합니다. 또한 enqueue과정과 dequeue과정에서 각각 rear index, front index가 점점 뒤로 밀려나기 때문에 이를 효율적으로 구성하려면 환형 배열로 구현해주어야 합니다.

<그림 3> 환형 배열로 구현한 큐의 dequeue

<그림 4> 환형 배열로 구현한 큐의 enqueue

2) 링크드 리스트를 이용한 방법에서는 값과 다음 노드의 위치를 저장하는 큐 노드들을 이용할 것이며 마지막으로 삽입된 노드의 위치를 저장하는 노드형 포인터 rear와 큐의 가장 앞 노드의 위치를 저장하는 노드형 포인터 front, 노드들의 수를 저장하는 변수 size가 필요합니다. front와 rear는 초기화시 처음에 널 값을 넣어주고, enqueue할 경우 이전에 rear의 next는 새로 삽입하는 노드가 되고, 새로 삽입되는 노드가 rear가 됩니다. dequeue할 경우 이전의 Head의 next가 Head가 되고, 이전의 head는 메모리 할당 해제 시킵니다.

<그림 5> 링크드 리스트로 구현한 queue



* 출처 & 참고 링크

Samsung CodeGround

Stack & Queue & PriorityQueue

반응형
저작자표시 비영리 변경금지

'∙Data Structure' 카테고리의 다른 글

[Data Structure] Heap (힙)  (0) 2019.01.17
[Data Structure] Stack (스텍)  (0) 2019.01.17
[Data Structure] LinkedList (연결리스트)  (0) 2019.01.17
[Data Structure] ArrayList vs LinkedList  (0) 2018.12.27
반응형

* LinkedList (연결리스트)

연결리스트는 랜덤 접근이 가능한 배열과는 다른 순차적인(sequential) 자료구조입니다.

연결리스트는 노드들로 구성되어 있습니다. 노드는 저장할 값과 다음 노드를 가리키는 포인터로 이루어져 있습니다. 연결리스트의 첫 노드인 헤드(Head)로 부터 노드에 다음 노드를 가리키는 포인터를 사용해 리스트를 순회할 수 있게 됩니다.

<List(연결리스트)>

위와 같은 연결리스트를 Singly Linked List라고 합니다.

Singly Linked List의 각 노드에 이전 노드를 가리키는 포인터를 추가하게 되면 양방향으로 순회가 가능한 Doubly Linked List가 되고, 환형 큐(Circular Queue)와 같이 연결리스트의 마지막 노드인 테일(Tail)과 헤드를 이으면 Circular Linked List가 됩니다.
이는 문제의 상황에 따라 구현하여 사용하시면 됩니다.

<Doubly Linked List>

각 노드는 저장할 값과 자신의 앞, 뒤 노드를 가리키는 포인터를 가짐

<Circular Linked List>

테일의 포인터는 헤드를 가리킴

두 자료구조의 장단점을 나열해보자면, 배열은 인덱스로 인한 무작위 접근이 가능하고, 리스트에 비해 저장공간을 적게 필요로 하지만, 리스트에 비해 자료의 삽입, 삭제가 비효율 적인 부분이 있습니다. 순서를 유지하면서 자료를 삽입 / 삭제하기 위해서는 최악의 경우 모든 데이터를 옮겨주어야 하기 때문입니다.

리스트는 무작위 접근이 불가능하므로 무조건 순차적으로 탐색해야 하며, 노드에 저장할 값과 포인터를 포함하고 있기 때문에 똑같은 크기의 배열에 비해 저장공간을 많이 차지하게 되지만, 자료의 삽입과 삭제가 새로운 노드를 만들어 포인터로 이어주기만 하면 되기 때문에 간편하고 유연하게 동작합니다.

List(연결리스트)동적배열
IndexingO(N)O(1)
Insert / Delete at beginningO(1)O(N)
Insert / Delete at endO(1) when last element is known;
O(N) when last element is unknown		O(1)
Insert / Delete in middlesearch time + O(1)O(N)



* 출처 & 참고 링크

Samsung CodeGround

ArrayList vs LinkedList


반응형
저작자표시 비영리 변경금지

'∙Data Structure' 카테고리의 다른 글

[Data Structure] Heap (힙)  (0) 2019.01.17
[Data Structure] Stack (스텍)  (0) 2019.01.17
[Data Structure] Queue (큐)  (0) 2019.01.17
[Data Structure] ArrayList vs LinkedList  (0) 2018.12.27
반응형

* 핵심

우선순위큐를 이용하여 다익스트라를 구현

* 문제

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(stk.nextToken());
        int E = Integer.parseInt(stk.nextToken());
        int start = Integer.parseInt(br.readLine());
 
        ArrayList<Edge>[] edge = new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) edge[i] = new ArrayList<>();
        int[] dijkstra = new int[V + 1];
        Arrays.fill(dijkstra, -1);
 
        for (int i = 0; i < E; i++) {
            stk = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(stk.nextToken());
            int v = Integer.parseInt(stk.nextToken());
            int w = Integer.parseInt(stk.nextToken());
            edge[u].add(new Edge(u, v, w));
        }
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[V + 1];
        pq.add(new Edge(0, start, 0));
        while (!pq.isEmpty()) {
            Edge e = pq.poll();
            if (!visited[e.v]) {
                visited[e.v] = true;
                dijkstra[e.v] = e.w;
                for (int i = 0; i < edge[e.v].size(); i++) {
                    pq.add(new Edge(e.v, edge[e.v].get(i).v, e.w + edge[e.v].get(i).w));    //해당 간선과 연결된 간선 
                }
            }
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            int tmp = dijkstra[i];
            if (tmp != -1) sb.append(tmp + "\n");
            else sb.append("INF\n");
        }
        System.out.print(sb);
    }
 
 
    public static class Edge implements Comparable<Edge> {
        int u, v, w;
 
        Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
 
        @Override
        public int compareTo(Edge o) {
            return w - o.w;     //오름차순 정렬
        }
    }
}
 
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/1275 :: 커피숍2  (0) 2019.01.22
[Algorithm] 백준/2042 :: 구간 합 구하기  (0) 2019.01.22
[Algorithm] 백준/1922 :: 네트워크 연결  (0) 2019.01.16
[Algorithm] 백준/11055 :: 가장 큰 증가 부분 수열  (0) 2019.01.14
반응형

* 핵심

MST의 Union-Find를 이용하여 최소비용을 출력

* 문제

문제

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입력

첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다.

출력

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.io.*;
import java.util.*;
 
public class Main {
    public static int[] disjoint;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
 
        Edge[] edge = new Edge[m];
        for (int i = 0; i < m; i++) {
            StringTokenizer stk = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(stk.nextToken());
            int v = Integer.parseInt(stk.nextToken());
            int w = Integer.parseInt(stk.nextToken());
            edge[i] = new Edge(u, v, w);
        }
        Arrays.sort(edge);
        disjoint = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            disjoint[i] = i;
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {       //union-find
            Edge e = edge[i];
            int u = e.u;
            int v = e.v;
            int x = find(u);        //find
            int y = find(v);        //find
            if (x != y) {           //union
                disjoint[x] = y;
                ans += e.w;
            }
        }
        System.out.println(ans);
    }
 
    public static int find(int x) {
        if (disjoint[x] == x) return x;
        else return disjoint[x] = find(disjoint[x]);
    }
 
    public static class Edge implements Comparable<Edge> {
        int u, v, w;
 
        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
 
        @Override
        public int compareTo(Edge o) {
            return this.w - o.w;
        }
    }
}
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/2042 :: 구간 합 구하기  (0) 2019.01.22
[Algorithm] 백준/1753 :: 최단경로  (0) 2019.01.16
[Algorithm] 백준/11055 :: 가장 큰 증가 부분 수열  (0) 2019.01.14
[Algorithm] 백준/10835 :: 카드게임  (0) 2019.01.14
반응형

* 최단 경로 알고리즘

최소 신장 트리와 달리, 최단 경로 알고리즘은 출발 정점과 도착 정점이 존재한다.

즉, 최소 신장 트리처럼 모든 정점을 방문할 필요 없이 출발 정점에서 도착 정점까지 최단 경로만 찾으면 된다.


* 다익스트라 알고리즘    =>O(|E||log|V|)

다익스트라 알고리즘은 음의 가중치가 없을 때 우선순위 큐를 활용해 최단 경로를 구하는 알고리즘이다.

1. 출발 지점에서 시작하는 간선들 중 최소 가중치를 가지는 간선을 선택한다.

2. 해당 정점을 방문하면 해당 정점까지 필요한 가중치 + 해당 정점에서 방문할 수 있는 간선의 가중치 들을 우선순위 큐에 넣는다.

3. 위 과정을 목표 정점에 도착할 때까지 반복한다.

단, 음의 가중치가 존재해서는 안된다. => 벨만-포드 알고리즘 사용


* 벨만 - 포드 알고리즘    =>O(VE)



* 플로이드 와샬 알고리즘    =>O(n^3)

모든 경우의 수를 시도해보는 알고리즘이다.

2차원 배열 d의 초기값을 모두 무한대로 설정한다.

이후 해당 정점을 거쳐가는 최단거리가 있다면 해당 거리를 업데이트한다.

1
2
3
4
5
6
7
8
9
for (int k = 0; k < N; ++k) {            //거쳐가는 정점
    for (int i = 0; i < N; ++i) {        //시작 정점
        for (int j = 0; j < N; ++j) {    //도착 정점
            if (d[i][j] > d[i][k] + d[k][j]) {
                d[i][j] = d[i][k] + d[k][j];
            }
        }
    }
}
cs

즉, d[1][5] = d[1][k] + d[k][5]가 되는데 

d[1][1] + d[1][5]  or  d[1][2] + d[2][5]  or  d[1][3] + d[3][5]  or  d[1][4] + d[4][5]  or  d[1][5] + d[5][5] 중 최소값을 찾는다.

반응형
저작자표시 비영리 변경금지

'∙Algorithm Tech' 카테고리의 다른 글

[Algorithm Tech]공통 부분 문자열과 최장 공통 부분 수열  (0) 2019.01.30
[Algorithm Tech] Segment Tree(세그먼트 트리)  (0) 2019.01.22
[Algorithm Tech] 최소 신장 트리(MST, Minimum Spanning Tree)  (0) 2019.01.16
[Algorithm Tech] Scanner vs BufferedReader  (0) 2019.01.10

티스토리툴바