[DP] 정수 삼각형 - Python / JavaScript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

[문제 간단 요약]

• 꼭대기에서 시작해 바로 아래 왼쪽/오른쪽으로만 이동
• 지나간 숫자의 합이 최대가 되는 경로의 합을 반환

[문제 해결 방안]

• 동적 프로그래밍 적용
• 아래 행에서 위로 올라가며 각 칸에 만들 수 있는 최대 합을 누적
• 바텀업 방식 사용 시 전체 원소를 한 번씩만 갱신

[문제 해결 코드 - python]

def solution(triangle):
    answer = 0
    dp = []
    for i in range(len(triangle)):
        dp.append([0]*(i+1))
    for i in range(len(triangle[-1])):
        dp[-1][i] = triangle[-1][i]
    for y in range(len(triangle)-2,-1,-1):
        for x in range(len(triangle[y])):
            dp[y][x] = max(triangle[y][x]+dp[y+1][x], triangle[y][x]+dp[y+1][x+1])
    return dp[0][0]

[문제 해결 코드 - javascript]

function solution(triangle) {
  // 바텀업으로 triangle 자체를 갱신해 공간 절약
  for (let i = triangle.length - 2; i >= 0; i--) {
    for (let j = 0; j < triangle[i].length; j++) {
      triangle[i][j] += Math.max(
        triangle[i + 1][j],
        triangle[i + 1][j + 1]
      );
    }
  }
  return triangle[0][0];
}

[코드 개선점]

• 배열 재사용으로 공간 절약
  별도 dp 배열 대신 triangle을 직접 갱신해 추가 메모리 사용을 제거
• 중복 연산 제거
  triangle[y][x]를 한 번 읽어 변수에 담아 두 곳 더하는 형태로 미세 최적화 가능
• 루프 가독성 향상
  range(len(triangle) - 2, -1, -1)처럼 역순 반복을 명시해 바텀업 흐름을 분명하게 표현
• 타입/경계 안전성
  JS에서는 triangle[i + 1][j + 1] 접근 시 인덱스 범위 보장이 전제, 입력 형식 유효성 체크 추가 가능
• 복잡도
  총 원소 수가 약 n(n+1)/2, 시간 O(n^2), 공간 O(1)(제자리 갱신 기준)
• 확장성
  경로 자체가 필요하면 별도 parent 테이블을 두거나 역추적 배열을 추가해 경로 복원 가능