DDijkstra's Record DDijkstra's Record

다룰 내용 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 간선 수를 가집니다. 부분 그래프: 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프입..

다룰 내용 순열이란 무엇인가? 순열 구현 next_permutation이란 무엇인가? next_permutation 구현 순열이란 무엇인가? 순서 있게 수들을 나열하는 것으로, 원소의 순서가 의미있다면 순열입니다. 서로 다른 N개의 수 중에 R개를 선택하여 나열(nPr)로 표현할 수 있고 경우의 수를 구하면 nPr = n * n - 1 * n - 2 ~~ n - r + 1 이렇게 구할 수 있습니다. 순열을 구현하는 방법 각 자리에서 앞 쪽에 선택된 수를 배제합니다. (앞쪽에서 선택된 수를 알기 위해 boolean 배열 사용) 현재 자리에서 선택 가능한 수를 선택합니다. import java.io.BufferedReader; import java.io.IOException; import java.io.In..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net 문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에..