DDijkstra's Record DDijkstra's Record

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다. 섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다. 다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸..

다룰 내용 Brute-Force로 패턴 매칭 KMP 알고리즘이란 무엇인가? KMP 알고리즘 구현 Brute-Force로 패턴 매칭 기존에 있는 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴과 일치하는지 일일이 확인하는 방식으로 동작하게 됩니다. 기존 문자열을 패턴 길이만큼 비교해보기 때문에 시간 복잡도는 O(문자열 길이 * 패턴 길이)가 됩니다. 위의 그림처럼 하나 하나 일치하는지 비교를 하기 때문에 문자열의 길이가 길어진다면 비효율적인 탐색이 됩니다. KMP 알고리즘이란 무엇인가? 불일치가 발생한 텍스트 문자열의 앞부분에 어떤 문자가 있는지 미리 알고 있기 때문에 불일치가 발생한 앞부분에 대해서 다시 비교하지 않으면서 매칭이 일어나는지 판단할 수 있는 알고리즘입니다. 시간 복잡도는 O(문자열 길이 ..

다룰 내용 Dijkstra 알고리즘 벨만 포드 알고리즘 Dijkstra 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해가면서 최단 경로를 구하는 알고리즘으로 탐욕 기법을 이용하는 Prim 알고리즘과 유사합니다. 그러나 다익스트라의 경우 근시안적인 관점 때문에 음의 가중치가 있다면 사용할 수 없습니다. Dijkstra import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Dijkstra { public static class Vertex implements Comparable{ int v, weight; public Vert..

다룰 내용 신장 트리란 무엇인가? 최소 비용 신장 트리란 무엇인가? 최소 비용 신장 트리를 구성하는 방법 Kruskal 알고리즘 Prim 알고리즘 신장 트리란 무엇인가? 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리를 말합니다. 사이클이 안 생기는 조건 안에서 간선의 개수를 정점 - 1개로 골라 만드는 것으로, 정점 - 1의 수가 간선의 수가 되는 트리입니다. 최소 비용 신장 트리란 무엇인가? 신장 트리 중에서 간선들의 합이 최소인 트리입니다. 또한 무향 가중 그래프에서 만들어질 수 있고 사이클이 발생되지 않으며 비용의 합이 최소인 트리입니다. 최소 비용 신장 트리의 특징 무방향 가중치 그래프입니다. 가중치의 합이 최소입니다. 정점 n개에서 n - 1개의 간선을 가지는 트리입니다. 사이클이 포..

다룰 내용 조합이란 무엇인가? 조합 구현 부분 집합이란 무엇인가? 부분 집합 구현 조합이란 무엇인가? 순서의 의미가 없이 수를 나열하는 것으로, 순열의 경우 순서가 의미가 있으나 조합은 의미가 없습니다. 조합을 구현하는 방법 현재 자리에서 조합할 수를 선택합니다. 조합 구현 첫 번째 방법 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Combination { public static int N, R; public static int origin[], number[]; public static void main(Strin..

다룰 내용 서로소 집합이란 무엇인가? 상호 배타 집합을 표현하는 방법 Union Find 구현 서로소 집합(Disjoint-set)이란? 서로소 또는 상호 배타 집합들은 서로 중복되는 원소가 없는 집합을 말합니다. 상호 배타 집합을 표현하는 방법 연결 리스트로 구현 트리로 구현 상호 배타 집합 연산 Make-set(x) : 집합을 만드는 동작입니다. Find-set(x) : x가 속한 집합을 찾는 동작입니다.(이때 해당 원소의 대표자를 반환합니다.) Union(x, y) : 두 집합의 원소를 주고 합치는 동작입니다. 상호 배타 집합 - 연결리스트 구현 같은 집합의 원소들은 하나의 연결리스트로 관리합니다. 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 생각해봅니다. 따라서 각 원소는 집합의 대표 원소를 ..

다룰 내용 그래프란 무엇인가? 그래프의 종류 그래프를 표현할 수 있는 방법 그래프란 무엇인가? 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조를 의미합니다. 그래프의 종류 무향그래프: 간선의 방향이 없는 그래프입니다. 유향그래프: 간선의 방향이 있는 그래프입니다. 가중치 그래프: 정점에서 정점으로 이어진 간선에 가중치가 있는 그래프입니다. 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph): 사이클이 존재하지 않는 유향 그래프를 말합니다. 완전 그래프: 정점들에 대해 가능한 모든 간선들을 가진 그래프입니다. M개의 정점을 가지는 완전 그래프는 최대 M(M - 1) / 2 간선 수를 가집니다. 부분 그래프: 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프입..

다룰 내용 Priority Queue란 무엇인가? Priority Queue 구현 방법 PrioriyQueue의 우선 순위 기준 부여하기(Java) - Comparable, Comparator Priority Queue란 무엇인가? 우선 순위에 따라 데이터가 추출되는 자료구조입니다. 따라서 들어간 순서에 상관없이 우선 순위가 높은 데이터가 먼저 추출됩니다. Prioriy Queue를 구현하는 방법 배열로 구현하는 방법 연결 리스트로 구현하는 방법 Heap을 이용하는 방법 배열로 구현하는 방법 구현하는 방법은 간단하나 데이터 삽입 및 삭제가 일어날 때마다 당기거나 미는 연산을 계속해서 연산이 많다는 단점이 있습니다. 또한 들어오는 데이터의 삽입 위치를 결정하기 위해 저장되어 있는 모든 데이터들과 우선 순위..