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) : 두 집합의 원소를 주고 합치는 동작입니다. 상호 배타 집합 - 연결리스트 구현 같은 집합의 원소들은 하나의 연결리스트로 관리합니다. 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 생각해봅니다. 따라서 각 원소는 집합의 대표 원소를 ..

다룰 내용 순열이란 무엇인가? 순열 구현 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..

다룰 내용 재귀란 무엇인가? 재귀를 구현할 때 주의할 점 Factorial Fibonachi 재귀란 무엇인가? 자신의 메소드 내부에서 자신의 메소드를 호출하는 것 재귀를 구현할 때 주의할 점 1) 메소드의 역할을 명확히 해야 함. 2) 자신이 해야할 일과 나머지 작업으로 분리해야 함. 3) 기저 조건이 반드시 있어야 함. (재귀 탈출 조건) -> 기저가 없으면 스택 오버 플로우 발생 4) 재귀의 깊이를 생각해야 함. (상태 공간 트리 활용) 5) 깊이뿐만 아니라 수행시간도 고려해야 함. Factorial 5! -> 5 * 4 * 3 * 2 * 1 => 이는 5 * 4! 형태로 이해할 수 있음. => 또 5 * 4 * 3! 형태로도 이해할 수 있음. => 5 * 4 * 3 * 2! 형태 => 5 * 4 *..