7.4 문제 : 울타리 잘라내기(Python)

문제 출처 : algospot.com :: FENCE

algospot.com :: FENCE

---

1. 문제 해결을 위한 사고 과정

(1) 무식하게 풀기

• 각 판자 높이의 배열 h[]가 주어졌을 때 l번 판자부터 r번 판자까지 잘라내서 사각형을 만듦
• 가장 간단한 방법은 가능한 모든 l과 r로 만들 수 있는 사각형의 값을 계산한다.
• 2중 for문을 통해 계산할 수 있으므로 시간 복잡도는 O(n^2)
• 그러나 문제에서 제한된 입력의 최대 입력은 20,000으로 20,000^2은 1억을 넘어가므로 제한 시간(1초) 내에 해결하기 어렵다.

 

(2) 분할 정복으로 풀기

1) 설계

• 문제를 어떻게 분할할 것인가? n개의 판자를 절반으로 나눠 일단 두 개의 부분 문제를 만든다!
• 그러나 최대 직사각형은 다음 중 세 가지 중 하나에 속할 것이다.
• 1. 가장 큰 직사각형은 왼쪽 부분 문제에 존재
• 2. 가장 큰 직사각형은 오른쪽 부분 문제에 존재
• 3. 가장 큰 직사각형은 왼쪽과 오른쪽 부분 문제에 걸쳐서 존재
• 따라서 총 세 가지의 부분 문제를 해결해야 한다.

 

2) 문제 해결은 어떻게

• 1과 2의 경우 재귀 호출을 통해 구현
• 최대 크기의 직사각형이 걸쳐서 존재하는 경우(3의 경우) 가운데 경계에 있는 판자는 반드시 포함된다!
• 가운데 판자를 기준으로 좌우로 한 칸씩 판자를 확장하며 문제를 해결할 수 있다.(좌우의 판자 중 더 높이가 높은 판자쪽으로 확장)
• 검사하는 판자가 1개 밖에 남지 않은 경우가 기저 사례

---

2. 해설 풀이 방법

(1) 코드

# left, right 사이에서 가장 범위가 넓은 사각형을 찾는다.
def solve(left, right):
    # 기저 사례 1: 판자가 하나밖에 없는 경우
    if left == right:
        return data[left]

    # left ~ mid, mid+1 ~ right의 두 구간으로 문제를 분할
    # 부분 분제 1 : 가장 범위가 넓은 사각형이 좌측에 있는 경우
    # 부분 문제 2 : 가장 범위가 넓은 사각형이 우측에 있는 경우
    mid = (left + right) // 2

    # 분할한 문제들을 다시 재귀적으로 호출하고 가장 큰 값을 취함
    result = max(solve(left, mid), solve(mid+1, right))

    # 부분 문제 3 : 가장 범위가 넓은 사각형이 중앙에 걸쳐 있는 경우
    # 먼저, 중앙의 두 판자만 고려하는 너비가 2인 사각형을 확인
    low = mid
    high = mid+1
    # height = min(low, high) : 실수한 부분
    height = min(data[low], data[high])

    # 2 * height = 중앙의 두 판자를 이용한 사각형의 넓이
    # 판자가 이 단계에서 2개 밖에 없으므로 2(가로) * height(세로) 입력
    result = max(result, 2 * height)

    # 중앙의 사각형을 좌, 우로 점차 확대해가면서 모든 판자들에 대해서 확인
    while (left < low or high < right):
        # 항상 높이가 높은쪽으로 확장

        # 1. 오른쪽으로 확장하는 경우
        # 사각형의 오른쪽 부분이 전체 판자 내부에 위치하고,
        # 사각형의 왼쪽 부분이 제일 왼쪽에 위치한 판자이거나 오른쪽 판자의 높이가 왼쪽 판자의 높이보다 큰 경우 오른쪽으로 확장
        if high < right and (low == left or data[low - 1] < data[high + 1]):
            high += 1
            height = min(height, data[high]) # 사각형의 최대 높이를 새로 계산

        # 2. 왼쪽으로 확장하는 경우
        else:
            low -= 1
            height = min(height, data[low]) # 사각형의 최대 높이를 새로 계산

        result = max(result, height * (high - low + 1)) # 확장 후 사각형의 넓이를 새로 계산

    return result


for tc in range(int(input())):

    n = int(input()) # 울타리를 구성하는 판자의 수
    data = list(map(int, input().split())) # 판자의 높이 정보를 저장하는 리스트

    print(solve(0, n-1))

(2) 해설

• 설계 단계에서 처럼 문제를 3부분으로 분할하여 각 부분 문제에서 계산된 사각형의 크기 중 가장 큰 사각형을 반환한다.
• 문제를 분할할 때 남은 판자의 수가 1인 경우 기저 사례로 해당 판자의 높이(판자가 1개인 경우, 사각형의 넓이 = 판자의 높이)를 반환한다.
• 이진 탐색의 경우 처럼 인수로 전달된 인덱스의 중간 판자를 기준으로 먼저 좌, 우에 해당하는 2개의 부분 문제를 재귀 호출한다.
• 그리고 이 결과와 사각형이 양쪽에 걸쳐있는 경우와 비교하여 가장 큰 사각형의 크기를 반환한다.

 

• 판자들에서 잘라내어진 사각형을 만들 때, 사각형의 높이는 판자들 중 가장 작은 크기의 판자의 높이임을 유의 해야한다.(확장 시 매번 새롭게 사각형의 높이를 새롭게 갱신해야 한다.)
• 양쪽에 걸친 사각형에 대해 부분 문제를 해결할 때, 확장 방향에 조건을 자세하게 설정할 필요가 있음을 유의 해야한다.

---

3. 시간 복잡도 분석

• 시간 복잡도는 책의 설명 + 뇌피셜로 분석해봤다.
• 먼저 분할 과정에서 문제를 항상 n/2로 나눈뒤 각각 해결하기 때문에 O(logN)의 시간 복잡도를 갖는다고 생각할 수 있다.(이진 탐색을 생각하면...)
• 그리고 병합 과정에서 너비가 2인 사각형부터 n인 사각형까지 하나하나 검사하므로 O(N)의 시간 복잡도가 된다.
• 결과적으로 문제를 항상 절반으로 나누어서 재귀 호출하고 O(N) 시간의 후처리를 하는 대표적인 알고리즘인 병합 정렬과 같다.
• 따라서 병합 정렬과 같은 시간 복잡도 O(N*logN)을 갖는다.
• N = 20,000에서 N*logN은 대략 290,000이기 때문에 제한 시간 내에 문제 해결이 가능하다.

---

4. 후기

  이전에 쿼드 트리 문제보다 이해하기 쉬웠던 문제였다. 문제를 보고 무식하게 푸는 방법은 생각할 수 있었고 중앙의 판자를 기준으로 좌우로 분할하여 부분 문제를 풀어야 겠다는 생각까지는 도달할 수 있었다. 문제는 양쪽에 사각형이 걸쳐있는 경우였는데 이를 해결할 방법을 생각하지 못 했다. 그래도 다행인건 풀이 해설을 보고 단번에 이해할 수 있었고 코드 역시 해결 방법을 곧이 곧대로 코드로 옮긴 수준이라 작성하면서 동시에 이해하기에 어려움은 없었다.

  조금이나마 공부를 하면서 나아진 점을 꼽으라면 이제 어느정도 재귀 호출에 대한 두려움이 사라졌다는 점이다. 처음에는 재귀 호출이 어떻게 호출되고 반환되는지 또 어떤 값을 반환해야 되는지 아무것도 모르는 백지상태고 주어진 재귀 호출에 대한 이해도 어렵고 시간도 많이 소모되었다면 지금은 아직도 스스로 백지에다가 그 함수를 만들기에 부족하지만 주어진 재귀 호출에 대한 과정은 비교적 쉽게 이해할 수 있는 상태가 되었다. 앞으로는 스스로 백지에 재귀 함수를 구현할 수 있는 단계가 되도록 좀 더 문제들을 살펴봐야겠다.

---

github : Algorithmic_Problem_Soving_Strategies/q2_0.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies