최소 신장 트리(MST)

신장 트리 (Spanning Tree)

최소 신장 트리에 앞서 신장 트리란 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프이다.
신장트리의 조건은 다음과 같다.

  1. 본래의 그래프의 모든 노드를 포함해야 함
  2. 모든 노드가 서로 연결
  3. 트리의 속성을 만족시킴 (사이클이 존재하지 않음)

최소 신장 트리 (Minimum Spanning Tree)

가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭한다.
최소 신장 트리의 특징은 다음과 같다.

  1. 간선의 가중치의 합이 최소여야 한다.
  2. n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
  3. 사이클이 포함되어서는 안된다.

최소 신장 트리 알고리즘 중 대표적인 알고리즘이 크루스칼 알고리즘과 프림 알고리즘이다

크루스칼 알고리즘 (Kruskal Algorithm)

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘으로 최소 스패닝 트리를 찾음으로써 간선의 가중치의 합이 최솟값이 되도록 하는 알고리즘이다.

  1. 모든 간선들의 가중치를 오름차 순으로 정렬
  2. 가중치가 가장 작은 간선을 선택
  3. 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다.
  4. 이 과정을 반복

프림 알고리즘 (Prim Algorithm)

시작 정점을 기준으로 가장 작은 간선과 연결된 정점을 선택하며 신장 트리를 확장 시키는 알고리즘으로 정점 선택을 기반으로 한다.

  1. 임의의 간선을 선택
  2. 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택
  3. 모든 정점이 선택될 때까지 반복

참고

https://velog.io/@dnjscksdn98/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%AC
https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

Continue reading

최단 경로 알고리즘(다익스트라, 벨만-포드, 플로이드-와셜)

대표적인 그래프 내 특정 정점에서 갈 수 있는 모든 정점들까지의 최단 경로를 구하는 알고리즘들로는 다익스트라, 벨만-포드, 플로이드-와셜 알고리즘이 있다.
이 세가지 모두 Optimal substructure 의 개념을 이용하여 최단 경로를 찾는데 이는 중간의 정점들이 각각 최단이 된다면 이를 모두 이은 경로 또한 최단이 된다는 개념이다.
따라서 한 정점에서 다른 정점까지 가는 도중 다른 정점을 거쳐 지나가는 것이 더 짧은지 확인하고 값을 갱신하여 최단 거리를 찾는다는 공통점이 있지만 알고리즘마다 약간의 차이가 있다.
자세한 내용은 순서대로 각 알고리즘에 대해 작성해보도록하겠다.

Continue reading

분할 정복이란 (Divide & Conquer)

분할 정복 (Divide & Conquer)

  • 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다.
  • 분할 정복이 일반적인 재귀 호출과 다른 점은 문젤르 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나눈다는 것 이다. 같은 작업일지라도 빠르게 해결할 수 있다는 장점을 가지고 있다.

분할 정복을 사용하는 알고리즘은 대게 세 가지 구성요소를 가지고 있다.

  1. 문제를 더 작은 문제로 분할하는 과정 (Divide)
  2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (Merge)
  3. 더이상 답을 분할하지 않고 곧장 풀 수 있는 매두 작은 문제 (Base case)

문제에 이런 특성이 있어야 분할 정복을 사용할 수 있다

  1. 문제를 둘 이상의 부분으로 나누는 자연스러운 방법이 있다.
  2. 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있다.
  • 절반으로 나누는 알고리즘이 큰 효율 저하를 불러오는 등 같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커지기도하는데 이렇게 중복 계산이 반복되며 시간을 소보하는 문제를 ‘Overlapping subproblems’라고 한다. 이는 동적 계획법을 고안하는 계기가 되기도 하는데 더 자세한 내용은 아래 링크에서 확인해볼 수 있다.

https://ataraxiady.github.io/dev/2021/03/22/dev-algorithm-dynamicprogrammingalgorithm/

Continue reading

큐와 덱 (Queue & Deque)

큐 (Queue)

  • 먼저 들어온 데이터가 먼저 나가는 구조로, 선입선출(FIFO) 형식으로 입출력이 일어나는 자료구조이다.
  • 스택과 다르게 큐는 삽입과 삭제가 다른 쪽에서 일어난다.
  • 삽입은 enqueue 연산을 통해 큐의 맨 뒤(rear)에 새로운 요소를 추가한다. 삭제는 dequeue 연산을 통해 큐의 맨 앞에 있는 요소를 꺼내 외부로 반환한다.
  • 장점 : 데이터의 삽입/삭제가 빠르다
  • 단점 : queue 중간에 위치한 데이터의 접근이 어렵다
  • 데이터를 입력된 순서대로 처리하거나 BFS 구현할 때 사용한다.

덱 (Deque)

  • 덱은 double-ended queue의 줄임말로 큐의 맨 앞과 맨 뒤 모두 삽입과 삭제가 가능한 큐를 의미한다.
  • 장점 : 데이터의 삽입과 삭제가 빠르고 크기가 가변적이다. 앞, 뒤에서 데이터를 삽입/삭제 할 수 있다. index로 임의 원소 접근이 가능하다. 새로운 원소 삽입 시에, 메모리를 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입한다.
  • 단점 : deque의 중간에서의 삽입과 삭제가 어렵고 구현이 어렵다.
  • 앞과 뒤에서 삽입, 삭제가 잘 일어나느 경우, 데이터의 개수가 가변적일 경우, 데이터 검색을 거의 하지않을 경우(랜덤 요소 접근)에 사용한다.

참고 사이트

C언어로 쉽게 풀어쓴 자료구조
https://velog.io/@choiiis/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue

Continue reading

Pagination


© 2020.09. by 다로

Powered by theorydb