Dynamic Programming이란?

Dynamic Programming이란?

---

큰 문제를 작은 문제로 나누어 푸는 문제입니다.
+ 작은 문제가 중복되어 발생하는지 여부 및 작은 문제의 답이 동일

 

Devide&Conquer와 동일한 것이지 않는가?

-> Devide&Conquer도 큰 문제를 작은 문제로 나누어 푸는 부분에서 동일합니다. 하지만 Devide&Conquer는 말 그대로 작은 문제로만 나누어서 풀 뿐 작은 문제가 중복해서 발생한다던지 하지 않습니다.

 

Memoization

작은 문제가 중복으로 발생하다보니 동일한 연산을 중복으로 할 이유가 없습니다. 따라서 해당 문제의 답을 적어두는 것입니다. DP의 대표적인 예가 피보나치,  ROD CUTTING(막대기 자르기) 등이 있습니다.

1,1,2,3,5,8 .... 은 다음 수열 = 이전 수열 + 두 단계전 수열의 합을 구하다보면, F(5)는 F(4),F(3)를 부르게 되고 F(4)는 F(3),F(2) 를 부르게 됩니다. F(3)을 봐도 알 수 있죠?

 

결국 Dynamic programming이란 큰 문제를 작은 문제로 나누어 풀되, 작은 문제가 반복된다 + 작은 동일한 문제에 대한 답이 동일해야 합니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12905

# Dynamic Programming
# 작은 문제 = 정사각형은 전의 값의 대각선 / 좌 / 상 중에서 가장 작은 정사각형
def solution(board):
    answer = 0
    row , column = len(board) , len(board[0])
    maps = [[0]*column for _ in range(row)]
    
    for i in range(row):
        if board[i][0] :
            maps[i][0]=1
            answer = 1
    for j in range(column):
        if board[0][j] :
            maps[0][j]=1
            answer = 1

    for i in range(1,row) :
        for j in range(1,column) :
            if board[i][j] :
                maps[i][j] = min(maps[i][j-1] , maps[i-1][j] , maps[i-1][j-1])+1
                if maps[i][j] > answer :
                    answer = maps[i][j]

    return answer*answer

board = [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]
print(solution(board))