Spanning Tree그래프 내의 모든 정점을 포함하는 트리💡 최소 신장 트리는 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.특징사이클이 만들어지지 않아야 한다.사이클이 만들어진 경우는 불필요한 연결이 존재한다는 뜻이기 때문전체 노드(n) -1 개의 간선으로 구성된다.하나의 그래프에 여러 개의 최소 신장 트리가 존재할 수 있다.최소 신장 트리의 대표적인 알고리즘으로는 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 존재한다.크루스칼 알고리즘 (Kruskal Algorithm)동작 원리선택하지 않은 간선들 중 최소 가중치인 간선을 선택사이클이 없는 경우에만 트리에 추가총 v-1 (정점 개수 -1)개의 간선이 선택될 때까지 반복구성한 스..
💡 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.음의 간선을 포함할 수 없다. (음의 간선 포함은 벨만-포드 알고리즘 사용)매번 가장 비용이 적은 노드 를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘으로 분류알고리즘 작동 원리출발 노드를 설정한다.최단 거리 테이블을 초기화한다.방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.3, 4를 반복한다. 알고리즘 구현 방법 방법 1. 간단한 다익스트라 알고리즘간단하게 구현할 때 $O(V^2)$의 시간 복잡도를 가진다.전체 노드의 개수가 5,000개 이하일 때 무난하게 사..
정렬 알고리즘의 일종순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것진입차수와 진출차수진입차수 (Indegree): 특정한 노드로 들어오는 간선의 개수진출차수 (Outdegree): 특정한 노드에서 나가는 간선의 개수위상 정렬 알고리즘 동작 과정1. 진입 차수가 0인 노드를 큐에 넣는다.2. 큐가 빌 때까지 다음의 과정을 반복한다. a. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 b. 새롭게 진입차수가 0이 된 노드를 큐에 삽입⇒ 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과위상 정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프(DAG) 여야만 한다.위상 정렬의 ..
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다www.acmicpc.net문제를 간단하게 설명하자면 세준이가 바보같이 문제를 잘 만들어놓고 괄호를 지워버렸다.이 문제에서는 무조건 숫자와 연산자가 번갈아가면서 나오기 때문에 특수한 예외상황을 신경쓰지 않아도 되었다. 그러면 '-' 연산자가 나오면 최대한 크게 묶어서 처리를 해주면 되겠다라고 생각이 들어서 스택을 사용해 뒤에서부터 수를 계속 더하다가 '-'가 나오면 minus 변수에 추가를 해주고 '+' 연산자까지의 부분은..
