[알고스팟/종만북/분할정복/재귀/스위핑] 울타리 잘라내기(Python)

문제

너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비스듬히 잘라낼 수는 없습니다.

판자의 너비는 모두 1이라고 가정합니다.

입력

첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 판자의 수 N (1≤N≤20000)이 주어집니다. 그 다음 줄에는 N개의 정수로 왼쪽부터 각 판자의 높이가 순서대로 주어집니다. 높이는 모두 10,000 이하의 음이 아닌 정수입니다.

출력

각 테스트 케이스당 정수 하나를 한 줄에 출력합니다. 이 정수는 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기를 나타내야 합니다.

예제 입력

3 7 7 1 5 9 6 7 3 7 1 4 4 4 4 1 1 4 1 8 2 2

예제 출력

20 16 8

출처 : https://www.algospot.com/judge/problem/read/FENCE

분할정복 풀이

[접근방식]

1. 가장 단순하게 푸는 방법? ⇒ 울타리 하나씩 돌아가며 기준으로 잡고 전체 울타리 탐색(완전탐색)
2. 완전탐색 가능? ⇒ O(N^2)라 불가능
3. 풀이기법 ⇒ 분할정복
4. 분할정복에 쓰인 아이디어⇒ 가장 큰 사각형은 3가지 경우가 있음 1) 왼쪽에서 가장 큰 것, 2) 오른쪽에서 가장 큰 것, 3) 겹치는 것 중 가장 큰 것
5. 3)번의 경우에서 중앙의 2개를 포함하게 되어있음
6. 1)과 2)의 경우 재귀로 넘겨주고 3)의 기저조건은 울타리가 하나일 때로 설정

[어려웠던 점]

1. 분할정복 자체를 생각해내기가 어려웠음
2. 나는 1), 2), 3)을 각각의 함수로 생각했고 1)과 2)를 재귀로 넘겨준다는 것을 생각하지 못했음
3. 3)의 경우에 중앙의 2개를 무조건 가지게 된다는 조건에 대해 잘 생각하지 못했던 것 같음

[분할정복 풀이코드(책 코드 참조)]

#입력값
n = 7
h = [1, 4, 4, 4, 4, 1, 1]

def dfs(left, right):
    global h
    if left == right: return h[left]
    mid = (left+right)//2
    lo = mid
    hi = mid+1
    ret = max(dfs(left, lo), dfs(hi, right))
    height = min(h[lo], h[hi])
    ret = max(ret, height*2)
    while left < lo or hi < right:
        if hi<right and (h[lo-1]<h[hi+1] or lo == left):
            hi += 1
            height = min(height, h[hi])
        else:
            lo -= 1
            height = min(height, h[lo])
        ret = max(ret, height*(hi-lo+1))
    return ret

print(dfs(0, n-1))

스위핑 풀이

[스위핑이란?]

스위핑 알고리즘이란, 이미 연산이 진행된 이전 공간에 대해서는 연산을 하지않는다는 개념

[접근방식]

1. 사각형을 구하기 위해 필요한 정보는 해당 사각형의 왼쪽 끝과 오른쪽 끝 그리고 높이임
2. 높이가 오른쪽 끝점의 높이라고 했을 때, 왼쪽으로 연속된 판자들 중 이 높이를 포함하는 가장 낮은 지점이 왼쪽 끝점이 될 것
3. 위의 사항을 이용하기 위해 index(폭 구할 때 이용)를 stack에 저장하고 stack에서 빼내면서 폭을 구하고 해당 index로 높이 정보에 접근도 가능
4. index를 꺼내는 시점의 경우, 현재 울타리 높이가 stack의 마지막 울타리 높이보다 낮을 때 현 울타리 보다 낮은 울타리 전까지 하나씩 빼면서 넓이를 업데이트 해주면 됨
5. 단, 스텍에서 뺄 때, 스택이 비어있는지 확인이 필요함
6. 추가적으로 마지막 울타리의 높이가 굉장히 높을 경우가 있으므로 울타리 높이 배열에 0을 추가해주면 이 경우 처리 가능
7. 해당 문제를 푸는 알고리즘 요약 (O(N) 풀이 가능)

[(참고) 스텍 생성 울타리를 저장하는 배열에 0 추가 0부터 n까지(n+1 번) 다음을 순회]

1. 스텍이 비지 않고 현재 스택에 가장 나중에 저장된 위치의 울타리 높이가 현 울타리 높이 이상일때까지 다음을 반복 a. 스텍에 가장 나중에 저장된 위치 가져옴 b. 너비는 스텍이 비었을 땐 현재위치 i를, 비지 않았다면 i-다음으로 나중에 저장된 위치-1 c. 넓이를 구하고 최대값 갱신
2. 현재 idx를 스텍에 넣어줌

[어려웠던 점]

1. 스텍까지는 떠올렸었는데, 울타리의 idx를 스텍에 넣는다는 것을 떠올리지 못해서 풀이로 연결시키기 어려웠던 것 같다.
2. 스텍을 넣고 빼고하는 지점의 조건에 대해 정당성을 입증하기가 어려웠던 것 같다. 정작 그림을 그려가며 생각해보니, 모든 조건에서 정상작동하였다.
3. 울타리의 idx가 0부터 시작한다는 점에서 너비의 조건이 i 혹은 i-다음으로 나중에 저장된 위치-1가 된다는 것을 잘 연결시키지 못했다.

[느낀 점]

1. 분할정복 보다 스위핑이 시간복잡도도 낮은데다, 스위핑은 재귀를 부르지 않기 때문에 이해만 잘 한다면 스위핑이 훨씬 간단하고도 강력한 알고리즘이 될 것이다.
2. 앞으로 스위핑과 스텍을 이용하는 방법에 대해 항상 유념하고 비슷한 문제를 만나면 잘 활용해봐야겠다.

[스위핑 풀이코드]

#입력값
n = 7
h = [1, 4, 4, 4, 4, 1, 1]

#마지막 울타리 처리를 위해서 0높이의 울타리 추가
h.append(0)
#울타리 idx 담을 stack
stack = []
#업데이트할 결과값
ret = 0

for i in range(n+1):
    #현재 울타리가 stack의 마지막 울타리보다 낮으면
    #현 울타리보다 작은 울타리 나오기 전까지 뺴주면서 넓이 업데이트
    while stack and h[stack[-1]] >= h[i]:
        #높이를 stack 마지막걸로 업데이트해가며 진행
        height = h[stack[-1]]
        stack.pop()
        #stack이 비었다면(idx가 0부터 시작)
        if not stack:
            width = i
        #stack이 남아있으면(idx가 0부터 시작)
        else:
            width = i-stack[-1]-1
        #넓이 업데이트
        ret = max(ret, height*width)
    #stack에 넣어주기
    stack.append(i)

print(ret)

참고출처 https://gurumee92.tistory.com/90 https://doctcoder.tistory.com/27