Today I Learned
오늘은 내일 코테 대비로 알고리즘 복습
알고리즘 복습
DP (동적계획법)
어떤 문제를 풀기위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 저장해 활용하는 방식. 답을 재활용 하는 것.
-
큰 문제를 위에서부터 작은 문제로 나누는 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(n) / for문으로 순회한다.
이진 탐색
선형 데이터 구조에서 원하는 값을 찾기위해 탐색 범위를 절반씩 계속 나눠 탐색하는 방법
-
반드시 정렬이 되어 있어야 한다.
-
시간복잡도는 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]이 가장 짧은 부분 배열)
}백트래킹
모든 경우의 수를 고려하는 알고리즘 중 하나. 해를 찾는 도중 조건을 만족하지 않으면 이전 단계로 돌아가서 다른 가능성을 탐색하는 방법
DFS
-
트리나 그래프에서 모든 루트를 완전 탐색하고자 할 때, 최대한 깊게 들어가서 확인한 뒤 다른 루트를 찾는 방법
-
이미 방문한 곳은 체크를 해둬 중복 순회하지 않도록 해야한다.
-
재귀, 스택으로 구현한다.
-
코드 예시
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);
}
}BFS
루트노드에서 시작해 깊이가 같은 노드를 모두 방문해 한 단계씩 더 깊은 노드로 방문해가는 방식
-
모든 분기점을 다 검사하면서 진행한다. / 중복 순회하지 않도록 방문여부를 체크해야 한다.
-
큐를 이용해 구현한다.
-
코드 예시
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)
네트워크의 모든 정점을 가장 적은 수의 간선과 비용(가중치)으로 연결하는 것
- cycle이 되면 안되고, n-1개의 간선만 사용해 n개의 정점을 연결해야하며, 간선 가중치의 합이 최소여야한다.
Prim Algorithm(프림)
정점을 기준으로 MST를 형성하는 알고리즘
-
시작정점을 정하고 연결된 정점 중 가중치가 가장 적은 정점을 선택해 계속 나아가는 방식
-
시간복잡도는 우선순위큐(최소 힙) 사용 시 O(E log V)
Kruskal Algorithm(크루스칼)
가중치가 적은 간선부터 선택해나가는 방식
-
간선을 오름차순으로 정렬해 사이클을 형성하는 간선을 제외하고 가장 적은 가중치의 간선을 차례대로 선택한다.
-
시간복잡도는 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;
}
}Union-Find(유니온파인드)
두 노드가 같은 그래프에 속하는지 판단하는 알고리즘
-
크루스칼에서 사이클 형성 여부를 판단할 때 사용한다.
-
부모 노드를 찾는 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;
}
}
}최단 경로 알고리즘
Dijkstra Algorithm (다익스트라)
음의 가중치가 없는 그래프의 한 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘
-
최단 거리를 저장할 배열을 만들고 우선순위큐를 이용해 구현한다.
-
시간복잡도는 우선순위큐를 사용할 경우 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]);
}
}Floyd-Warshall(플로이드 워셜)
가능한 모든 노드 쌍에 대한 최단 경로를 구하는 알고리즘
-
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);
}- 최소 공배수는 두 수의 곱을 최대 공약수로 나눈 것과 같다.
LCM(a,b) = a * b / GCD(a,b)
꾸준히 성장하기 위해 매일 log를 남깁니다!