211031 일 Algorithms TIL

병사 배치

• 동빈북 ch16 다이나믹 프로그래밍 dp 문제
• 코드
• 문제

동빈북 해설

• 가장 긴 증가하는 부분수열 LIS Longest Increasing Subsequence
  • 하나의 수열이 주어졌을 때 값들이 증가하는 형태의 가장 긴 부분 수열을 찾는 문제
  • D[i] = array[i] 를 마지막으로 가지는 부분수열의 최대 길이라고 저장하면 부분수열을 계산하는 점화식은 다음과 같다. 이 때 초기의 DP 테이블의 값은 모두 1로 초기화 한다.
    • 모든 0 <= j < i 에 대하여 D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

내 풀이

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] soldiers = new int[n];
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxV = 1;
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            soldiers[i] = x;
            for(int j=i-1; j >=0; j--) {
                if(soldiers[j] > x) {
                    dp[i] = dp[j] + 1;
                    maxV = Math.max(maxV, dp[i]);
                    break;
                }
            }
        }
        System.out.println(n - maxV);
    }

• 처음엔 이렇게 풀리는데 자꾸 틀리는 거. 근데 왜 틀리는지 몰랐다. 문제는 저 자기보다 큰 값을 찾는 것을 체크해주는 부분이 문제였다. 자기보다 큰 값을 제일 먼저 찾는 것의 + 1 하도록 되어 있는데 그럼 안된다. 예를 들어 arr = { .. 7, 9} 이고 dp = { ... 10, 3} 이라고 되어 있을 때 x 값이 5가 들어오면 제일 먼 저 찾는 자기보다 큰 값이 9 이니까 dp에 4가 들어갈 터인데 사실은 10 + 1 해서 11이 들어가는 것이 맞으니까 처음부터 다 검사를 해봐야 한다. 자기보다 큰 모든 값들에서 +1 한 값들 중 max를 기입해야 한다.

 public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] soldiers = new int[n];
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxV = 1;
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            soldiers[i] = x;
            for(int j=i-1; j >=0; j--) {
                if(soldiers[j] > x) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    maxV = Math.max(maxV, dp[i]);
                }
            }
        }
        System.out.println(n - maxV);
    }

• 이렇게 고쳤더니 통과

못생긴수

• 동빈북 ch16 다이나믹 프로그래밍 dp 문제
• dp라고 하지만 그냥 처음부터 해당 수를 구하는 느낌이다.
• 코드