신장 트리 (Spanning Tree)
최소 신장 트리에 앞서 신장 트리란 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프이다.
신장트리의 조건은 다음과 같다.
- 본래의 그래프의 모든 노드를 포함해야 함
- 모든 노드가 서로 연결
- 트리의 속성을 만족시킴 (사이클이 존재하지 않음)
최소 신장 트리 (Minimum Spanning Tree)
가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭한다.
최소 신장 트리의 특징은 다음과 같다.
- 간선의 가중치의 합이 최소여야 한다.
- n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
- 사이클이 포함되어서는 안된다.
최소 신장 트리 알고리즘 중 대표적인 알고리즘이 크루스칼 알고리즘과 프림 알고리즘이다
크루스칼 알고리즘 (Kruskal Algorithm)
가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘으로 최소 스패닝 트리를 찾음으로써 간선의 가중치의 합이 최솟값이 되도록 하는 알고리즘이다.
- 모든 간선들의 가중치를 오름차 순으로 정렬
- 가중치가 가장 작은 간선을 선택
- 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다.
- 이 과정을 반복
프림 알고리즘 (Prim Algorithm)
시작 정점을 기준으로 가장 작은 간선과 연결된 정점을 선택하며 신장 트리를 확장 시키는 알고리즘으로 정점 선택을 기반으로 한다.
- 임의의 간선을 선택
- 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택
- 모든 정점이 선택될 때까지 반복
참고
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
그래프 탐색의 대표적인 방법으로는 DFS와 BFS가 있다.
그래프 탐색의 목적은 모든 정점을 한 번씩 방문한다는 것인데 위 두가지는 차이는 ‘어떤 순서로 방문할 것인가’ 이다.
Continue reading
분할 정복 (Divide & Conquer)
- 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다.
- 분할 정복이 일반적인 재귀 호출과 다른 점은 문젤르 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나눈다는 것 이다. 같은 작업일지라도 빠르게 해결할 수 있다는 장점을 가지고 있다.
분할 정복을 사용하는 알고리즘은 대게 세 가지 구성요소를 가지고 있다.
- 문제를 더 작은 문제로 분할하는 과정 (Divide)
- 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (Merge)
- 더이상 답을 분할하지 않고 곧장 풀 수 있는 매두 작은 문제 (Base case)
문제에 이런 특성이 있어야 분할 정복을 사용할 수 있다
- 문제를 둘 이상의 부분으로 나누는 자연스러운 방법이 있다.
- 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있다.
- 절반으로 나누는 알고리즘이 큰 효율 저하를 불러오는 등 같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커지기도하는데 이렇게 중복 계산이 반복되며 시간을 소보하는 문제를 ‘Overlapping subproblems’라고 한다. 이는 동적 계획법을 고안하는 계기가 되기도 하는데 더 자세한 내용은 아래 링크에서 확인해볼 수 있다.
https://ataraxiady.github.io/dev/2021/03/22/dev-algorithm-dynamicprogrammingalgorithm/
Continue reading
큐 (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
스택이란 (Stack)
- 같은 구조와 같은 크기의 자료들을 정해진 방향으로만 쌓을 수 있고 후입선출(LIFO) 형식으로 입출력이 일어나는 자료구조이다.
- 제일 먼저 입력된 데이터가 맨 아래 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조이다.
- 삽입 연산은 Push연산 이라 하고 삭제 연산은 pop 연산 이며 둘다 사용이 쉽다.
- 비어있는 스택에서 원소를 추출하는 것은 Stack underflow이고 스택이 넘치는 경우 stack overflow라고 말한다.
장점과 단점
- 장점 : 데이터의 삽입과 삭제가 빠르다
- 단점 : 탐색을 하려면 원소를 하나하나 꺼내서 옮겨야하고 맨 위의 원소만 접근 가능하다
- 재귀 알고리즘이나 역추적을 해야할 경우(실행취소) 유용하게 사용할 수 있다
Continue reading
그리디 알고리즘 (Greedy Algorithm)
Continue reading
동적계획법이란 (Dynamic Programming)
- 동적계획법이란 전체 문제를 subproblmes로 단순화하고 재귀적 구조를 활용하여 병합해나가며 전체 문제를 해결하는 방법이다.
- 분할정복 알고리즘(Divide & Conquer)은 subproblems가 여러번 계산되지만 동적계획법은 딱 한번만 계산하고 그 답을 배열에 저장해두기에(Memoization) 매번 다시 계산하는 불필요한 작업을 피한다.
- 중복 계산을 줄이기에 시간복잡도가 분할정복 알고리즘보다는 적다.
- 최적해를 구할 수 있도록 전체 문제를 작은 문제로 단순화한다
- 최적해를 구할 수 있는 재귀적 구조를 찾는다
- 일반적으로 Bottom-up방법으로 최적해를 계산한다 (작은 문제 해결방법으로 전체 문제 해결)
Continue reading
백트랙킹 알고리즘 (Backtracking Algorithm)
- 백트래킹은 여러 개의 솔루션을 가진 문제에서 조건을 만족하는 모든 솔루션을 체크 하는 알고리즘이다.
- 솔루션을 하나씩 체크하며 조건에 맞지 않는 솔루션은 삭제하는 과정을 거친다.
- 재귀를 사용하거나 스택을 통한 DFS를 사용할 수 있다.
Continue reading
기본적인 정렬 알고리즘에 대한 요약이다.
Continue reading