[Python] 동적계획법(Dynamic Programming) : 정수 삼각형

 

1시간정도 삽질하는데 도저히 풀리지가 않아서 DP 알고리즘에 대해 찾아보고 이해한 후에 풀었더니 바로 풀렸다

앞으론 하다가 안풀리면 알고리즘 공부를 해야겠다

 

 

 

https://youtu.be/0bqfTzpWySY?si=UI57iprAFi1TFG7l

=> 이해하는데 많은 도움이 된 영상!!!

 

 

 

---

 

 

문제

 

 

 

---

 

 

코드

def solution(triangle):
    # print('triangle: ', triangle)

    dp_lst = []
    for idx, floor in enumerate(triangle):
        # print('================ dp_lst: ', dp_lst)
        if idx == 0:
            dp_lst.append(triangle[idx])
        else:
            # print(floor)
            tmp_lst = []
            for idx2, num in enumerate(floor):
                # print('idx2:', idx2, 'num:', num)
                # print('len(floor)-1', len(floor)-1)
                if idx2 == 0:
                    start_val = num + dp_lst[idx-1][idx2]
                    tmp_lst.append(start_val)
                elif idx2 == len(floor)-1:
                    last_val = num + dp_lst[idx-1][idx2-1]
                    tmp_lst.append(last_val)
                else:
                    left_val = num + dp_lst[idx-1][idx2-1]
                    right_val = num + dp_lst[idx-1][idx2]
                    big_val = max(left_val, right_val)
                    tmp_lst.append(big_val)
            dp_lst.append(tmp_lst)

    answer = max(dp_lst[-1])
    
    return answer

 

 

 

 

---

 

설명

 

https://youtu.be/0bqfTzpWySY?si=UI57iprAFi1TFG7l

위 영상의 핵심 내용을 적어봅니다

확실히 영상을 보는게 도움이 많이 됩니다

 

 

동적 프로그래밍은 완전탐색, DFS, BFS와 같이 수많은 경우의 수를 전부 따져봐야 하는데 
그 경우의 수가 너무 많아서 속도가 느려지는 문제를 개선하고자 수행 시간을 단축하고자 만들어진 알고리즘이다.

 

DP 삼각형이라는 해당 위치까지 올 수 있는 최댓값을 저장하는 배열을 만들어서 풀자

 

DP의 목적: 메모리를 사용해서 중복 연산을 줄이고 중복 연산을 줄여서 수행 속도를 개선한다
메모리를 사용한다 => DP 삼각형과 같이 배열 혹은 자료구조를 만든다
중복 연산을 줄인다 => 연산한 결과를 배열에 담아서 같은 연산을 또 하지 않는다

 

기억하기 알고리즘, 기억하며 풀기
연산한 내용을 기억해 놓고 다음에도 그 연산이 필요할 때 기억해 놓은 값을 사용해서 문제를 푸는 게 다이나믹 프로그래밍의 전부이다.

DP 삼각형과 같이 나만의 자료구조를 하나 더 만들고 거기에 어떤 정보를 담아야 이전 단계로 돌아가지 않을지 고민해봐야한다.

 

 

DP로 풀면 좋을 것 같은 문제
1. DFS/BFS로 풀 수는 있지만 경우의 수가 너무 많은 문제
2. 경우의 수들에 중복적인 연산이 많은 경우

 

---

 

 

 

2시간만에 풀기 성공~!