java
-
[Java]SetAlgorithm/자료구조 for Algorithm 2022. 3. 22. 00:52
Set Set은 내부 데이터를 중복해서 저장할 수 없고, 저장된 객체에 순서가 없다. 따라서 Set은 List와 같이 인덱스를 사용하여 원소에 바로 접근할 수 없다. HashSet Java는 내부적으로 Set 인터페이스를 따로 정의해 두었다. 이곳에 다양한 Set 구현체를 활용하여 코드를 작성할 수 있는데, HashSet은 기본적인 Set의 특성을 그대로 반영한 클래스이다. Set set = new HashSet(); set.add(5); set.add(5); set.add(1); set.add(1); set.add(3); System.out.println(set); 다음과 같이 중복된 자료를 저장하더라도 중복되지 않게 저장되는 것을 확인할 수 있다. TreeSet Set은 TreeSet을 사용하여 내부..
-
[Java]우선순위큐(PriorityQueue)Algorithm/자료구조 for Algorithm 2022. 3. 22. 00:16
우선순위큐(PriorityQueue) 스택은 후입선출, 큐는 선입선출을 특징을 가졌다. 이와 달리 우선순위큐는 사용자가 지정한 우선순위에 의거하여 원소를 꺼내는 특징이 있다. 기본적인 사용 Java에서는 PrioryQueue 클래스를 이미 내부적으로 포함하고 있다. 이는 기본적으로 오름차순으로 수를 꺼낼 수 있도록 구현되어 있다. PriorityQueue pq = new PriorityQueue(); pq.offer(5); pq.offer(3); pq.offer(9); pq.offer(1); while(!pq.isEmpty()) { System.out.println(pq.poll()); } 정렬기준 정하기(사용자 정의) PriorityQueue의 생성하는 단계에서 Comparator 인터페이스를 재정의한..
-
[Java] 문자열 문제풀이시 자주 사용되는 내용들Algorithm/문자열 2022. 3. 21. 22:23
String ↔ Integer // String -> Integer int num = Integer.parseInt(string); // Integer -> String String string = Integer.toString(num); // Byte, Long, Float, Double 모두 동일한 함수를 가지고 있다. String ↔ Character /*** * String -> Character */ String sentence = "15151515"; // 한 글자 변환 char c = sentence.charAt(0); // 전체 글자 변환 char[] c_arr = sentence.toCharArray(); /*** * Character -> String */ // 한 글자 변환 Strin..
-
[Java]거듭 제곱의 계산Algorithm/수학&기타 2021. 4. 20. 17:17
*거듭 제곱의 계산 -> 거듭 제곱을 구현하는 방법은 간단하다. 기본적으로는 그 정의 그대로 어떤 수를 n번 곱하여 거듭제곱을 구현 가능하다. 하지만 n번 곱하기 때문에 시간복잡도는 O(n)이 걸린다는 것을 알 수 있다. *개선된 거듭 제곱의 계산 -> 이러한 거듭 제곱은 분할 정복을 기반으로 시간복잡도를 O(logN)까지 줄일 수 있다! -> 기본적인 아이디어는 다음과 같다. 예를 들어 5^10을 계산한다고 생각하였을 때, 아래와 같은 과정을 거쳐서 그 값을 구하는 것 이다. -> 따라서, 재귀를 이용하여 다음과 같은 거듭제곱을 구현할 수 있음을 알 수 있다. *구현 -> 점화식도 구하였으니 그대로 구현하기만 해주면 된다. import java.util.Scanner; public class Expon..
-
[Java]유클리드 호제법(Euclidean Algorithm)Algorithm/수학&기타 2021. 4. 19. 18:16
*유클리드 호제법(Euclidean Algorithm) -> 유클리드 호제법은 두 개의 자연수 or 두 개의 다항식의 최대공약수를 구하는 방법이다. ※ a는 b의 피제수(즉, 나누어지는 수)이므로 a > b이다. ※ 따라서 수식의 q는 몫, r은 나머지를 의미한다(따라서 r은 0보다 같거나 크고 b보다는 작아야 한다). -> 유클리드 호제법은 최대공약수를 구하는데 사용한다고 하였다. 최대공약수는 수학적으로 두 수의 모든 약수를 나열한 뒤 공통되는 약수 중 최대를 선택하거나 소인수 분해를 이용한 방법이 있지만, 유클리드 호제법을 이용하면 더 빠른 시간 안에 최대공약수를 구할 수 있다. *유클리드 호제법의 사용 -> 피제수가 제수에 의해 나누어 떨어진다면, 그 피제수와 제수의 최대공약수는 제수이다. 이 명제..
-
[Java]플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)Algorithm/그래프&최단경로 2021. 4. 15. 22:44
*플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) -> 플로이드-워셜 알고리즘은 음수 사이클이 없는 그래프내의 각 모든 정점에서 각 모든 정점에 까지의 최단거리를 모두 구할 수 있는 알고리즘이다. 다익스트라 알고리즘과는 다르게 그래프에 음수 사이클만 존재하지 않으면, 음의 가중치를 갖는 간선이 존재해도 상관이 없다는 것이다. ※음수 사이클 : 사이클의 모든 경로를 지나 원래 지점으로 돌아 왔을때, 최종적인 비용이 음수가 되는 경우. *플로이드-워셜 알고리즘의 이해 -> 플로이드-워셜 알고리즘은 다이나믹 프로그래밍 기법을 사용한 알고리즘이고, 인접 행렬을 이용하여 각 노드간 최소 비용을 계산한다. -> 플로이드-워셜 알고리즘은 모든 노드에서, 모든 노드로 가는 최소 비용을 단계적으로 ..
-
[Java]크루스칼 알고리즘(Kruskal Algorithm)Algorithm/그래프&최단경로 2021. 4. 15. 17:15
*크루스칼 알고리즘(Kruskal Algorithm) -> 크루스칼 알고리즘은 그래프에서 최소 비용 신장 부분 트리(최소 신장 트리 : Minimum Spanning Tree(MST))를 찾는 알고리즘이다. ※ 최소 신장 트리, 신장 트리와 같은 용어를 조금 더 자세히 알고 싶다면 위키백과를 참고하도록 하자. ko.wikipedia.org/wiki/%EC%8B%A0%EC%9E%A5_%EB%B6%80%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 신장 부분 그래프 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 그래프의 신장 부분 나무 그래프 왼쪽의 그래프는 오른쪽과 같이 총 8개의 신장 부분 나무 그래프들을 갖는다. 그래프 이론에서, 신장 부분 그래프(身長部分gr..
-
[Java]서로소 집합(Disjoint Set)(Union-Find)(Merge-Find Set)Algorithm/자료구조 for Algorithm 2021. 4. 15. 11:08
*서로소 집합(Disjoint Set) -> 서로소 집합 자료구조는 상호 배타적으로 이루어진 집합(서로소 집합 : 공통 원소가 없는 두 집합)을 효율적으로 표현하기 위해 만들어진 자료구조이다. -> 서로소 집합은 서로 다른 두 개의 집합을 병합하는 연산(Union)(Merge)과 집합의 원소가 어떤 집합에 속해 있는지 판단하는 연산(Find)을 기반으로 구현되기 때문에, Union-Find 혹은 Merge-Find Set이라고도 불린다. -> 서로소 집합을 구현하는 방법은 연결 리스트를 이용하는 방법과, 트리를 이용하는 방법이 있는데, 이 글에서는 트리를 이용하는 방법에 대해서만 다룬다. *서로소 집합의 단순 구현(트리) -> 서로소 집합은 기본적으로 총 3가지 연산(MakeSet, Find, Union..
-
[Java]다익스트라 알고리즘(Dijkstra Algorithm)Algorithm/그래프&최단경로 2021. 3. 12. 00:40
*다익스트라 알고리즘(Dijkstra Algorithm) -> 다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다. -> 초기 모델은 O(V^2)의 시간복잡도를 가졌다. 이후 우선순위 큐 등을 이용한 고안된 알고리즘이 탄생했고, 현재는 O((V+E)log V)의 시간복잡도를 가지고 있다(만일 연결 그래프라면 O(ElogV)까지 시간 복잡도를 줄일 수 있다고 한다). 일반적으로는 그래프가 희소 그래프인 경우에 우선순위 큐를 이용하는 것이 낫다고 한다. ※음의 가중치를 가지면 안되는 이유는 최소 비용의 음의 무한대 발산, 그리디 알고리즘 적용 불가능 등이 있다. 후자는 제일 아래에 있는 다익스트라 알고리즘 정당성 증명을..
-
[Java]다음 순열(Next Permutation)Algorithm/완전 탐색 2021. 2. 25. 22:47
*다음 순열(Next Permutation). -> 다음 순열이란, 말 그대로 해당 숫자의 다음에 올 순열의 수를 의미한다. Ex) {1, 2, 3}에서 3개를 선택하는 경우 순열은 123, 132, 213, 231, 312, 321이 있다. 그렇다면 123 다음에 올 순열은 무엇일까? 132이다. 즉, 123의 다음 순열은 132임을 알 수 있다. *다음 순열 구하기 -> 다음 순열을 구하는 로직은 우리가 무의식적으로 다음 순열을 구하는 로직을 천천히 곱씹으며 구체화시켜보면 가능하다. 우리는 이미 다음 순열을 구하는 방법을 알고 있다!(다만 막상 논리적 순서로 나타내보려 하면 헷갈리고 어려울 뿐이다...) -> 규칙성을 찾기 위해서는, 작은 경우부터 침착하게 내가 어떻게 구하고 있는지 분석해보면 된다...