분할 정복 중요 테크닉 - 히스토그램에서 가장 큰 직사각형 찾기

1. 문제

 

1725번: 히스토그램 (acmicpc.net)

1725번: 히스토그램

 

2. 풀이

 

히스토그램이 주어질때, 찾을 수 있는 직사각형중 넓이가 가장 큰 직사각형을 찾는 문제

 

 

 

위와 같은 경우 다음과 같은 직사각형을 찾을 수 있을 것이다.

 

 

 

히스토그램이 높이 배열 A로 주어질 때, 어떤 구간 [i,j]까지 잡았을 경우, 만들 수 있는 직사각형은

 

높이가 가장 낮은 min(A)에 구간의 길이 j-i+1을 곱한 값이다.

 

 

따라서 가능한 모든 경우에 대해 min(A) * (j-i+1)의 최댓값을 찾는 문제다.

 

분할 정복으로 해결할 수 있다.

 

중간 지점 m에 대하여, A[m]을 포함하는 모든 직사각형들의 넓이 중 최댓값을 찾는다면, 

 

나머지 구간은 [start, m-1], [m+1, right]이다.

 

나머지 구간은 재귀적으로 찾으면 될 것이고, A[m]을 포함하는 모든 직사각형들의 넓이 중 최댓값을 찾는 방법만 알면 된다.

 

단순하게 찾는다면 $O(N^{2})$으로 매우 느릴텐데, [m,m]부터 시작해서 한칸씩 확장하는 방식으로 접근

 

하지만 왼쪽이냐? 오른쪽이냐? 어디로 가야할지가 문제

 

구간의 길이는 어디로 가든 매 순간 1씩 증가

 

그러므로, 구간 [i,j]에서 높이 min(A[i], A[i+1], ... , A[j])가 최대한 덜 작아지는 방향으로 확장해나가야함

 

확장은 최대 r-l번 하기 때문에, 선형 시간에 처리 가능해서 $O(NlogN)$에 처리 가능하다.

 

----------------------------------------------------------------------------------------------------------------------------------------------

 

구간 [start,end]가 주어졌을때, mid = start + (end - start)//2로 찾을 수 있다

 

그러면 현재 직사각형의 넓이는, answer = A[mid]

 

사각형의 수는 count = 1

 

최소 높이는 A[mid]

 

이제 i = mid - 1, j = mid + 1로 두고, 왼쪽, 오른쪽을 보면서 높이가 덜 작아지는 방향으로

 

구간을 확장해나갈 것

 

mid = start + (end-start)//2

answer = A[mid]
count = 1
min_h = A[mid]

i = mid-1
j = mid+1

 

왼쪽, 오른쪽을 보면서 왼쪽 사각형의 높이가 높다면? 왼쪽으로 늘려가는게 유리할 것이고

 

오른쪽 사각형의 높이가 높다면? 오른쪽으로 늘려가는게 유리할 것이다.

 

i >= start이고 j <= end 인 경우에...

 

A[i](왼쪽)와 A[j](오른쪽) 값을 비교하면서 A[i]가 더 크다면, 왼쪽으로 구간을 늘리는게 유리하다.

 

왼쪽으로 구간을 늘린다는 것은 i를 1 감소시키는 것이다.

 

그리고 새로운 사각형이 들어왔으니 count를 1 증가시키고,

 

이때, 구간의 최소 높이는 원래 최소 높이 min_h와 새로 들어온 사각형 A[i]중 최솟값으로 갱신

 

반대로 A[j]가 더 크다면, 오른쪽으로 구간을 늘리는게 유리하다.

 

오른쪽으로 구간을 늘린다는 것은 j를 1 증가시키는 것이다.

 

그리고 구간의 최소 높이는 원래 최소 높이 min_h와 새로 들어온 사각형 A[j]중 최솟값으로 갱신한다.

 

매 반복마다, 구간에 들어있는 사각형의 수 count = 구간의 길이가 될 것이고, 여기에 구간의 최소 높이 min_h를 곱한 값이 새로 갱신된 사각형의 넓이이다.

 

갱신된 사각형의 넓이와 지금까지 최댓값 넓이 answer중 최대인 값으로 갱신해주자.

 

while i >= start and j <= end:

    if A[i] > A[j]:

        count += 1
        min_h = min(min_h,A[i])
        i -= 1

    else:

        count += 1
        min_h = min(min_h,A[j])
        j += 1

    answer = max(answer,count*min_h)

 

 

여기서 끝이 아니다.

 

위 반복문을 탈출한다는 것은..?

 

i나 j중 하나가 끝에 도달했다는 의미다. 즉 i가 start가 되었거나 j가 end가 된 것이다.

 

하지만 모든 경우를 다 체크해봐야하므로, j가 end에 갔다면..? i가 start에 도달할때까지, 왼쪽으로 구간을 늘려가며,

 

넓이를 계산하고, 최대 넓이를 갱신한다.

 

while start <= i:

    count += 1
    min_h = min(min_h,A[i])
    i -= 1

    answer = max(answer,count*min_h)

 

만약 i가 start에 도달했다면?

 

그러면 j가 end에 도달할 때까지 오른쪽으로 구간을 늘려가면서 넓이를 계산하고 최대 넓이를 갱신한다

 

while j <= end:

    count += 1
    min_h = min(min_h,A[j])
    j += 1

    answer = max(answer,count*min_h)

 

첫번째 반복문이 끝나면, i나 j중 하나만 start나 end에 도달했다.

 

두 반복문을 모두 적으면 while문이 조건문을 검사해서, 이미 도달한건 반복문을 수행하지 않고

 

아직 도달하지 않은 반복문만 실행된다.

 

이제, mid 기준으로 [start,end]까지 히스토그램에서 직사각형의 최대 넓이를 계산했다.

 

그러면 나머지 구간 [start,mid-1], [mid+1,end]로 분할해서, 이는 재귀적으로 처리하도록 한다

 

answer = max(answer, histogram(A,start,mid-1))
answer = max(answer,histogram(A,mid+1,end))

 

구간 [start,end]에서 start < end를 가정하기 때문에,

 

분할정복으로 쪼개면서 start > end이면, 0을 return하고 start == end이면 A[start]를 return하자.

 

실험해봤는데 start > end인 경우는 있는데 start == end인 경우는 없는듯..?

 

from sys import stdin

def histogram(A,start,end):
    
    if start > end:
        
        return 0
    
    if start == end:
        
        return A[start]
    
    #정복 과정
    #중간 지점 A[mid]을 기준으로
    #왼쪽 오른쪽에서 mid의 높이 일부를 포함하는 가장 큰 직사각형을 찾는다. 
    mid = start + (end-start)//2

    answer = A[mid] #현재 최대 넓이 = 중간 지점 직사각형 넓이
    count = 1 #현재 구간이 가지는 사각형 수
    min_h = A[mid] #현재 구간의 사각형 중 가장 낮은 높이

    i = mid-1 #왼쪽
    j = mid+1 #오른쪽

    #왼쪽 오른쪽을 보면서 직사각형의 높이가 덜 작아지는 방향으로 구간을 늘린다
    while i >= start and j <= end:
        
        if A[i] > A[j]: #왼쪽 사각형이 더 높은 경우, 왼쪽으로 늘리는게 유리하다.
            
            count += 1
            
            #구간의 최소 높이를 갱신 -현재 최소 높이와 새로 들어온 사각형 높이중 작은 값으로
            min_h = min(min_h,A[i])
            i -= 1 #왼쪽으로 늘리는건 i를 1 감소시키는 것
        
        else: #오른쪽 사각형이 더 높은 경우, 오른쪽으로 늘리는게 유리하다.
            
            count += 1
            min_h = min(min_h,A[j]) #구간의 최소 높이 갱신
            j += 1 #오른쪽으로 늘리는건 j를 1 증가시키는 것
        
        #매 반복마다, 구간의 최대 직사각형 넓이는 count(구간의 사각형 수 = 구간의 길이)*min_h(구간의 최소 높이)
        #현재 최대 넓이인 answer와 새로 갱신된 넓이 count*min_h중 최댓값으로 갱신
        answer = max(answer,count*min_h)
    
    #위 반복문을 탈출하면 왼쪽,오른쪽 구간중 한쪽이 끝에 도달한 상태

    #끝에 도달하지 못한 구간 중 하나를 끝까지 이동 시켜봐서 
    #넓이가 최대가 될 수 있는지, 조사하면서 최대 직사각형을 찾는다.
    
    #while 조건문에 의해 둘 중 하나는 거짓이고 실행이 안된다.
    while start <= i:
        
        count += 1
        min_h = min(min_h,A[i])
        i -= 1

        answer = max(answer,count*min_h)

    while j <= end:
        
        count += 1
        min_h = min(min_h,A[j])
        j += 1

        answer = max(answer,count*min_h)
    
    #mid를 기준으로 두 구간으로 분할하는 과정
    answer = max(answer, histogram(A,start,mid-1))
    answer = max(answer,histogram(A,mid+1,end))

    return answer

n = int(stdin.readline())

A = []

for _ in range(n):
    
    x = int(stdin.readline())

    A.append(x)


print(histogram(A,0,n-1))

 

 

참고로 min, max를 풀어쓰면 2배정도 빨라지긴 한다

 

이 테크닉을 이용해서 풀 수 있는 문제가 꽤 많기 때문에 반드시 익혀야한다.

 

 

3. 문제2

 

2104번: 부분배열 고르기 (acmicpc.net)

2104번: 부분배열 고르기

 

4. 풀이

 

배열이 주어질때, 구간의 모든 수의 합과 구간의 최솟값의 곱의 최댓값을 구하는 문제

 

위의 히스토그램 문제에서, 구간의 길이 대신에 '구간의 모든 수의 합'으로 바뀌었다.

 

그러면 count를 1씩 증가시키는게 아니라, count에 새로 들어오는 수 A[i]를 더해나가면 될 것이다

 

from sys import stdin

def divide_and_conquer(A,start,end):
    
    if start > end:
        
        return 0
    
    if start == end:
        
        return A[start]*A[start]

    mid = start + (end - start)//2

    s = A[mid] #현재 구간의 수의 합
    m = A[mid] #현재 구간에 들어간 수들의 최솟값
    score = s*m #현재 최대 점수

    i = mid - 1
    j = mid + 1
    
    #왼쪽과 오른쪽을 보면서 구간에 들어간 수들의 최솟값이 최대한 덜 작아지도록 구간을 확장
    while i >= start and j <= end:

        if A[i] > A[j]: #왼쪽의 수가 더 큰 경우,

            s += A[i] #새로 들어온 수를 구간에 들어간 수들의 합에 누적해나감
            
            #구간의 수들의 최솟값은, 새로 들어온 수와 현재 구간 수들의 최솟값중 더 작은 값으로 갱신
            m = min(A[i],m)
            i -= 1 #왼쪽으로 늘린건 i를 1 감소시킨 것

        else: #오른쪽의 수가 더 큰 경우
            
            s += A[j] #새로 들어온 수를 구간에 들어간 수들의 합에 누적해나감
            m = min(A[j],m)
            j += 1 #오른쪽으로 늘린건 j를 1 증가시킨 것
        
        score = max(score,s*m) #매 반복마다 현재 최대 score와 갱신된 score중 더 큰 값을 최댓값으로
    
    #위 반복문이 끝나면, i가 start에 도달했거나 j가 end에 도달했거나
    #도달하지 못한 방향을 끝까지 탐색하며 최댓값이 발견되면 갱신
    while i >= start:

        s += A[i]
        m = min(A[i],m)
        i -= 1

        score = max(score,s*m)

    while j <= end:
        
        s += A[j]
        m = min(A[j],m)
        j += 1

        score = max(score,s*m)
    
    #mid를 기준으로 (start,mid-1)과 (mid+1,end)로 분할해서 분할정복
    score = max(score,divide_and_conquer(A,start,mid-1))
    score = max(score,divide_and_conquer(A,mid+1,end))

    return score   

n = int(stdin.readline())

A = list(map(int,stdin.readline().split()))

print(divide_and_conquer(A,0,n-1))