우선 DP에 대해 학습하기 전 DP에 대해 알아보자.

DP란 Dynamic Programming의 약자로 " 큰 문제에 대한 답을 얻기 위해 동일한 문제이지만 크기가 더 작은 문제들을 먼저 해결한 뒤, 그 결과들을 이용해 큰 문제를 비교적 간단하게 해결하는 기법" 라고 코드트리에서 정의했다.

좀 더 간단하게 요약해보면 작은 단위로 쪼개진 문제들을 해결하고 그 결과를 이용하여 큰 문제를 해결하는 기법이라고 생각한다.

그럼 바로 문제를 풀어보도록 하자.

maximum-sum-path-in-square?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

해당 문제의 키포인트는 (1, 1)에서 시작하여 오른쪽 혹은 밑으로만 이동하여 (N, N)에 도달하는 부분을 말한다.

그러면 (1, 1) 좌표에서 N이 3인 (3, 3)좌표로 도달하고자 할 때의 과정을 살펴보도록 하자.

초기값 = (1, 1)

(1, 1) 에서 오른쪽으로 이동하면 (1, 2) 밑으로 이동하면 (2,1)이 된다.

이를 통해 점화식을 알 수 있다. (d[i][j] = max(d[i-1][j], d[i][j-1]) + a[i][j])

그럼 이제 다음 문제로 가보자.

정수 사각형 최댓값의 최소

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

해당 문제는 먼저 지문을 이해하는 것이 관건이라고 생각한다.

거쳐간 위치에 적혀 있는 숫자 중 최대값을 최소로 한다는 것은 (1, 1)에서 (N, N)으로 이동하면서 지나가는 위치 중 최대값을 최소로 즉, d[i-1][j]와 d[i][j-1] 중 최소값을 현재 위치(i, j)와 비교하여 최대값을 저장한다고 이해했다.

점화식으로 표현하면 d[i][j] = min(max(d[i][j-1], d[i-1][j]), num[i][j])이다.

max함수 안의 두 값이 각각 왼쪽과 위에 해당하는 값이고 다음 인자가 현재 위치를 의미한다.

솔직히 DP를 처음 접하는 입장이라면 진입장벽이 매우 높다고 생각한다.

하지만 꾸준함과 열정을 갖고 열심히 한다면 정복할 수 있을거라 생각한다.