Computer Science Knowledge Storage

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

해당 문제는 결합법칙을 무시한 채 최대 값을 구하기 위한 문제입니다. - 연산에서는 왼쪽 값은 최댓값, 오른쪽 값은 최솟값이 되어야 최대값이 되고, + 연산에서는 두 값 모두 최대 값이 되어야 합니다. 이를 통해 dpMax 배열과 dpMin 배열을 통해 문제를 풀었습니다.

소스코드

class Solution {
        public int solution(String[] arr) {
            int n = arr.length / 2 + 1; // 숫자의 개수
            int[][] dpMax = new int[n][n];
            int[][] dpMin = new int[n][n];

            // 숫자 초기화
            for (int i = 0; i < n; i++) {
                dpMax[i][i] = Integer.parseInt(arr[i * 2]);
                dpMin[i][i] = Integer.parseInt(arr[i * 2]);
            }

            // 구간 길이
            for (int len = 1; len < n; len++) {
                for (int i = 0; i < n - len; i++) {
                    int j = i + len;
                    dpMax[i][j] = Integer.MIN_VALUE;
                    dpMin[i][j] = Integer.MAX_VALUE;

                    // i부터 j까지 연산자에 대한 분할 계산
                    for (int k = i; k < j; k++) {
                        String operator = arr[k * 2 + 1];
                        int maxLeft = dpMax[i][k];
                        int minLeft = dpMin[i][k];
                        int maxRight = dpMax[k + 1][j];
                        int minRight = dpMin[k + 1][j];

                        if (operator.equals("+")) {
                            dpMax[i][j] = Math.max(dpMax[i][j], maxLeft + maxRight);
                            dpMin[i][j] = Math.min(dpMin[i][j], minLeft + minRight);
                        } else if (operator.equals("-")) {
                            dpMax[i][j] = Math.max(dpMax[i][j], maxLeft - minRight);
                            dpMin[i][j] = Math.min(dpMin[i][j], minLeft - maxRight);
                        }
                    }
                }
            }

            return dpMax[0][n - 1]; // 전체 구간의 최댓값 반환
        }
    }

코드 설명

• int n = arr.length / 2 + 1; // 숫자의 개수 int[][] dpMax = new int[n][n]; int[][] dpMin = new int[n][n];
  • n: 숫자의 개수. 연산자는 숫자보다 항상 하나 적으므로, 전체 배열 길이의 절반(arr.length / 2)에 1을 더해 계산합니다.
  • dpMax[i][j]: i번째 숫자부터 j번째 숫자까지 가능한 최대값을 저장합니다.
  • dpMin[i][j]: i번째 숫자부터 j번째 숫자까지 가능한 최소값을 저장합니다.
• for (int i = 0; i < n; i++) { dpMax[i][i] = Integer.parseInt(arr[i * 2]); dpMin[i][i] = Integer.parseInt(arr[i * 2]); }
  
  • 각 숫자는 연산 없이 자기 자신이므로, dpMax[i][i]와 dpMin[i][i]를 해당 숫자로 초기화합니다.

for (int len = 1; len < n; len++) {
    for (int i = 0; i < n - len; i++) {
        int j = i + len;
        dpMax[i][j] = Integer.MIN_VALUE;
        dpMin[i][j] = Integer.MAX_VALUE;

• len: 현재 계산하려는 구간의 길이. 길이가 1부터 시작하여, 점차 늘어나며 모든 가능한 구간을 탐색합니다.
• i: 구간의 시작점.
• j: 구간의 끝점. 구간 길이가 len이므로, j = i + len으로 계산.

for (int k = i; k < j; k++) {
    String operator = arr[k * 2 + 1];
    int maxLeft = dpMax[i][k];
    int minLeft = dpMin[i][k];
    int maxRight = dpMax[k + 1][j];
    int minRight = dpMin[k + 1][j];

• k: 구간을 분할하는 기준점.
  • arr[k * 2 + 1]에서 연산자(+, -)를 가져옵니다.
  • k를 기준으로 왼쪽(i에서 k)과 오른쪽(k+1에서 j)의 최대/최소값을 가져옵니다.
    • maxLeft, minLeft: 왼쪽 구간 최대/최소값.
    • maxRight, minRight: 오른쪽 구간 최대/최소값.

if (operator.equals("+")) {
    dpMax[i][j] = Math.max(dpMax[i][j], maxLeft + maxRight);
    dpMin[i][j] = Math.min(dpMin[i][j], minLeft + minRight);
} else if (operator.equals("-")) {
    dpMax[i][j] = Math.max(dpMax[i][j], maxLeft - minRight);
    dpMin[i][j] = Math.min(dpMin[i][j], minLeft - maxRight);
}

• 연산자에 따라 결과를 계산
  • + 연산: 양쪽 구간의 최대/최소값을 더합니다.
  • - 연산: 왼쪽 최대값에서 오른쪽 최소값을 빼거나, 왼쪽 최소값에서 오른쪽 최대값을 뺍니다.
• 계산 결과를 갱신하며, dpMax[i][j]는 가능한 최대값, dpMin[i][j]는 가능한 최소값을 유지합니다.
• return dpMax[0][n - 1];
  • dpMax[0][n-1]: 입력 배열 전체(0번째 숫자부터 마지막 숫자까지)의 가능한 최대값을 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

원형으로 이루어진 집들에서 이웃집 체크를 할 때에 첫번째 집과 마지막 집을 체크하는 것이 문제였습니다. 이를 위해 동적 계획법을 두가지로 나누어 두 부분의 최댓 값중 더 큰 값을 반환하는 로직으로 문제를 해결하였습니다.

소스코드

class Solution {
    
    public int solution(int[] money) {
        int n = money.length;
        /* 
         * 첫번째 집을 포함하고 마지막 집을 빼는 경우
         * n까지 고려했을 때의 돈의 최댓값
         */ 
        int[] dp_includeFirst = new int[n]; 
        dp_includeFirst[0] = money[0];
        dp_includeFirst[1] = Math.max(money[1], money[0]);
        for(int i = 2; i < n-1; i++) {
            dp_includeFirst[i] = Math.max(money[i] + dp_includeFirst[i-2], dp_includeFirst[i-1]);
        }
        
        /* 
         * 첫번째 집을 제외하고 마지막 집을 선택하는 경우
         * n까지 고려했을 때의 돈의 최댓값
         */ 
        int[] dp_excludeFirst = new int[n]; 
        dp_excludeFirst[0] = 0;
        dp_excludeFirst[1] = money[1];
        for(int i = 2; i < n; i++) {
            dp_excludeFirst[i] = Math.max(money[i] + dp_excludeFirst[i-2], dp_excludeFirst[i-1]);
        }
        
        return Math.max(dp_excludeFirst[n-1], dp_includeFirst[n-2]);
    }
}

코드 설명

첫 번째 집을 포함하고 마지막 집은 제외.

• dp_includeFirst[i]: 0번째 집부터 i번째 집까지 고려했을 때, 훔칠 수 있는 최대 금액.
• 초기값:
  • 첫 번째 집(money[0])은 반드시 포함됨: dp_includeFirst[0] = money[0].
  • 두 번째 집은 첫 번째 집과 비교해 더 큰 금액 선택: dp_includeFirst[1] = Math.max(money[1], money[0]).
• for (int i = 2; i < n-1; i++) { dp_includeFirst[i] = Math.max(money[i] + dp_includeFirst[i-2], dp_includeFirst[i-1]); }
  • i번째 집을 포함하거나 포함하지 않는 경우 중 최대값 계산:
    • money[i] + dp_includeFirst[i-2]: 현재 집(i)을 포함하고, i-2번째 집까지의 최대값을 더함.
    • dp_includeFirst[i-1]: 현재 집을 포함하지 않고, i-1번째 집까지의 최대값.
  • 마지막 집(n-1)은 포함되지 않으므로 제외.

첫 번째 집을 제외하고 마지막 집을 포함.

• dp_excludeFirst[i]: 첫 번째 집을 제외하고, 1번째 집부터 i번째 집까지 고려했을 때의 최대 금액.
• 초기값:
  • 첫 번째 집은 제외되므로, dp_excludeFirst[0] = 0.
  • 두 번째 집은 money[1]으로 초기화: dp_excludeFirst[1] = money[1].
• for (int i = 2; i < n; i++) { dp_excludeFirst[i] = Math.max(money[i] + dp_excludeFirst[i-2], dp_excludeFirst[i-1]); }
  • 마지막 집(n-1)까지 포함.
• return Math.max(dp_excludeFirst[n-1], dp_includeFirst[n-2]);
  • 최대값 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

삼각형 형태로 있는 숫자를 이차원 배열로 생각하여 문제를 풀었습니다. 현재 행의 i-1에 j열 또는 j-1의 합으로 문제를 풀었습니다.

여기에서 ArrayIndexOutOfBoundsException이 나오지 않게 체크를 해줍니다.

소스코드

int solution(int[][] triangle) {
        int len = triangle.length;
        int[][] ans = new int[len][len];
        for(int i = 0; i < len; i++) {
            for(int j = 0; j <= i; j++) {
                ans[i][j] = triangle[i][j];
            }
        }

        // init
        for(int i = 1; i < len; i++) {
            ans[i][0] = ans[i - 1][0] + triangle[i][0];
            ans[i][i] = ans[i - 1][i - 1] + triangle[i][i];
        }

        for(int i = 2; i < len; i++) {
            for(int j = 1; j < i; j++) {
                ans[i][j] = Math.max(ans[i-1][j-1], ans[i-1][j]) + triangle[i][j];
            }
        }

        int answer = Integer.MIN_VALUE;
        for(int i = 0; i < len; i++) {
            answer = Math.max(answer, ans[len-1][i]);
        }

        return answer;
    }
}

코드 설명

• 초기화
  
  • len: 삼각형의 높이.
  • ans: 각 위치까지의 최대 합을 저장하는 2차원 DP 배열.
  • 삼각형의 값을 그대로 ans 배열에 복사합니다.

for (int i = 1; i < len; i++) {
    ans[i][0] = ans[i - 1][0] + triangle[i][0]; // 삼각형 맨 왼쪽 경로
    ans[i][i] = ans[i - 1][i - 1] + triangle[i][i]; // 삼각형 맨 오른쪽 경로
}

삼각형의 왼쪽 끝 경로와 오른쪽 끝 경로는 고정된 값만 참조하므로 초기화합니다.

• 왼쪽 끝 경로는 위쪽 요소에서만 내려옵니다.
• 오른쪽 끝 경로도 마찬가지입니다.

for (int i = 2; i < len; i++) {
    for (int j = 1; j < i; j++) {
        ans[i][j] = Math.max(ans[i - 1][j - 1], ans[i - 1][j]) + triangle[i][j];
    }
}

• 중간 경로 계산
  
  • 위치 ans[i][j]는 위에서 내려올 수 있는 두 가지 경로 중 더 큰 값을 선택합니다:
    • ans[i-1][j-1]: 왼쪽 대각선 위에서 내려오는 경로.
    • ans[i-1][j]: 바로 위에서 내려오는 경로.
  • 이 중 더 큰 값을 선택해 현재 위치의 값을 갱신합니다.
• 마지막 행에서 가장 큰 값을 조회 후 반환합니다.