본문 바로가기

알고리즘(アルゴリズム）

벨만-포드 알고리즘(가중치가 음수일 때의 최단경로) https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net import java.io.*; import java.util.*; // 벨만-포드에 대해서는 https://velog.io/@kimdukbae/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Bellman-Ford-Algorithm .. 더보기
플로이드 - 워샬 알고리즘 https://www.acmicpc.net/problem/11404 [모든] 정점과 정점 사이의 최단 거리를 알고 싶을 때 사용 (시간 복잡도 O(N^3)으로 그렇게 성능이 좋지 않다) 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net import java.io.*; import java.util.*; public class Main { private static int n,m; private static BufferedReader br = new BufferedReader(new InputStreamReader.. 더보기
0-1 BFS 특징 1. 가중치가 0과 1로만 이루어 져 있을 때에만 사용이 가능 2. 일반적인 큐가 아닌 데큐(Deque)를 사용해야 한다. 알고리즘의 핵심 포인트 1. 가중치 그래프이므로, 기존의 BFS로 최단 경로를 구할 때와 같이 [깊이]가 아닌, [가중치의 최소합]이 최단 경로의 길이가 된다. 2. 위 1의 [가중치의 최소합]을 구하기 위하여, a) 가중치의 합이 0인 경로... b) 가중치의 합이 1인 경로.. c) 가중치의 합이 2인 경로.. -> 가중치의 합이 0인 경로부터 시작하여 , +1씩하여 1인 경로를 탐색한다. 3. 데큐(Deque)로부터 removeFirst()를 한 노드가 target 노드이면 알고리즘 종료! 아래의 문제를 기준으로, 그림을 그려보았다. https://www.acmicpc.n.. 더보기
다익스트라 알고리즘 다익스트라 알고리즘은 최소 비용 신장 트리(MST)와는 달리 방향 그래프만 아니라, [무방향] 그래프에서도 적용이 가능하다. import java.io.*; import java.util.*; public class Main { private static final int INF = 10000; //다익스트라 최단 경로 // 1. 하나의 시작 정점을 두고, 다른 모든 정점을 목적지로 하여 최단 경로를 구하는 것이다 // -> 모든 정점을 시작점으로 두고, 다른 모든 정점까지의 최단 경로는 [플로이드-워샬] 알고리즘으로 구한다. // 2. 가중치가 있는 가중치 그래프를 전제로 한다.(가중치가 없으면, BFS로 최단 경로 구하면 됨) // -> 시작 노드에서 목적지 노드까지의 가중치의 합이 최소인 경로가 최.. 더보기
BFS()는 공짜로 최단 경로를 보장하지 않는다(Feat. Predecessor) https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [그래프] 26. 최단 경로용 BFS 아래와 같은 빈 큐와 그래프가 있다고 가정하자. 여기에 BFS 알고리즘을 사용할 것이다. 각 Node 의 predecessor 는 보기 편하게 표로 나타내겠다. 먼저 시작점 Node를 방문했다고 표시한다. 시작점은 아무데서도 오지 않았다. 그러니 이전 Node가 없는 것이다. predecessor 는 없다고 표시한다. 시작점 Node A 를 큐에 넣는다. 큐에서 가장 앞에 있는 Node를 꺼.. 더보기
Decision Problem https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 위 문제에서 처음으로 결정 문제(Decision Problem)에 대해 접하게 되었다. 결정 문제의 정의는 다음과 같다. 계산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말한다. 예를 들어 "두 숫자 x와 y가 있을 때, y는 x로 나누어떨어지는가?" 하는 질문이 있다. 답은 x와 y 값에 따라 '.. 더보기
Parametric Search Algorithm( 백준 1654번 ) https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 개인적으로, 매우 좋은 문제였다. 최적화 문제를 결정 문제로 변화하여 풀 수가 있다니... 1 | 이진 탐색(Binary Search) 이진 탐색은 정렬된 일련의 값들이 주어졌을 때 그 값들 중에서 원하는 값을 찾는 알고리즘이라고 할 수 있습니다. 이진 탐색은 처음에 중간값을 선택하여 그 값과 찾으려는 값을 비교하여 클 경우 선택했던 중간값을 최솟값으로, 작을 경우 중.. 더보기
점화식은 행렬의 거듭 제곱을 이용해서, DP 보다 빠르게 구할 수가 있다 우리는 고등학교 시절, 점화식을 일반항으로 고치는 방법을 공부하였다. 그러나, 이 작업은 매우 기술적이여서 일반항으로의 변환이 그렇게 쉽지가 않다. 그러나, 행렬을 이용을 하면, 일반항을 매우 쉽게, 그리고 매우 빠른 속도로 구할 수가 있다. 위와 같은 점화식이 있다고 하자! 피보나치 수열의 점화식은 아래와 같다. p == q == 1이므로, 위 식을 아래와 같이 변형할 수가 있다. 위 식을 귀납적으로 표현을 하면 위와 같다. 이 식을 이용을 하면, 피보나치 수열의 (n+2) 번째 항을 알 수가 있다. ( 만약, 이 문제를 DP로 풀게 되면, O(십억)의 비용이 들지만, 행렬의 거듭 제곱을 이진수로 구하게 되면, O(log십억)으로 빠르게 구할 수가 있다.) ( 아래 문제 참조 ) https://www... 더보기

티스토리툴바