DP - LIS, 냅색 알고리즘

LIS (Longest Increasing Subsequence)

주어진 수열에서 가장 긴 증가하는 부분 수열을 찾는 알고리즘이다.

부분 수열은 원래 수열의 순서를 유지하되, 연속하지 않은 원소들로 이루어진 수열을 말한다.

  public static int solution() {
    Collections.sort(bricks);
    
    dy[0] = bricks.get(0).height;
    int answer = dy[0];
    
    for (int i = 1; i < n; i++) {
      int max = 0;

      // 이 부분 중요
      for (int j = i-1; j >= 0; j--) {
        if (bricks.get(i).weight < bricks.get(j).weight && dy[j] > max) {
          max = dy[j];
        }
      }
      
      dy[i] = max + bricks.get(i).height;
      answer = Math.max(answer, dy[i]);
    }
    
    return answer;
  }

 

냅색 알고리즘 (Knapsack Problem)

주어진 가방의 용량(무게) 안에서 가장 가치가 높은 물건들의 조합을 찾는 최적화 문제를 해결하는 알고리즘이다.

  private static int solution() {
  
    for (int i = 0; i < n; i++) {
      Problem problem = problems.get(i);
      int score = problem.score;
      int time = problem.time;
      
      // 이 부분 중요
      for (int j = m; j >= time; j--) {
        dy[j] = Math.max(dy[j], dy[j-time]+score);
      }
    }

    return dy[m];
  }

 

동전, 벽돌, 문제 등등 사용할 수 있는 개수(횟수)가 유한할 때와 무한할 때의 차이점이 있다.

 

유한할 때(1개)는 j를 뒤에서부터 순회시킨다.

무한할 때는 j를 앞에서부터 순회시킨다.

 

유한하지만 2개, 3개 중복해서 사용할 수 있다면, 3중 다이나믹 등의 고도화된 DP 알고리즘이 필요하다.

 

 

 

냅색 알고리즘은 또 Fractional Knapsack Problem, 0/1 Knapsack Problem으로 나뉜다.

 

 

 

 

//

추후 내용 보강 예정