7. DP - 행렬 경로 문제

# 소개

안녕하세요 공상 개발입니다.

오늘은 전형적인 DP 문제인 행렬 경로 문제에 대해 알아보겠습니다.

앞서 다루었던 '피보나치수열' 보다 관계식을 유추하기 다소 어렵긴 하지만 같이 풀어봅시다.

 

 

# 행렬 경로 문제

n * n 행렬의 좌측 상단에서 시작하여 우측 하단까지 오른쪽 혹은 아래쪽으로만 이동하여 도달하는 방법들 중 이동 경로상의 점수의 합을 최대로 하는 경로를 찾는 문제.

 

최장 경로 문제 : 최장 경로상의 부분 경로가 반드시 두 점상의 최장 경로는 아니다.

단순히 부분 경로에서 제일 큰 값을 따라가는 것이 아닌 경로상에 있는 모든 값들을 더했을 때 최대가 되는 최적의 경로를 찾아야 됩니다.

최단 경로 문제 : 최단 경로상의 모든 부분 경로들 역시 해당 정점들에 대하여 최적.

 

 

1. m [][] 배열에 기본 cost 값들을 할당한다.

2. cache [][] 배열에 최적의 경로로 왔을 때 최장 값을 할당한다.

 

 

# 로직

재귀 관계식을 처음부터 짜기는 어려우니까 말로 한번 풀어서 정리해봅시다.

1.  좌상단에서 출발 2.  1행의 1,2,3,4열은 전부 왼쪽에서 온다 3.  1열의 1,2,3,4행은 전부 위에서 온다. 4.  오른쪽으로 이동, 아래로 이동 조건을 신경 써야 되는 부분은 2행 4열 ~3행 4열

 

이제 수식화를 해보죠.

cache(0,0) = m(0,0)    // 좌상단  cache(0, j) = cache(0, j-1) + m(0, j), j>0   // 1행 전부 cache(i,0) = cache(i-1, 0) + m(i,0), i>0  // 1열 전부 cache(i, j) = Max(cache(i-1, j), cache(i, j-1)) + m(i, j), i>0, j>0  // 2가지 조건 , 위 혹은 왼쪽 중 최대인 곳 + 자신의 값

 

바로 DP로 구현하려면 머리 아프니 재귀로 구현해봅시다.

행렬 경로 재귀 알고리즘

 

이제 효율성을 높이기 위해 DP로 구현하면 아래와 같은 소스코드가 나옵니다.

좌상단의 값을 미리 넣어줘서 인터넷에 돌아다니는 코드보다 좀 더 가독성이 좋게 구현해봤습니다.

# DP 소스 코드

 

이해가 어려우신 분 들은 직접 3 * 3  행렬로 직접 대입해보시길 권장합니다.

다음 시간에는 최장 공통부분 순서 문제(LCS : Longest Common Subsequence) 문제로 찾아뵙겠습니다. 

감사합니다.

---

 

 

작성된 내용 중 잘못된 정보나 접근이 있을 시, www.instagram.com/hong_.98/을 통해 말씀해 주시기 바랍니다.

좋은 하루 보내세요.