[python code review] 6주차 (파일 합치기, 정수 삼각형, 가장 큰 정사각형)

참고) cs 면접 대비와 알고리즘 자료구조를 잘 정리해둔 블로그가 있어 소개합니다 ㅎㅎ

https://gyoogle.dev/blog/algorithm/Dynamic%20Programming.html

동적 계획법(Dynamic Programming) | 👨🏻‍💻 Tech Interview

 

파일합치기 문제 풀이 방법

https://www.youtube.com/watch?v=4OdIDIYLHlY 

 

https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

for _ in range(int(input())):
    n = int(input())
    arr = [int(x) for x in input().split()]
    rst = [[0 for _ in range(n)] for _ in range(n)]
    for j in range(1, n):
        for i in range(j-1, -1, -1):
            small = 1e9
            for k in range(j-i):
                small = min(small, rst[i][i+k] + rst[i+k+1][j])
            rst[i][j] = small + sum(arr[i:j+1])
    print(rst[0][n-1])

연쇄 행렬 최소 곱셈 알고리즘을 이용하면 O(N^3)

크누스 알고리즘을 이용하면 O(N^2)만에 풀 수 있다.. 어렵다ㅏㅏ

 

 

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

def solution(triangle):
    answer = 0
    dp = [0]*(len(triangle[-1])+1)
    dp[1] =  triangle[0][0]
    for i in range(1, len(triangle)): # 삼각형 1부터 마지막 레벨까지 
        for j in range(len(triangle[i])): # i레벨의 각 원소에 대해 
            dp[j] = max(triangle[i][j]+dp[j], triangle[i][j]+dp[j+1])
        dp.insert(0, 0)
        
    return max(dp)

1은 3과 8중에 최대값인 8을 고를 수 있다.

이러한 아이디어를 dp로 가져와보면 

 

dp[i] = i번째에 저장되는 누적 합의 최댓값이라할 때dp[i] = max(dp[i], arr[i]+dp[i])

dp[i] = max(dp[i], arr[i]+dp[i+1])

 

각 레벨별로 누적합을 이러한 방식으로 더해줘야 하므로 레벨별로 누적할 때마다 dp 0번째에 0을 넣어주었다.

코드개선)

dp 사이즈를

dp = [0]*(len(triangle[-1])+1) 에서

dp = [0]*3 으로 변경하여 메모리 절약 가능  

 

 

https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

n, m = map(int, input().split())
board = [list(map(int, list(input()))) for _ in range(n)]
answer = max([max(b) for b in board]) # n이나 m이 1인 경우를 대비해 최댓값 저장 

for i in range(1, n):
    for j in range(1, m):
        if board[i][j] != 0:
            board[i][j] = min(board[i][j-1], board[i-1][j], board[i-1][j-1]) + 1
            answer = max(answer, board[i][j])

print(answer**2)

배열로 접근하는 dp 문제는 잘 생각이 안난다. 풀이법을 보니 전혀 생각치 못했던 방식이었다. 

dp[i][j] = (i, j)에서 가질 수 있는 직사각형 최대 길이

 

case1)

0 1

1 0

최대길이 : 1

 

case2)

1 1 1

1 1 1

1 1 1

최대길이 : 3

1, 1에서 (0,1) (1,0) (0,0) 좌표에서 모두 1이므로 2를 저장함

 

1 1 1

1 2 1

1 1 1

1, 2에서 (0,2) (1,1) (0,1) 좌표에서 최솟값이 1이므로 2를 저장

 

1 1 1

1 2 2

1 1 1

3,1에서 3,2 또한 이러한 로직을 따르면

 

1 1 1

1 2 2

1 2 3

이 된다.

이 로직의 점화식을 만들어보면 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 

dp[i][j] = (i, j)에서 가질 수 있는 직사각형 최대 길이이므로

마지막 (n-1, m-1) 좌표에서 dp[i][j]는 최대 정사각형 길이이므로 이를 answer에 저장