크루스칼 알고리즘 : 가장 적은 비용으로 모든 노드를 연결하기 위해 사용되는 알고리즘 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘입니다. ​ ※ 신장 트리 : 그래프 내의 모든 노드를 포함하는 트리 노드 = 정점 = 도시 : 그래프에서 동그라미에 해당하는 부분 간선 = 거리 = 비용 : 그래프에서 선에 해당하는 부분 ​ 위 그래프를 살펴보았을 때 6개의 노드와 8개의 간선이 있습니다. 해당 그래프를 크루스 칼 알고리즘을 적용시켜 본다면 아래와 같습니다. ​ 잠시 그래프에서 모든 노드를 연결하기 위해 최소한으로 필요한 간선의 수는 N( 노드) - 1개입니다. 즉 위 그래프는 노드가 6개 있으므로 최소 비용 신장 트리를 만들기 위해 필요한 간선의 수는 5개입니다. ​ 일단 모든 노드를 최대한 적은 ..

Union-Find ( 합집합 찾기) : 대표적인 그래프 알고리즘. 서로소 집합( Disjoint-Set) 알고리즘이라고도 한다. 여러 개의 노드가 존재할 때 두 개의 노드를 선택하여, 현재 두 노드가 같은 그래프에 속하는지 판별 -> Find와 Union 연산을 수행할 수 있다. ​ 위와 같이 여러 개의 노드가 자유분방하게 존재하고 있다고 했을 때, 이들은 모두 연결되지 않고 각자 자신만을 집합의 원소로 가지고 있을 때 아래와 같이 표현할 수 있다. 모든 값은 자기 자신을 부모 노드로 가지고 있습니다. 이때, 위와 같이 1과 2가 연결되었을 때, 표로 표현하였을 때 아래의 표로 나타납니다. 노드 번호 1 2 3 4 5 6 7 부모 노드 번호 1 1 3 4 5 6 7 2번째 인덱스의 값에 ' 1 ' 이 ..

깊이 우선 탐색 : 탐색을 할 때 깊이를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 ​ ' 맹목적으로 각 노드를 탐색 ' 할 경우 주로 사용하는 탐색 기법으로, 모든 노드를 방문하고자 하는 경우 ( 완전 탐색) 사용 너비 우선 탐색 ( BFS) 보다 지나온 경로를 쉽게 파악할 수 있다는 장점이 있다. 또 층별로 모든 자식 노드를 저장해야 할 필요가 없기 때문에 BFS에 비해 메모리 요구량이 훨씬 적다 ​ ※ 어느 방향으로 검색할지 확률에 따라 속도가 많이 빨라질 수도 있고 느려질 수도 있다.(확률 의존) ​ 깊이 우선 탐색을 수행하기 위해서 필요한 준비물은 Stack이다. 이다. ※컴퓨터는 구조적으로 스택의 원리를 사용하기 때문에 재귀 함수를 사용하여 구현이 가능하다. ​ 이제 어떤 식으로 정렬이 이루..

너비 우선 탐색 : 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 ​ ' 맹목적인 탐색 ' 을 하고자 할 때 사용할 수 있는 탐색 기법으로 ' 최단 경로 ' 를 찾아준다는 점에서 최단 길이를 보장할 때 많이 사용 ​ ※ 시작점과 거리가 멀수록 탐색이 느려진다. 하지만 근처에 있을 경우 빠르게 탐색 가능하다. ※ 맹목적인 탐색 : 이미 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 탐색하는 방법을 말한다. ​ 너비 우선 탐색을 하기 위해서 필요한 준비물은 Queue ( 큐 ) 이다. ​ 우선 어떤식으로 정렬이 이루어 지는지 보자면! 다음과 같이 1 2 3 4 5 가 서로 연결되어 있다고 보았을 때 너비 우선 탐색을 해보자면 시작 노드 ( Start Node ) 를 큐에 삽입..

Queue : 데이터를 일시적으로 저장하기 위한 자료구조 가장 먼저 들어온 데이터가 가장 먼저 나가는 자료구조 ( FIFO : First In First Out) ex) 은행 창구 : 먼저 번호표를 뽑은 사람이 먼저 서비스를 받는다. Queue를 코드로 구현해보자면 import java.util.LinkedList; public class QueueEx { public static void main(String[] args) { Queue s = new Queue(); for(int i = 1; i

Stack : 데이터를 일시적으로 저장하기 위한 자료구조 가장 먼저 들어온 데이터가 가장 마지막에 나가는 자료구조 ( FILO : First In Last Out) ex) 택배 상하차 : 택배차에 택배를 처음 넣은 것이 제일 마지막에 나온다. ​ Stack을 코드로 구현해보자면 import java.util.ArrayList; public class StackEx { public static void main(String[] args) { // TODO 자동 생성된 메소드 스텁 Stack s = new Stack(); for(int i = 1; i

수 정렬 : https://www.acmicpc.net/problem/10989 ================================== 풀이 ==================================== 계수 정렬 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(Sy..

시리얼 번호 정렬 :https://www.acmicpc.net/problem/1431 ================================== 풀이 ==================================== C++ 함수 사용 #include // C++ 헤더 #include // STL 라이브러리 -> sort() 함수가 정의되어있음 #include #include using namespace std; string a[20000]; int n; int getSum(string a) { int n = a.length(), sum = 0; for (int i = 0; i < n; i++) { if (a[i] - '0' = 0) { sum += a[i] - '0'; } } return sum; }..