오늘은 내일 코테 대비로 알고리즘 복습
어떤 문제를 풀기위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 저장해 활용하는 방식. 답을 재활용 하는 것.
큰 문제를 위에서부터 작은 문제로 나누는 Top-Down / 작은 문제를 해결해가며 아래서부터 순차적으로 올라가는 Bottom-Up으로 나뉜다.
코드 예시(bottom-up)
public class A_DP_피보나치 {
static long fiboBottomUp(int n) {
long[] dp = new long[n+1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i<=n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
public static void main(String[] args) {
int n = 10;
System.out.println(fiboBottomUp(n)); // 55
}
선형 데이터 구조에서 원하는 값을 찾기위해 처음부터 순서대로 탐색하는 방법
선형 데이터 구조에서 원하는 값을 찾기위해 탐색 범위를 절반씩 계속 나눠 탐색하는 방법
반드시 정렬이 되어 있어야 한다.
시간복잡도는 O(log n)
코드 예시
private static int binarySearch(int[] array, int target){
int low = 0;
int high = array.length-1;
while (low <= high){
int mid = (low + high) / 2;
if (array[mid] == target){
return mid;
} else if (array[mid] < target){
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
선형 자료구조에서 두 개의 포인터를 사용해 원하는 요소를 찾는 기법
일반적으로 정렬된 데이터에서 두개의 포인터를 시작/끝에 두고 탐색을 한다.
배열을 한 번만 순회하므로 시간복잡도는 O(n)
코드 예시
int[] arr = {15,3,11,5,7,1,4};
Arrays.sort(arr);
int target = 12;
int l = arr.length;
int left = 0;
int right = l - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
System.out.println(left + " " + right);
break;
} else if (sum < target) {
left++;
} else {
right--;
}
}
선형자료구조에서 연속된 요소의 부분집합을 효과적으로 탐색할 때 사용하는 기법
부분배열의 크기는 고정되어있지만 배열상에서 좌표만 움직인다.
정렬된 배열에서 효과적이며, 시간복잡도는 O(n)이다.
코드 예시
public int minSubArrayLen(int k, int[] nums) {
int minLength = Integer.MAX_VALUE; // 결과 저장
int sum = 0; // 윈도우 내부의 합
int left = 0; // 슬라이딩 윈도우의 왼쪽 포인터
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= k) {
minLength = Math.min(minLength, right - left + 1);
sum -= nums[left];
left++;
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
public static void main(String[] args) {
int[] nums = {2, 3, 1, 2, 4, 3};
int k = 7;
System.out.println(new ClassName().minSubArrayLen(k, nums)); // 결과는 2 ([4,3]이 가장 짧은 부분 배열)
}
모든 경우의 수를 고려하는 알고리즘 중 하나. 해를 찾는 도중 조건을 만족하지 않으면 이전 단계로 돌아가서 다른 가능성을 탐색하는 방법
트리나 그래프에서 모든 루트를 완전 탐색하고자 할 때, 최대한 깊게 들어가서 확인한 뒤 다른 루트를 찾는 방법
이미 방문한 곳은 체크를 해둬 중복 순회하지 않도록 해야한다.
재귀, 스택으로 구현한다.
코드 예시
public class A_DfsR {
private static boolean[] checked;
private static int[][] graph = {{},
// ... 생략
};
public static void dfs(int v){
checked[v] = true;
System.out.println(v + "번 노드를 탐색합니다.");
for (int i : graph[v]){
if (!checked[i]) dfs(i);
}
}
public static void main(String[] args) {
int start = 1; // 시작노드
checked = new boolean[11];
dfs(start);
}
}
루트노드에서 시작해 깊이가 같은 노드를 모두 방문해 한 단계씩 더 깊은 노드로 방문해가는 방식
모든 분기점을 다 검사하면서 진행한다. / 중복 순회하지 않도록 방문여부를 체크해야 한다.
큐를 이용해 구현한다.
코드 예시
public class A_BfsQ {
private static boolean[] checked = new boolean[11];
private static int[][] graph = {{},
// ... 생략
};
public static void bfs(int v){
checked[v] = true;
Queue<Integer> queue = new LinkedList<>();
queue.add(v);
while(!queue.isEmpty()){
int tmp = queue.poll();
System.out.println(tmp + "번 노드를 탐색합니다.");
for (int i : graph[tmp]){
if(!checked[i]){
queue.add(i);
checked[i] = true;
}
}
}
}
public static void main(String[] args) {
int start = 1; // 시작노드
bfs(start);
}
}
네트워크의 모든 정점을 가장 적은 수의 간선과 비용(가중치)으로 연결하는 것
정점을 기준으로 MST를 형성하는 알고리즘
시작정점을 정하고 연결된 정점 중 가중치가 가장 적은 정점을 선택해 계속 나아가는 방식
시간복잡도는 우선순위큐(최소 힙) 사용 시 O(E log V)
가중치가 적은 간선부터 선택해나가는 방식
간선을 오름차순으로 정렬해 사이클을 형성하는 간선을 제외하고 가장 적은 가중치의 간선을 차례대로 선택한다.
시간복잡도는 O(E log E) or O(E log V)
간선이 적으면 크루스칼, 많으면 프림이 더 유리하다.
코드 예시 (TIL #157 섬 연결하기)
import java.util.*;
class Solution {
static int[] root;
static int answer;
static int count;
public void union(int x, int y, int cost){
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY) return;
root[rootY] = rootX;
answer += cost;
count++;
}
public int find(int x){
if(root[x] != x){
root[x] = find(root[x]);
}
return root[x];
}
public int solution(int n, int[][] costs) {
if(n<=1) return 0;
answer = 0;
root = new int[n];
count = 0;
// unionfind 초기화
for(int i=0; i<n; i++){
root[i] = i;
}
// 크루스칼 적용하기 위해 sort
Arrays.sort(costs, Comparator.comparingInt(a -> a[2]));
// 크루스칼로 MST 구현
for(int i=0; i<costs.length; i++){
if(count >= n-1) break;
int x = costs[i][0];
int y = costs[i][1];
int cost = costs[i][2];
union(x,y,cost);
}
return answer;
}
}
두 노드가 같은 그래프에 속하는지 판단하는 알고리즘
크루스칼에서 사이클 형성 여부를 판단할 때 사용한다.
부모 노드를 찾는 find와 부모가 같지 않을 경우 합치는 union으로 구성되어 있다.
코드 예시
class UnionFind {
private int[] parent;
public UnionFind(int size) {
parent = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
}
음의 가중치가 없는 그래프의 한 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘
최단 거리를 저장할 배열을 만들고 우선순위큐를 이용해 구현한다.
시간복잡도는 우선순위큐를 사용할 경우 O((V+E) log V)
코드 예시
import java.io.*;
import java.util.*;
public class A_DijkstraPQ {
static List<List<Node>> graph;
static int V;
static int[] distance;
static class Node implements Comparable<Node> {
int vertex;
int weight;
Node(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.weight, other.weight);
}
}
public static void dijkstra(int index) {
Queue<Node> pq = new PriorityQueue<>();
distance = new int[V];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[index] = 0;
pq.offer(new Node(index, 0));
while(!pq.isEmpty()){
Node node = pq.poll();
int nv = node.vertex;
int nw = node.weight;
if(nw > distance[nv]) continue;
for(Node linkedNode : graph.get(nv)) {
int lv = linkedNode.vertex;
int lw = linkedNode.weight;
if(nw+lw < distance[lv]){
distance[lv] = nw+lW;
pq.offer(new Node(lv, distance[lv]))
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken()); // 정점의 개수
int E = Integer.parseInt(st.nextToken()); // 간선의 개수
graph = new ArrayList<>();
for(int i=0; i<V; i++){
graph.add(new ArrayList<>());
}
//
for(int j=0; j<E; j++){
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken()); // 시작노드
int end = Integer.parseInt(st.nextToken()); // 도착노드
int w = Integer.parseInt(st.nextToken()); // 가중치(거리)
graph.get(start).add(new Node(end, w));
// 양방향일 경우
graph.get(end).add(new Node(start, w));
}
// 알고리즘 실행
dijkstra(0);
// 결과 출력
for(int i=0; i<V; i++){
System.out.println(i+ "번 정점까지의 최단 거리는 " + distance[i]);
}
}
가능한 모든 노드 쌍에 대한 최단 경로를 구하는 알고리즘
DP를 기반으로 중간 노드를 거쳐 가는 경우를 고려해 최단 경로를 구한다.
3중 for문으로 사용해 시간복잡도는 O(V^3)
코드 예시
public class A_FloydWarshall {
// Integer.MAX_VALUE는 덧셈과정에서 overflow가 발생할 수있으므로 큰 값으로 초기화
final static int INF = 999999, V = 4;
void floydWarshall(int graph[][]) {
int dist[][] = new int[V][V];
// 초기값 설정
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
// 플로이드 워셜 알고리즘 적용
for (int m = 0; m < V; m++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][m] + dist[m][j] < dist[i][j])
dist[i][j] = dist[i][m] + dist[m][j];
}
}
}
printSolution(dist);
}
// 출력
void printSolution(int dist[][]) {
for (int i=0; i<V; ++i) {
for (int j=0; j<V; ++j) {
if (dist[i][j] == INF)
System.out.print("X ");
else
System.out.print(dist[i][j] + " ");
}
System.out.println();
}
}
public static void main (String[] args) {
int graph[][] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{4, INF, 0, 1},
{2, 5, 8, 0} };
A_FloydWarshall fw = new A_FloydWarshall();
fw.floydWarshall(graph);
}
}
주어진 범위에서 소수를 구하는 알고리즘
소수가 되는 수의 배수를 지우면 남는 수가 소수가 된다.
코드 예시
public class A_Eratos {
static boolean[] primeList;
static List<Integer> primes;
private static void eratos(int n){
if (n<=1) return;
primeList = new boolean[n+1];
primeList[0] = false;
primeList[1] = false;
for (int i=2; i<=n; i++){
primeList[i] = true;
}
for (int i=2; (i*i)<=n; i++){
if (primeList[i]){
for (int j= i*i; j<=n; j+=i) primeList[j] = false;
}
}
primes = new ArrayList<>();
for (int i=0; i<=n; i++){
if (primeList[i]) primes.add(i);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
eratos(n);
System.out.println(primes.toString());
}
}
두 정수의 최대 공약수를 찾는 효율적인 알고리즘
큰 수를 작은 수로 나머지가 0이 될때 까지 반복적으로 나눠 그 때의 작은수가 최대 공약수가 된다.
코드 예시
public static int gcdRecursion(int a, int b){
if (b==0) return a;
return gcdRecursion(b,a%b);
}