(24.09.04) 코딩테스트 알고리즘 정리(동적 계획법 Dynamic Programming / 다익스트라 알고리즘)

개발 이력서/Portfolio 동시에 준비 + 기존 완성 프로젝트 Update/점검 상황에서 매일 알고리즘 학습을 하는게 워낙 어려운 일이 아닌 것 처럼 느껴져서 심리적으로 압박이 크다.

 

코딩테스트 준비이기도 하지만, 학습하면서, 로직에서 구현되어야할 알고리즘을 배우는 것도 나름 흥미가 있고,

학습한 동적 계획법 처럼 어떤 특정 패턴의 알고리즘이 아닌 로직을 구성하는 방법에 관한 것들도

실제 코드를 작성하는데 도움이 될 것으로 생각해서

 

내 언어로 하나하나 정리하면서 학습

 

---

동적 계획법 Dynamic Programming

• 하나의 문제를 큰 문제를 여러개의 문제로 쪼개서 결과를 저장 → 다시 해결에 사용하는 방식
• DFS에서의 재귀방식을 사용할 시, 과하게 많은 로직이 반복이 되거나, 또는 많은 양의 반복문을 계속해서 시도를 해야하는 경우에 사용

최적 부분 구조 (Optimal Substructure)

• 하나의 문제를 큰 문제를 여러개의 문제로 쪼개서 결과를 저장 → 다시 해결에 사용하는 방식
  • 구하고자 하는 문제에서의 최적의 해는 부문 문제들의 최적 해를 사용하여 도출해내는 방식
  • 최적의 해들을 결합하여 활용하는 방식

중복되는 부분 문제 (Overlapping Subproblems)

• 중복되는 로직(문제)를 단 한번만 사용하여, 중복을 최소화
• 한번만 계산한 문제의 결과값은 따로 저장하여 효율성을 주는방식
  • 단, 중복되는 문제가 없을 경우에는 강제로 사용 X

접근 방식에 따른 분류

메모이제이션 (Memoization)

• Top-Down 접근 방식을 시도할 때, 쪼개진 부분 문제들의 결과를 다시 재사용하기 위해서 저장, 즉 메모를 하는 것
  • Top-Down 접근 방식 : 시작 부터 끝 까지 계속 전의 값을 활용해서 다음 값에 전이를 시켜서 활용하는 방식
  • ex) 피보나치 수열

테이블화 (Tabulation)

• Bottom-up 접근 방식을 시도를 할 때, 쪼개진 부분 문제 중에서 작은 문제 부터 순서대로 해결해 나가는 방식
  • Bottom-up 접근 방식 : 기저 상태(최소 상태) 에서 계속 결과 값을 위로 점진적으로 전이 시켜서 최종적으로 값을 내는 방식
• 반복문을 사용하되, 값을 구하는 반복이 아닌, 어떠한 동적 계획법 테이브을 채우고(Table-Filling, 테이블 필링), 그 테이블에서의 값을 재사용하면서 최적의 해를 구하는 방식

동적 계획법 DP FLOW

1. 문제 정의
   • 문제를 어떻게 나눌 것인지, 각 부분 문제의 정의
2. 부분 문제의 수립
   • 원래 문제를 해결하기 위해 필요한 부분 문제를 정의
3. 초기 조건 설정
   • 가장 간단한 부분 문제의 해를 설정
     • 보통은 기본적인 값이나 상태를 정의
4. 부분 문제 해결
   • 각 부분 문제를 해결 → 결과를 저장
     • 이 때, 접근 방식인 메모이제이션 / 테이블을 사용하여 저장.
5. 결과 결합
   • 부분 문제의 결과를 결합, 활용하여 원래 문제의 최적 해를 도출

 

피보나치 수열 : 동적 계획법 활용 기본 예제

F(n)=F(n−1)+F(n−2)

• 수열의 값은 이전 두수의 합으로 정의
• 단, 시작은 0, 1의 초기값을 설정 후 다음에서 부터 법칙을 적용`

동적 계획법 DP 활용

Top-Down (Memoization)

• Map 을 만들어서 메모를 하는 형태
• 셀프 문제로 주어진 n번째까지의 피보나치 수열 중, 100을 넘기 직전의 마지막 수열 번째와 그 수열을 알려주는 예제

package Algorithm;

import java.util.*;

public class DP_Fibonacci_Memoization {

  private static Map<Integer, Integer> memo = new HashMap<>();

  public static void main(String[] args) {
    int n = 30;

    // 100 이 넘지 않는 피보나치 수열
    for (int i = 0; i <= n; i++) {
      if (memoization(i) >= 100) {
        System.out.println("100 직전의 피보나치 수열 " + (i - 1) + "번째 수열 : " + memoization(i - 1));
        break;
      }
    }
  }

  public static int memoization(int n) {

    // 초기값일 경우
    if (n == 0 || n == 1) {
      return n;
    }

    // 메모에 있을 경우
    if (memo.containsKey(n)) {
      return memo.get(n);
    }

    // 메모에 없을 경우, 그 만큼 계산5
    int result = memoization(n - 1) + memoization(n - 2);
    memo.put(n, result);
    return result;
  }
}

Bottom-Up (Tabulation)

package Algorithm;

public class DP_Fibonacci_Tabulation {
  public static void main(String[] args) {
    int n = 30;

    System.out.println("피보나치 수열 " + n + "번째 수열 : " + tabulation(n));

  }

  public static int tabulation(int n) {

    // 초기값일 경우
    if (n == 0 || n == 1) {
      return n;
    }

    // 테이블을 생성
    int[] table = new int[n + 1]; // 번째와 인덱스를 맞추기 위해서

    // 초기값 설정
    table[0] = 0;
    table[1] = 1;

    // 두번쨰 부터 테이블에 순차적으로 정리
    for (int i = 2; i <= n; i++) {
      table[i] = table[i - 1] + table[i - 2];
    }

    return table[n];
  }
}

---

다익스트라 Dijkstra

• 단일 출발점에서 마지막 지점까지의 최단 경로를 찾는 알고리즘
  • 기본적으로 모든 정점까지의 최단거리를 모두 구하는 알고리즘
• BFS와 달리 가중치가 양수인 존재하는 그래프에서 유용하게 사용
  • 음의 가중치가 존재해 버릴경우, 결과가 이상할 수 있음
  ex) 노드간 연결되어있다가 아닌, 노드마다 일정 구간 떨어져 있다고 가정한 문제에서 활용
• PriorityQueue 를 사용
  • 최단 거리리를 선택할 수 있음과 동시에 Neighbor 확장 가능

다익스트라 Dijkstra FLOW

1. 시작 정점 설정
   • 출발 정점을 선택
   • 그 정점까지의 거리를 0으로 설정
   • 나머지 모든 정점의 거리는 무한대(∞)로 설정
2. 방문하지 않은 정점 중에서 최단 거리를 가진 정점 선택
   • 출발 정점에서부터 반복적으로 최단 거리를 가진 정점을 선택
3. 선택된 정점에서 인접한 정점들로 경로를 확장
   • 선택된 정점의 인접한 정점들을 확인
   • 인접한 정점으로 가는 경로의 비용을 계산
   • 계산된 비용이 기존에 기록된 거리보다 짧으면, 그 거리를 갱신
4. 방문 완료 표시
   • 선택된 정점은 이제 방문한 것으로 표시하고, 더 이상 해당 정점으로부터 경로를 확장 X
5. 반복
   • 모든 정점을 방문할 때까지 2~4 단계를 반복합니다.
6. 결과
   • 출발 정점에서 다른 모든 정점까지의 최단 거리가 계산되어 있습니다.

최단 거리 계산

• 양의 가중치를 가지고 있는 그래프에서의 시작점과 끝점 사이의 최소 거리 계산

package Algorithm;

import java.util.*;

public class Dijkstra {

  public static Map<Integer, List<Node>> graph = new HashMap<>();

  public static void main(String[] args) {

    addEdge(1, 2, 4);
    addEdge(1, 3, 2);
    addEdge(2, 4, 5);
    addEdge(2, 5, 10);
    addEdge(3, 6, 3);
    addEdge(3, 7, 6);
    addEdge(4, 5, 1);
    addEdge(6, 7, 7);

    int start = 4;
    int end = 7;

    Results results = dijkstra(start, end);

    System.out.println("최단 거리 : " + results.minDistance);
    System.out.println("최단 경로 : " + results.minPath);
  }

  public static Results dijkstra(int start, int end) {
    // 필요한 자료구조 구성
    // PriorityQueue 에서는 비교할 것에 대한 기준으로 node 클래스의 distance를 지정
    PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));
    Map<Integer, Integer> distances = new HashMap<>();
    Map<Integer, Integer> previous = new HashMap<>();

    // 초기 설정
    for (Integer node : graph.keySet()) {
      distances.put(node, Integer.MAX_VALUE); // 그래프의 모든 노드의 깅리을 무한대로 설정
    }
    pq.add(new Node(start, 0));
    distances.put(start, 0);

    // 거리찾기 시작
    while (!pq.isEmpty()) {
      Node currentNode = pq.poll();
      int current = currentNode.node;

      // 시작 노드가 End일 경우
      if (current == end) {
        break;
      }

      // 이웃 노드들을 탐색
      for (Node neighborNode : graph.get(current)) {
        // 현재 - 이웃 노드간 길이 연산
        int currentDistance = distances.get(current) + neighborNode.distance;

        // 기존보다 작으면 자료넣기
        if (currentDistance < distances.get(neighborNode.node)) {
          distances.put(neighborNode.node, currentDistance);
          previous.put(neighborNode.node, current);
          pq.add(new Node(neighborNode.node, currentDistance));
        }
      }
    }

    // 경로 정리
    List<Integer> path = new ArrayList<>();
    if (distances.get(end) != Integer.MAX_VALUE) {
      // prvieous로 경로 복기
      for (Integer node = end; node != null; node = previous.get(node)) {
        path.add(node);
      }

      Collections.reverse(path);
    }

    return new Results(distances.get(end), path);

  }

  public static void addEdge(int u, int v, int distance) {
    graph.putIfAbsent(u, new ArrayList<>());
    graph.putIfAbsent(v, new ArrayList<>());

    graph.get(u).add(new Node(v, distance));
    graph.get(v).add(new Node(u, distance));
  }

  static class Node {
    int node;
    int distance;

    Node(int node, int distance) {
      this.node = node;
      this.distance = distance;
    }
  }

  static class Results {
    int minDistance;
    List<Integer> minPath;

    Results(int minDistance, List<Integer> minPath) {
      this.minDistance = minDistance;
      this.minPath = minPath;
    }

  }

}

 

---

기본적인 알고리즘 FLOW와 더불어서 알고리즘 코드들도 스스로 생각하고 쓰면서 학습을 하고자 했다.

주먹구구로 코드카타, 코딩테스트 문제를 풀다가 한두시간은 한문제만 잡고 늘어진경험이 많아 시간이 걸리더라도

최단거리문제, 또는 전체적인 다이내믹 프로그래밍 방법 등은 유용하므로 빠르게 칠 수 있도록 더 연습을 해야.