230529 Today I Learned

오늘 TIL에는 저번 TIL에서 정리한 동적계획법을 적용해 코테 문제를 풀이한 걸 정리해보려 한다.

정수삼각형

• https://school.programmers.co.kr/learn/courses/30/lessons/43105

• 문제 : dp문제인지 모르고 봤어도 dp를 적용했을 꺼 같긴 했다. 중간 해들을 다 저장해두고 최종값들만 비교하면 문제 풀이가 쉬워 보인다. 하지만 어떤 자료구조 형태로 저장할 지 고민이었다.

• 시도 :

1. 1차원 배열 : 배열 크기를 미리 지정하고 안에 저장된 요소들을 구분하기 번거로워 구현하다가 pass

2. ArrayList : 크기를 미리 지정안해도 되는 점에서 편하긴 했지만 저장된 요소들 구분하기 번거로워 pass

3. 이중배열 : 모든 중간해들을 저장하려고 하니 배열안의 배열의 크기가 2^n 만큼 커져서 사이즈를 정할때 공간복잡도가 심하게 낭비되어 pass

• 해결 :
  이중배열을 쓰되 크기를 원본과 삼각형과 같게 수정. bottom-up 방식으로 순차적으로 중간해를 구해서 올라감.
  어차피 최종값에서 max값을 찾는 거라 중간해도 max가 아닌 값들은 dp에 저장할 필요가 없음.
  좌우측변은 생각해보니 좌우측변의 계속된 누적합이라 따로 케이스를 나눔.

• 풀이 :

public class T_정수삼각형 {
  public int solution(int[][] triangle) {
    int size = triangle.length;
    int[][] dp = new int[size][];
    dp[0] = triangle[0];
    if (size == 1) return dp[0][0];

    for (int i = 1; i < size; i++) {
      dp[i] = new int[triangle[i].length];
      for (int j = 0; j < dp[i].length; j++) {
        if (j==0) {
          dp[i][j] = dp[i-1][j] + triangle[i][j];
        } else if (j == dp[i].length-1) {
          dp[i][j] = dp[i-1][j-1] + triangle[i][j];
        } else {
          dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
        }
      }
    }
    int answer = 0;
    for (int i : dp[triangle.length-1]) {
      if (i>answer) answer = i;
    }
    return answer;
  }

• 개선점
  : 일단 위의 답은 프로그래머스 상에서는 문제없이 통과가 되었다. 혹시 추가적인 개선점이 있나 싶어서 gpt에 물어보니 새로 이중배열을 만들지 않고 int[][] triangle의 값을 그냥 누적합으로 바꿔버리면 메모리를 아껴서 공간복잡도를 낮출 수 있다고 했다. 이까진 생각을 못했는데 새롭게 배웠다.