Algorithm
[Algorithm] 벨만-포드 알고리즘(Bellman-Ford Algorithm)
[Algorithm] 벨만-포드 알고리즘(Bellman-Ford Algorithm)
2023.03.30벨만-포드 알고리즘(Bellman-Ford Algorithm)? 벨만-포드 알고리즘은 한 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘이다. 특징 벨만-포드 알고리즘의 시간 복잡도는 O(VE)로, O((V+E)logV)인 다익스트라보다 시간 복잡도가 더 크지만, 다익스트라는 가중치가 음수인 경우에는 사용할 수 없다. 반면, 벨만-포드 알고리즘은 가중치가 음수인 경우에도 사용할 수 있기 때문에 음수인 가중치가 존재한다면 벨만-포드 알고리즘을 사용할 필요가 있다. 구현 P[A][B]는 A와 B사이의 거리라고 가정한다. 출발점으로부터 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. 실무에서는 보통 d의 원소 타입에 대한..
[Baekjoon] 1629: 곱셈
[Baekjoon] 1629: 곱셈
2023.03.21문제 a^b % c를 구하는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Q1629 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] input = br.readLine().split(" "); long a = Long.parseLong(input[0]); long b = Long.parseLong(input[1]); long c ..
[Data Structure] 트라이 트리(Trie Tree)
[Data Structure] 트라이 트리(Trie Tree)
2023.03.19트라이 트리(Trie Tree)? 트라이 트리는 문자열 검색을 빠르게 해주는 트리 형태의 자료구조이다. radix tree, prefix tree, retireval tree 라고도 한다. 여기서 트라이(Trie)는 retireval에서 따온 단어이다. 구현 위 그래프 처럼 car, cb, do, dog라는 단어를 저장한다고 가정한다. 먼저 노드를 하나 만들어 주어야 한다. import java.util.HashMap; import java.util.Map; public class Node { private final Map children; private boolean endOfWord; public Node() { children = new HashMap(); } public Map getChildr..
[Baekjoon] 6064: 카잉 달력
[Baekjoon] 6064: 카잉 달력
2023.03.18문제 1 1 부터 시작하여 각각 m과 n에 대한 모듈로 연산을 진행하여 x y가 될 때 까지 몇번이 걸리는지 구하는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Q6064 { private static StringBuilder sb; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); sb = new StringBuilder(); int t = Inte..
[Algorithm] 페르마의 소정리
[Algorithm] 페르마의 소정리
2023.03.18페르마의 소정리? 페르마의 소정리는 피에르 드 페르마가 알아낸 정리로서, 정수론의 가장 기본이 되는 정리이다. 이 내용을 간단히 말하면, 임의의 소수 p와 서로소인 수 a에 대해, a^(p-1)을 p로 나눈 나머지는 무조건 1이라는 말이다. 예를 들어, 3^6 = 729를 7로 나누면 나머지는 1이라는 사실을 알 수 있다. 증명 이항정리를 사용한 증명 먼저 페르마의 소정리는 다음과 동치이며, n = 0일 경우는 자명하다. 이항정리에 의하면 여기서, 0 < n < p이면 은 p의 배수이다. 따라서, 는 항상 성립하는 명제이다. 같은 방법으로 도 항상 성립한다. 따라서 n일 때 성립한다 가정하면, n+1, n-1일 때도 성립한다. 즉, 모든 정수 n에 대해 이 공식이 성립한다는 것을 알 수 있다. 기약잉여계..
[Baekjoon] 17626: Four Squares
[Baekjoon] 17626: Four Squares
2023.03.17문제 특정 숫자의 제곱수 합을 구할 때 그 수들의 최소 개수를 구하는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Q17626 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] dp = new int[n + 1]; dp[..
[Algorithm] 플로이드-워셜(Floyd-Warshall)
[Algorithm] 플로이드-워셜(Floyd-Warshall)
2023.03.12플로이드-워셜(Floyd-Warshall)? 플로이드-워셜은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이며 다익스트라보다 구현이 쉽다. 플로이드-워셜은 모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야하기 때문에 2차원 배열에 최단 거리 정보를 저장한다. 또한, DP의 특징을 가지고 있어서 노드의 개수(N)번 만큼의 단계를 반복하며 점화식에 맞게 2차원 배열을 갱신해나간다. 구현 설명 플로이드-워셜은 임의의 노드 s에서 e까지 가는데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와..
[Baekjoon] 1654: 랜선 자르기
[Baekjoon] 1654: 랜선 자르기
2023.03.11문제 다양한 길이를 가진 n개의 랜선을 가지고 일정한 길이를 가진 k개의 랜선을 만들 때 만들 수 있는 최대 길이를 구하는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Q1654 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] nk = br.readLine().split(" "); int n = Integer.parseInt(nk..
[Algorithm] 상계/하계(Upper Bound/Lower Bound)
[Algorithm] 상계/하계(Upper Bound/Lower Bound)
2023.03.11상계/하계(Upper Bound/Lower Bound)? Lower Bound와 Upper Bound는 이진 탐색을 기반으로 하여 경곗값을 찾는 알고리즘이다. 이진 탐색을 기반으로 하기 때문에 당연히 데이터가 정렬되어 있어야 한다. 값을 찾을 때, 원하는 값이 없을 때 못찾았다는 신호(-1, false 등)를 반환하는 일반적인 이진 탐색과 달리 Upper Bound와 Lower Bound를 이용하면 찾고자 하는 값 또는 그 값의 초과값이 처음 나타나는 위치를 찾을 수 있다. 때문에 주로 특정 값을 어느 위치에 삽입해야 하는지 탐색할 때 많이 사용한다. 상계 (Upper Bound) Upper Bound는 찾고자 하는 값(target)보다 큰 값의 처음 위치를 반환한다. 구현 public class Upp..
[Algorithm] 이진 탐색(Binary Search)
[Algorithm] 이진 탐색(Binary Search)
2023.03.11이진 탐색(Binary Search)? 이진 탐색이란 데이터가 정렬되어 있는 상태에서 탐색 범위를 줄여나가며 특정한 값을 탐색하는 알고리즘으로, 탐색할 때마다 탐색 범위가 반으로 줄어들기 때문에 속도가 빠르다는 장점이 있다. 구현 코드 public class BinarySearch { public static void main(String[] args) { int[] array = {1, 3, 4, 6, 7, 9, 10, 11, 14, 16, 17, 20}; int target = 16; int left = 0; int right = array.length - 1; while (left right가 되므로 종료한다) 시간 복잡도 선형 탐색의 경우 O(n)이지만 이진 탐색의 경우 O(log n)이므로 대부..
[Algorithm] 모듈러 산술(modular Arithmetic)
[Algorithm] 모듈러 산술(modular Arithmetic)
2023.03.09모듈로(Modulo) 연산 컴퓨팅에서 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다. 즉 일반적으로 정수 범위의 내에서 대부분 a를 n으로 나눈 나머지 r과 몫 q는 다음을 충족한다. 일반적으로 a와 n이 모두 정수인 상태에서 수행되지만 요즘은 많은 곳에서 정수 범위 이상의 피연산자를 사용할 수 있다. 하지만, mod 0은 Divide by Zero 에서 예외가 발생할 수 있기 때문에 주의해야한다. 이 모듈로 연산에 관련된 규칙이 모듈러 산술이다. 모듈러 산술(Modular Arithmetic) 모듈로 합동(Congruence Modulo) 두 정수 a, b와 정수 n (n > 1)이 주어질 때 n이 a, b의 차의 약수인 경우 (즉, a - b = kn을 ..
[Baekjoon] 1167: 트리의 지름
[Baekjoon] 1167: 트리의 지름
2023.03.08문제 트리에서 두 점 사이의 거리가 가장 긴 길이를 트리의 지름이라 하는데 트리의 지름을 구하는 문제이다 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q1167 { private static List tree; private static boolean[] visited; private static int maxVertex; private static int max; public static void main(String[] args) throws IOException { BufferedReader br = new..