[파이썬][알고리즘] DP로 해결하기

1. 문제

자신이 속한 열을 제외한 값중 가장 큰 값을 중복으로 더하여 최종 행의 가장 큰 값을 호출하기

2. 해결방법 시간복잡도

1. DP O(N^2)

3. 문제 해결 및 코드

---

• 주석을 참고하면서 이해를 돕습니다.

4. 알고리즘 간략 설명

1. DP

• 동적 계획법이라고 불리는 문제로 1회용 알고리즘이다. 최소한의 계산방식으로 문제를 해결하기 때문에 시간을 최소화할 수 있지만 문제가 생길 시 브루트포스와 같이 코드 전체를 바꿔야할 수도 있다.
• 반복적으로 계산해야하는 문제이며 답이 같다라는 조건하여 DP로 해결할 수 있다.
• 위의 문제의 경우 반복적으로 문제를 해결해야하기에 DP를 사용했고 따로 변수를 만들지않고 기존의 값에 지속적으로 값을 추가하며 바꾸는 방식으로 메모리 소비를 최소화하였다. (이러한 방식을 메모이제이션 이라고 한다.)