프로그래머스 LV 3 정수삼각형

문제 유형 : 동적계획법 (Dynamic Programming) 
https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

1. 동적계획법
동적 계획법이란 DP라고 하며, 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결괏값을 저장해 다시 큰 문제를 해결할 때 사용되는 것으로 , 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용해 효율적으로 값을 구하는 알고리즘 설계 기법이다. 

앞에서 구했던 답을 다시 활용하는 방식이다.  큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다 그래서 '기억하며 풀기' 라고도 많이 부른다.

재귀와 흡사하지만 일반적인 재귀를 단순히 사용하면 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 점이다. 

Memoization : 변수의 값에 따른 결과를 저장하고 메모하는 것

상향식과 하향식 두 가지 접근 방법이 있다. 


2. 풀이
1) 위에서부터 내려오는 방식을 사용 했다. 맨 처음 풀이를 생각하기 위해 수기로 적었을 때는 sum이라는 함수를 새로 호출하려고 시도 했다. 
sum[0][0] = triangle[0][0] 
sum[1][0] = triangle[0][0] + triangle[1][0] // 예시 기준 7 -> 3 
sum[1][1] =  triangle[0][0] + triangle[1][1] // 예시 기준 7 -> 8 
sum[2][0] = sum[0][0] + sum[1][0] + triangle[2][0] // 7 -> 3 -> 8 
... 
Feedback : 동적계획법에 대해 살펴보고 난 뒤
sum을 만들 필요 없이 triangle 배열에 계속 이전 값을 더해서 저장해주면 된다. 

2) 이런 식으로 모든 경우의 수를 생각하려 하니 풀 순 있겠다 싶었지만 당장 머릿속에 있는 것을 코드로 짜내기가 굉장히 힘들었다. 그래서 경우의 수를 나누기로 했다

3) 경우의 수 
- 왼쪽 끝을 훑을 때 // 예시 기준 7 -> 3 -> 8 -> 2-> 4
: 한 방향만 고려하면 된다. 즉 , answer = triangle[0][0]  + triangle[1][0] + triangle[2][0] .... 이다.
=> triangle[i][j] += triangle[i-1][0] 
- 오른쪽 끝을 훑을 때 // 예시 기준  7 -> 8 -> 0 -> 4 -> 5 
: 역시 한 방향만 고려하면 된다. 즉, answer = triangle[0][0] + triangle[1][1] + triangle[2][2] ... 위에서부터 쭉 내려 올 시 다음과 같다
=> triangle[i][j] += triangle[i-1][j-1]
- 왼쪽도 아니고 오른쪽도 아닌 가운데 
: 이 부분이 맨 처음 경우의 수 나누지 않고 구했을 때 가장 어려웠던 부분인데 이렇게 경우의 수를 나눠보니 조금 편하게 생각할 수 있었다. 현재 값 기준 이전값 왼쪽과 오른쪽 중 큰 값을 현재값에 더해주면 된다. 비교 부분은 max를 쓰면 되기 때문에 쉽게 생각할 수 있었다.

4) 실패 결과 
1. int  object is not iterable Error

실패 사진1

해결 => triangle[-1] 을 주어서 해결했다. max 함수는 반복가능한 정수가 들어있는 객체를 넣어주어야 하는데 triangle[i][j] 는 특정 정수 하나만을 가리키는 것이기 때문에 안된다 했던 것이다. 그래서 마지막 행을 나타내는 triangle[-1]을 넣어주었더니 해결했다

 2. 결괏값과 일치하지 않음

실패 사진2

해결 => i를 반복하는 범위 설정 문제였다. 그냥 별 생각없이 len(triangle)로 설정했더니 다음과 같은 문제가 발생했다
j가 0일 때 triangle[0][0] += triangle[-1][0] 즉 , 마지막 왼쪽 끝에 있는 4가 추가되었다. i의 범위를 다르게 하거나 i-1이 아닌 다른 방식을 취했어야 했다. 그래서 range를 1,len(triangle)로 설정해주었더니 해결 됐다.
3. 시간초과

해결 => answer을 else 구문 안에 한번 더 넣어주어서 중간 변수가 있어서 이를 계산할 때 추가적인 연산이 필요해서 시간 초과가 생겼다. answer을 밖으로 빼주었더니 해결 됐다. 


4. 최종 코드 

def solution(triangle):


    for i in range(1,len(triangle)):
        for j in range(len(triangle[i])):
            if j==0:
                 triangle[i][j] += triangle[i-1][j]
            elif i == j :    
                  triangle[i][j] += triangle[i-1][j-1]
            else :
                triangle[i][j] += max(triangle[i-1][j],triangle[i-1][j-1])

    return  max(triangle[-1])

5. 시간복잡도
삼각형의 높이인 n 이라 하면 n * (n-1) * (n-2) ... 이루어지기 때문에 O(N^2)이라고 할 수 있다.