Algorithm/알고리즘 (Java)

문자열 알고리즘

용어 정리 |S| 문자열 S의 길이 S = “abcde” 라면 |S| = 5 S[i] (0 ≤ i < |S|) 문자열 S의 i번 글자 S = “abcde” 라면 S[3] = d S[i…j] 문자열 S[i] 부터 S[j] 까지 부분 문자열 S = “abcde” 라면 S[1…3] = bcd S[…a] 문자열 S[0] 부터 S[a] 까지 부분 문자열 S = “abcde” 라면 S[…3] = abcd S[b…] 문자열 S[b] 부터 S[|S|-1] 까지 부분 문자열 S = “abcde” 라면 S[3…] = de 문자열 검색 긴 문자열 H가 문자열 N을 부분 문자열로 포함하는지 확인하는 방법 H = “avava” N = “ava” 라면 N이 출현하는 모든 인덱스를 반환하는 알고리즘을 작성한다고 하자 이때 결과값은..

[Java] BFS : 너비 우선 탐색

너비우선탐색 개요 너비 우선 탐색은 최초 위치에서 가까운 노드들을 우선적으로 탐색하는 방법이다. 여기서 가깝다는 의미는 가중치가 적은 것이 아니라, 몇 번 만에 도달할 수 있는가를 의미한다. 시간 복잡도 인접리스트로 구현된 경우에는 각 노드마다 모든 간선을 확인해야 하므로, O(|V|+|E|) 입접 행렬로 구현된 경우에는 각 노드마다 다른 노드로 연결되어 있는지 확인해야 하므로, O(|V|^2) 동작 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Vector; public class 너비_우선_탐색 { // 그래프의 인접리스트 static Vector adj; static Vector bfs(int start) { Vec..

[Java] DFS : 깊이 우선 탐색

DFS : 깊이 우선 탐색 개요 그래프의 모든 정점을 특정한 순서로 탐색하는 그래프의 탐색 알고리즘 중 하나이다. 정점 1로부터 시작해서 모든 정점을 탐색하기 위한 목적이다. 현재 지점으로부터 인접한 지점을 찾아야 하므로 "재귀" 를 사용한다. 현재 방식은 단순히 "탐색" 만 할 뿐이며, D, F 등의 계산은 하지 않는다. 탐색의 우선순위는 정점의 번호가 작은 순이다. 파란색 정점은 방문 했다는 표시이다. 주황색 정점은 방문한 뒤 되돌아온다는 표시이다. 동작 코드 import java.util.Vector; public class 깊이_우선_탐색 { // 그래프의 인접 리스트 표현 static Vector adj; // 각 정점을 방문했는지 여부를 나타낸다. static Vector visited; //..

[Java] 트라이(Trie) 알고리즘

트라이(Trie) 알고리즘 개요 정렬된 배열에서 특정 정수 값을 찾기 위한 시간 복잡도는 $O(\log N)$ (N은 배열의 크기)이다. 예를 들어서 1~64 까지 임의의 수를 찾기 위한 최대 시도 횟수는 6번이다. 그러면 문자열을 찾기 위한 시간 복잡도는 어떻게 될까? 문자열을 찾기 위해서 각 문자마다 어디에 위치하는지 찾아야 한다. 이는 $O(\log N)$의 연산을 하고, 문자열의 길이가 M이라고 했을 때, 총 시간 복잡도는 $O(M\log N)$이 된다. 하지만 트라이 알고리즘을 사용한다면, 내가 원하는 원소를 $O(M)$만에 할 수 있다. (공간과 시간의 Trade Off를 이용..) 트라이 알고리즘은 트리를 이용하여 구현한다. 각 원소마다 HashMap이 존재하여 다음 문자의 위치로 이동하는 ..

[Java] 프림 최소 스패닝 트리

프림 최소 스패닝 트리 도입 스패닝 트리 보통 '신장 트리' 라고 알려진 이 트리 형태는 사이클이 없고 모든 정점이 연결된 형태의 트리이다. 대표적으로 크루스칼, 프림 2가지 방식이 있는데 여기서는 프림만 다룬다. 크루스칼 알고리즘은 여기저기 만들어진 트리 조각들을 합쳐서 스패닝 트리를 만드는 반면, 프림 알고리즘은 하나의 시작점으로 구성된 트리에 간선을 추가하는 방식이다. 시간 복잡도 그냥 단순히 정점을 추가할 때 마다 간선을 검색한다면 $O(|E||V|)$ 의 시간 복잡도를 갖으나, 최적화를 통해 $O(|V|^2+|E|)$ 가 될 수 있다. 알고리즘 시작점을 기준으로 트리에 추가할 정점을 추가 기존 트리에 존재하지 않으면서, 가중치가 가장 작은 간선 선택 선택된 정점으로부터 기존 정점(u)까지 최저비..

[Java] 상호 배타적 집합

상호 배타적 집합 개요 ㄹ 두 원소가 같은 트리에 속했는가? -> 각 원소가 포함된 트리의 루트를 찾은 뒤 이들이 같은 지 비교 if 루트가 같다면 두 노드가 같은 트리에 속함 else 루트가 다르다면 두 노드가 다른 트리에 속함 -> 합치기 연산 시행 루트 노드는 자기 자신을 가리킴 static class DisjointSet { // parent : 각 노드의 부모 위치 Vector parent; // rank : 각 노드의 높이 Vector rank; public DisjointSet(int n) { parent = new Vector(); rank = new Vector(); // 노드 수 만큼 반복 for (int i = 0; i < n; i++) { // 처음은 자기 자신이 부모 parent...

[Java] 크루스칼 최소 스패닝 트리

크루스칼 최소 스패닝 트리 도입 스패닝 트리 보통 '신장 트리' 라고 알려진 이 트리 형태는 사이클이 없고 모든 정점이 연결된 형태의 트리이다. 대표적으로 크루스칼, 프림 2가지 방식이 있는데 여기서는 크루스칼만 다룬다. 알고리즘 모든 간선을 가중치의 오름차순으로 정렬 간선을 트리에 추가 (단, 사이클이 생기는 간선은 고려 제외) 사이클이 생기는 것을 어떻게 판단하는가? -> 상호 배타적 집합 자료구조 사용 동작 과정은 다음과 같다. 코드 import java.util.Comparator; import java.util.Vector; public class 크루스칼_최소_스패닝_트리 { static class DisjointSet { // parent : 각 노드의 부모 위치 Vector parent; ..

[Java] 위상정렬 알고리즘

개요 위상정렬은 의존성이 있는 작업들이 주어질 때 어떤 순서로 수행해야 하는지 계산하는 알고리즘이다. 예를 들어서 A, C 가 끝나야 B를 작업한다고 하자. 이 경우에 탐색 순서를 A->C->B or C->A->B 순으로 해야한다. 위상 정렬의 특징은 그래프 내 사이클이 없는 방향그래프라는 점이다. 위상 정렬을 구현하는 방법은 깊이 우선 탐색의 응용 들어오는 간선이 하나도 없는 정점을 하나씩 찾아서 지우는 방식 2가지가 있다. 구현 1. 깊이 우선 탐색의 응용 import java.util.Vector; public class 깊이_우선_탐색 { // 그래프의 인접 리스트 표현 static Vector adj; // 각 정점을 방문했는지 여부를 나타낸다. static Vector visited; // 결..

[Java] 다익스트라(Dijkstra) 알고리즘

개요 다익스트라 알고리즘은 최단경로를 찾기 위한 알고리즘이다. 주의할 점은 음수 가중치를 갖는 간선을 가지면 안된다. 음수가 되는 사이클을 돌면 가중치가 음의 무한까지 발산하기 때문 설명 인접 노드라고 해서 최단경로가 아니라는 점에 주목하자. 위와 같은 형태의 그래프에서 0->3 까지 바로 갈 수 있지만, 0->1->2->3 경로로 가는 거리가 가장 짧기 때문에 최단경로는 후자가 된다. 다익스트라 알고리즘은 경로를 기준으로 하는 우선순위 큐를 이용한다. 우선순위 큐에는 정점의 번호와 지금까지 찾은 해당 정점까지의 최단거리를 쌍으로 갖는다. 최단거리 쌍(시작점으로 부터거리, 정점의 번호) 각 정점까지 최단거리를 저장하는 배열 dist[]를 정의한다. 해당 정점으로 부터 갈 수 있는 모든 노드를 검사한다. ..

8/12 (목) 자바 코딩 스터디

2618 경찰차9251 LCS10164 격자상의 경로2839 설탕 배달1010 다리 놓기 1010번 다리 놓기 강 서쪽에서 동쪽으로 다리를 잇는 프로그램 다리끼리는 서로 겹쳐질 수 없다. 결국에는 강 동쪽의 구역(M) 중 강 서쪽의 구역(N)만큼을 순서 상관 없이 뽑는 경우의 수 를 출력하는 프로그램이다. 첫 번째는 간단 수학식으로 해결해 보았다. 1. 다이나믹 프로그래밍 C(3, 2) = c(2, 1) + c(2, 2) = C(1, 0)+C(1, 1) + C(1, 1)+C(1, 2) C(M, N) = C(M-1, N-1) + C(M-1, N) nCr = n-1Cn-1 + n-1Cn; public static int buildBridge2(int n, int r) { if (n == r) { return..