[코드트리 조별과제] 격자 안에서 한 칸씩 전진하는 DP (Python) - 7월 3주차

👀  다이나믹 프로그래밍(DP)

 

쓰는 김에 드디어 DP를 제대로 공부해봤다.

 

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

 

기본 문제인 격자 안에서 한 칸씩 전진하는 DP 문제의 해설을 읽으면서 기본 개념을 이해하고, 같은 유형의 문제들을 풀면서 학습하는 방식인 것 같다. 

 

문제를 보다가 이거 점화식 나오겠는데? 싶으면 점화식을 세워보면 된다. 대략의 풀이 순서는 이렇다.

1) 값 저장을 위한 빈 DP 테이블 만들기 (주로 편의를 위해 0으로 채워둠)

2) DP 테이블에 초기조건부터 저장 (initialize 등의 이름으로 별도의 함수를 만들기도 함)

3) 반복문 돌면서 점화식으로 DP 테이블 채우기

 

 

 

💡 초기조건이란?

초기에 확실하게 채워줄 수 있는 값이다. 

내 경우, 길이 딱 한 가지밖에 없는 값들을 미리 저장해두는 절차라고 이해했다. 

현재 좌표가 i, j일 경우, 점화식에서는 i-1나 j-1 등을 사용하며 이전에 계산된 값을 갖다 써야 한다.

이것을 위한 초기값을 만들어놓는 것. (이라고 나는 이해했다.)

 

 

 

 

 

연습문제 1

정수 사각형 최대 합 https://www.codetree.ai/missions/2/problems/minimum-sum-path-in-square/description

N×N 행렬이 주어졌을 때, (1,N)에서 시작하여 왼쪽 혹은 밑으로만 이동하여 (N,1)로 간다고 했을 때 거쳐간 위치에 적혀있는 숫자의 합을 최소로 하는 프로그램을 작성해보세요.

제출한 코드

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(n)] for _ in range(n)]
# 점화식
# dp[i][j] = max(dp[i-1][j]+board[i][j], dp[i][j-1]+board[i][j])

# 1. 초기조건 넣기
dp[0][0] = board[0][0]
for i in range(1, n):
    dp[i][0] = dp[i-1][0] + board[i][0]
for j in range(1, n):
    dp[0][j] = dp[0][j-1] + board[0][j]

for i in range(1, n):
    for j in range(1, n):
        dp[i][j] = max(dp[i-1][j] + board[i][j], dp[i][j-1]+board[i][j])
print(dp[-1][-1])

 

 

 

 

 

 

 

연습문제 2

 

정수 사각형 최소 합 https://www.codetree.ai/missions/2/problems/minimum-sum-path-in-square/description

N×N 행렬이 주어졌을 때, (1,N)에서 시작하여 왼쪽 혹은 밑으로만 이동하여 (N,1)로 간다고 했을 때 거쳐간 위치에 적혀있는 숫자의 합을 최소로 하는 프로그램을 작성해보세요.

 

 

제출한 코드

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]

dp = [[0 for _ in range(n)] for _ in range(n)]

# 우측 상단 -> 좌측 하 이동
# 초기조건
# 1. 맨 윗줄은 무조건 바로 오른쪽칸에서 옴
# 2. 맨 오른쪽 줄은 무조건 바로 윗칸에서 옴
def initialize():
    global dp
    dp[0][n-1] = board[0][n-1]
    for i in range(n-2, -1, -1):
        dp[0][i] = dp[0][i+1] + board[0][i]
    for j in range(1, n):
        dp[j][-1] = dp[j-1][-1] + board[j][-1]

initialize()

# 점화식: dp[i][j] = min(dp[i-1][j]+board[i][j], dp[i][j+1]+board[i][j])

for i in range(1, n):
    for j in range(n-2, -1, -1):
        dp[i][j] = min(dp[i-1][j]+board[i][j], dp[i][j+1]+board[i][j])

print(dp[-1][0])

 

 

 

 

 

연습문제 3

정수 사각형 최솟값의 최대 https://www.codetree.ai/missions/2/problems/maximin-path-in-square/description

N×N 행렬이 주어졌을 때, (1,1)에서 시작하여 오른쪽 혹은 밑으로만 이동하여 (N,N)으로 간다고 했을 때 거쳐간 위치에 적혀있는 숫자들 중 최솟값을 최대로 하는 프로그램을 작성해보세요.

 

 

헛손질을 좀 했다.

제출한 코드

# 현재위치값, 왼쪽값, 위쪽값 3개 중 어떤 걸 고르냐
# 1. 현, 왼 비교 -> if 현이 크거나 같다? 왼을 후보로 남김/ 현이 작다? -> 현을 후보로 남김
# 2. 현, 위 비교 -> if 현이 크거나 같다? 위를 후보로 남김/ 현이 작다? -> 현을 후보로 남김
# 3. 후보가 1개든 2개든 제일 큰 거 고르면 됨 (=최선의 경로 선택 가능. if 현이 셋 중 최소면 이거 선택됨)
# 4. 현재값이 셋 중 최소면 -> 바로 이거 고르고
# 5. 최소가 아니면 -> 두 번째로 큰 값 고르면 됨

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(n)] for _ in range(n)]
dp[0][0] = board[0][0]

def initialize():
    for i in range(1, n):
        dp[0][i] = min(board[0][i], dp[0][i-1])
    for j in range(1, n):
        dp[j][0] = min(board[j][0], dp[j-1][0])
    
initialize()

for i in range(1, n):
    for j in range(1, n):
        if board[i][j] == min(board[i][j], dp[i-1][j], dp[i][j-1]):
            dp[i][j] = board[i][j]
        else:
            dp[i][j] = sorted([board[i][j], dp[i-1][j], dp[i][j-1]], reverse=True)[1]

print(dp[-1][-1])

일단 위처럼 경우를 나눠 식을 세워서 통과시킨 다음 해설을 확인했다. 

제대로 된 점화식은 다음과 같다.

for i in range(1, n):
    for j in range(1, n):
        dp[i][j] = min(max(dp[i-1][j], dp[i][j-1]), board[i][j])