2022 02 17

2022-02-17

알고리즘 문제풀이 - 최소 스패닝 트리

• 개요
  • 트리는 Cycle이 없어야 함!
  • 최소 스패닝 트리는 간선의 가중치 합이 최소가 되도록 하는 트리!
  • 최소 스패닝 트리가 되려면 간선은 (노드갯수 - 1)개 만큼 필요!

• Kruskal Algorithm
  • 작은 간선 가중치로 정렬 후 하나씩 탐색
  • Union & Find를 활용하여 Cycle이 생기는지 검사

• Prim's Algorithm
  1. 간선 정보들을 연결 리스트로 그래프 만들 것!
  2. Check 배열을 통해 갔는지 안갔는지 기록해둘 것
  3. 갈 수 있는 간선 중에 최소 간선을 PriorityQueue에 저장할 것!
  4. 하나씩 뽑아 Check 되어있는지 확인할 것!

알고리즘 문제풀이 - DP

• 개요
  • 큰 문제를 작은 문제로 소형화
  • 앞의 답을 그 다음 답을 구하는데 활용
  • Bottom Up + Memoization

• 최대 부분 증가수열(LIS)~

  • 처음에는 해당 원소가 들어가는지, 들어가지 않는지를 검사하는 방식으로 재귀를 통해 풀었음 (DFS)
    • 해당 방식은 O(2^n)으로 매우 비효율적

      public static int[] array;
      public static int numbers;
      public static int max;
      
      private void solution(int index, int subArrayLength, int currentMax) {
          if (index == numbers) {
              max = Math.max(max, subArrayLength);
          } else {
              if (currentMax > array[index]) {
                  solution(index + 1, subArrayLength, currentMax);
              } else {
                  solution(index + 1, subArrayLength + 1, array[index]);
                  solution(index + 1, subArrayLength, currentMax);
              }
          }
      }
      

  • Memoization을 통해 시간 복잡도를 줄이자!
    • 해당 원소를 마지막으로 하는 수열의 최대 길이를 담은 배열을 만들자!
    • 최대 길이를 담아 놓은 배열을 통해 이거 뒤로 들어갈 수 있는지를 검사
    • O(n^2) 의 시간 복잡도!

      public static int numbers;
      public static int[] array;
      public static int[] maxSubarrayLength;
      
      public static void main(String[] args) {
          Scanner in = new Scanner(System.in);
          numbers = in.nextInt();
          array = new int[numbers];
          maxSubarrayLength = new int[numbers];
          for (int i = 0; i < numbers; i++) {
              array[i] = in.nextInt();
          }
          maxSubarrayLength[0] = 1;
          int max = 0;
          for (int i = 1; i < numbers; i++) {
              int target = array[i];
              int maxSubarrayLen = 1;
              for (int j = i - 1; j >= 0; j--) {
                  if (target > array[j]) {
                      maxSubarrayLen = Math.max(maxSubarrayLen, maxSubarrayLength[j] + 1);
                  }
              }
              maxSubarrayLength[i] = maxSubarrayLen;
              max = Math.max(max, maxSubarrayLength[i]);
          }
      
          System.out.println(max);
      }
      

  • n이 1000이라면...
    • 2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
    • 1000^2 = 1000000