📚Algorithm/Algorithm

격자 안에서 한칸씩 전진하는 문제는 어떻게 풀까요~?~?우리는 DP 시리즈 중 2번째 격자 안에서 한칸씩 전진하는 DP를 이제 풀게되었습니다. 대표적인 알고리즘 문제중 정수 사각형 최대합or 최소합or 최솟값의 최대,   정수 사각형 최장 증가 수열, 사각형 차이의 최소, 등 2차원 배열의 최솟값, 최대값, 최장 증가 부분 수열(LIS라고들 하죠) 문제를 접했을때 푸는 문제입니다.  2차원 배열을 이용하는거라 좀더 흥미가 있는데요 이런 블럭이 존재했을때, 맨위에서 맨밑으로 내려왔을때 얻을수 있는 최대합은 무엇일까요? 에 대해서 문제 풀이를 진행해보도록하겠습니다. (이 때, 이동은 아래 혹은 오른쪽으로만 갈수있습니다) 우리가 생각한 문제접근의 반례문제를 접하고 어? 그냥 큰값만 보면서 내려가면되는거아니야?..

먼저 DP, 즉 Dynamic Programming이 무엇인지 알아볼까요?큰 문제에 대한 답을 얻기위해 동일한 문제이지만 크기가 더 작은 문제들을 해결한 뒤, 그 결과들을 이용해 큰 문제를 비교적 간단하게 해결하는 기법.실생활로 드는 예시는 스케줄링 문제, 금융 투자, 게임 전략 등 실생활에 많이 사용하고 있습니다. 문제로도 예시를 들어볼까요? 예를들어 1부터 N까지의 곱을 구하는 코드를 작성해본다면 N이 5라면, 1*2*3*4*5입니다result=1;for(i ~ N) int tmp = i*result; retulr+=tmp; 로 쉽게 구할수있겠죠 하지만 큰 단위에서 작게 생각해보자면 점화식을 이용할수있을것입니다. N을 구하는 함수를 F(N)으로 가정한다면,F(N) = F(N-1)*N (if N>..