240322 TIL #353 알고리즘 복습

김춘복·2024년 3월 22일
0

TIL : Today I Learned

목록 보기
353/543
post-custom-banner

Today I Learned

오늘은 내일 코테 대비로 알고리즘 복습


알고리즘 복습

DP (동적계획법)

TIL #96

어떤 문제를 풀기위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 저장해 활용하는 방식. 답을 재활용 하는 것.

  • 큰 문제를 위에서부터 작은 문제로 나누는 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
  }

탐색

TIL #116

순차 탐색

선형 데이터 구조에서 원하는 값을 찾기위해 처음부터 순서대로 탐색하는 방법

  • 시간복잡도는 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;
  }

투 포인터

TIL #158

선형 자료구조에서 두 개의 포인터를 사용해 원하는 요소를 찾는 기법

  • 일반적으로 정렬된 데이터에서 두개의 포인터를 시작/끝에 두고 탐색을 한다.

  • 배열을 한 번만 순회하므로 시간복잡도는 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--;
    }
}

슬라이딩 윈도우

TIL #158

선형자료구조에서 연속된 요소의 부분집합을 효과적으로 탐색할 때 사용하는 기법

  • 부분배열의 크기는 고정되어있지만 배열상에서 좌표만 움직인다.

  • 정렬된 배열에서 효과적이며, 시간복잡도는 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

TIL #136

  • 트리나 그래프에서 모든 루트를 완전 탐색하고자 할 때, 최대한 깊게 들어가서 확인한 뒤 다른 루트를 찾는 방법

  • 이미 방문한 곳은 체크를 해둬 중복 순회하지 않도록 해야한다.

  • 재귀, 스택으로 구현한다.

  • 코드 예시

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

TIL #138

루트노드에서 시작해 깊이가 같은 노드를 모두 방문해 한 단계씩 더 깊은 노드로 방문해가는 방식

  • 모든 분기점을 다 검사하면서 진행한다. / 중복 순회하지 않도록 방문여부를 체크해야 한다.

  • 큐를 이용해 구현한다.

  • 코드 예시

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)

TIL #154

네트워크의 모든 정점을 가장 적은 수의 간선과 비용(가중치)으로 연결하는 것

  • 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(유니온파인드)

TIL #155

두 노드가 같은 그래프에 속하는지 판단하는 알고리즘

  • 크루스칼에서 사이클 형성 여부를 판단할 때 사용한다.

  • 부모 노드를 찾는 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 (다익스트라)

TIL #163

음의 가중치가 없는 그래프의 한 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘

  • 최단 거리를 저장할 배열을 만들고 우선순위큐를 이용해 구현한다.

  • 시간복잡도는 우선순위큐를 사용할 경우 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(플로이드 워셜)

TIL #167

가능한 모든 노드 쌍에 대한 최단 경로를 구하는 알고리즘

  • 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);
    }
}

기타

에라토스테네스의 체

TIL #156

주어진 범위에서 소수를 구하는 알고리즘

  • 소수가 되는 수의 배수를 지우면 남는 수가 소수가 된다.

  • 코드 예시

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());

  }

}

유클리드 호제법

TIL #164

두 정수의 최대 공약수를 찾는 효율적인 알고리즘

  • 큰 수를 작은 수로 나머지가 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)
profile
Backend Dev / Data Engineer
post-custom-banner

0개의 댓글