Level 3 정수 삼각형 Python 3

https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3# 

코딩테스트 연습 - 정수 삼각형

 

최종 코드

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_정수삼각형.py

hwayeon351/Programmers-Algorithms

def solution(triangle):
    for i in range(len(triangle)-2, -1, -1):
        for j in range(len(triangle[i])):
            triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1])
    return triangle[0][0]

---

풀이 과정

triangle의 가장 바닥부터 위로 올라오면서 아래 칸의 왼쪽과 오른쪽 중에 큰 값을 더해가며 triangle의 꼭대기까지 구하면 거쳐간 최댓값을 구할 수 있다.

이 문제가 DP 알고리즘인 이유는 triangle의 아래 칸부터 위 칸으로 올라오면서 아래 칸의 왼쪽과 오른쪽 값을 참고하여 현재까지 거쳐온 값을 구할 수 있기 때문이다. 이를, DP의 bottom-up 방식으로 구현하였다.

현재 위치가 triangle[i][j]라면 한 칸 아래 칸의 왼쪽은 triangle[i][j]이며, 한 칸 아래 칸의 오른쪽은 triangle[i][j+1]이다.

#정수 삼각형
def solution(triangle):
    #바닥 위 부터 꼭대기까지 진행
    for i in range(len(triangle)-2, -1, -1):
        #아래 칸의 왼쪽과 오른쪽 중에 큰 값을 현재 삼각형 수에 더함
        for j in range(len(triangle[i])):
            triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1])
    #가장 꼭대기인 triangle[0][0]을 return
    return triangle[0][0]
#시간복잡도 = O(n^2), 공간복잡도 = O(n^2)

예제로 주어진 triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]의 경우 위 코드를 따라가면서 풀어보면 최종적으로 triangle = [[30], [23, 21], [20, 13, 10], [7, 12, 10, 10], [4, 5, 2, 6, 5]]이 되며, 삼각형의 꼭대기 값인 triangle[0][0] 값인 30이 정답이 된다.

삼각형의 구조에 따라 탐색하는 len(triangle[i])의 수가 바닥에서 꼭대기로 갈수록 1씩 감소하기 때문에, T(n) = (n-1) + (n-2) + (n-3) + (n-4) + ∙∙∙ + 3 + 2 + 1 = n(n-1)/2이다. 따라서 시간복잡도는 = O(n^2)이다.

공간복잡도는 triangle의 이차원 리스트의 사용으로 O(n^2)이다.