15.3 최대 용량 문제¶

문제

배열 \(ht\)의 각 원소는 수직 칸막이의 높이를 나타낸다. 배열에서 임의의 두 칸막이와 그 사이의 공간으로 용기를 만들 수 있다.

용량은 높이와 너비의 곱(넓이)이다. 높이는 더 낮은 칸막이로 결정되고, 너비는 두 칸막이의 배열 인덱스 차이다.

용량이 최대가 되도록 두 칸막이를 골라 최대 용량을 반환하라. 예시는 아래 그림(15-7)과 같다.

최대 용량 문제 예시 데이터

그림 15-7 최대 용량 문제 예시 데이터

임의의 두 칸막이로 용기를 만들므로 이 문제의 상태는 두 칸막이의 인덱스 \([i, j]\)다.

문제에 따르면 용량은 높이와 너비의 곱이고, 높이는 낮은 칸막이로 결정되며 너비는 두 인덱스의 차다. 용량을 \(cap[i, j]\)라고 하면 다음 공식을 얻는다.

\[ cap[i, j] = \min(ht[i], ht[j]) \times (j - i) \]

배열 길이가 \(n\)이면 두 칸막이의 조합 수(전체 상태 수)는 \(C_n^2 = \frac{n(n - 1)}{2}\)이다. 가장 직접적으로는 모든 상태를 열거하여 최대 용량을 구할 수 있으며, 시간 복잡도는 \(O(n^2)\)이다.

1. 탐욕 전략 결정¶

더 효율적인 풀이도 있다. 아래 그림(15-8)처럼 인덱스 \(i < j\)이고 높이 \(ht[i] < ht[j]\)인 상태 \([i, j]\)를 고르자. 즉, \(i\)는 낮은 칸막이, \(j\)는 높은 칸막이다.

초기 상태

그림 15-8 초기 상태

아래 그림(15-9)과 같이 높은 칸막이 \(j\)를 낮은 칸막이 \(i\) 쪽으로 옮기면 용량은 반드시 작아진다.

\(j\)를 옮기면 너비 \(j-i\)는 확실히 줄어든다. 높이는 낮은 칸막이로 결정되므로 그대로이거나(\(i\)가 계속 더 낮음), 더 낮아질 수만 있다(이동한 \(j\)가 더 낮아짐).

높은 칸막이를 안쪽으로 옮긴 상태

그림 15-9 높은 칸막이를 안쪽으로 옮긴 상태

반대로 생각하면 낮은 칸막이 \(i\)를 안쪽으로 옮겨야만 용량이 커질 가능성이 있다. 너비는 반드시 줄지만 높이는 커질 수도 있기 때문이다(이동한 \(i\)가 더 높을 수 있다). 아래 그림(15-10)에서는 낮은 칸막이를 옮긴 뒤 넓이가 커진다.

낮은 칸막이를 안쪽으로 옮긴 상태

그림 15-10 낮은 칸막이를 안쪽으로 옮긴 상태

따라서 두 포인터를 용기의 양 끝에 놓고, 매번 낮은 칸막이 쪽 포인터를 안쪽으로 옮겨 두 포인터가 만날 때까지 진행하는 탐욕 전략을 도출할 수 있다.

아래 그림(15-11)은 탐욕 전략의 실행 과정이다.

처음에는 포인터 \(i\)와 \(j\)를 배열의 양 끝에 둔다.
현재 상태의 용량 \(cap[i, j]\)를 계산하고 최대 용량을 갱신한다.
칸막이 \(i\)와 \(j\)의 높이를 비교하여 낮은 쪽을 안쪽으로 한 칸 옮긴다.
\(i\)와 \(j\)가 만날 때까지 2. 단계와 3. 단계를 반복한다.

그림 15-11 최대 용량 문제의 탐욕 과정

2. 코드 구현¶

반복문은 최대 \(n\) 회 실행되므로 시간 복잡도는 \(O(n)\)이다.

변수 \(i\), \(j\), \(res\)는 상수 크기의 추가 공간을 사용하므로 공간 복잡도는 \(O(1)\)이다.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

max_capacity.py

def max_capacity(ht: list[int]) -> int:
    """최대 용량: 탐욕"""
    # i와 j가 각각 배열의 양 끝을 가리키도록 초기화한다
    i, j = 0, len(ht) - 1
    # 최대 용량의 초깃값은 0이다
    res = 0
    # 두 칸막이가 만날 때까지 탐욕적 선택을 반복한다
    while i < j:
        # 최대 용량을 갱신한다
        cap = min(ht[i], ht[j]) * (j - i)
        res = max(res, cap)
        # 낮은 칸막이를 안쪽으로 이동한다
        if ht[i] < ht[j]:
            i += 1
        else:
            j -= 1
    return res

max_capacity.cpp

/* 최대 용량: 탐욕 */
int maxCapacity(vector<int> &ht) {
    // i와 j가 각각 배열의 양 끝을 가리키도록 초기화한다
    int i = 0, j = ht.size() - 1;
    // 최대 용량의 초깃값은 0이다
    int res = 0;
    // 두 칸막이가 만날 때까지 탐욕적 선택을 반복한다
    while (i < j) {
        // 최대 용량을 갱신한다
        int cap = min(ht[i], ht[j]) * (j - i);
        res = max(res, cap);
        // 낮은 칸막이를 안쪽으로 이동한다
        if (ht[i] < ht[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}

max_capacity.java

/* 최대 용량: 탐욕 */
int maxCapacity(int[] ht) {
    // i와 j가 각각 배열의 양 끝을 가리키도록 초기화한다
    int i = 0, j = ht.length - 1;
    // 최대 용량의 초깃값은 0이다
    int res = 0;
    // 두 칸막이가 만날 때까지 탐욕적 선택을 반복한다
    while (i < j) {
        // 최대 용량을 갱신한다
        int cap = Math.min(ht[i], ht[j]) * (j - i);
        res = Math.max(res, cap);
        // 낮은 칸막이를 안쪽으로 이동한다
        if (ht[i] < ht[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}

max_capacity.cs

/* 최대 용량: 탐욕 */
int MaxCapacity(int[] ht) {
    // i와 j가 각각 배열의 양 끝을 가리키도록 초기화한다
    int i = 0, j = ht.Length - 1;
    // 최대 용량의 초깃값은 0이다
    int res = 0;
    // 두 칸막이가 만날 때까지 탐욕적 선택을 반복한다
    while (i < j) {
        // 최대 용량을 갱신한다
        int cap = Math.Min(ht[i], ht[j]) * (j - i);
        res = Math.Max(res, cap);
        // 낮은 칸막이를 안쪽으로 이동한다
        if (ht[i] < ht[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}

max_capacity.go

/* 최대 용량: 탐욕 */
func maxCapacity(ht []int) int {
    // i와 j가 각각 배열의 양 끝을 가리키도록 초기화한다
    i, j := 0, len(ht)-1
    // 최대 용량의 초깃값은 0이다
    res := 0
    // 두 칸막이가 만날 때까지 탐욕적 선택을 반복한다
    for i < j {
        // 최대 용량을 갱신한다
        capacity := int(math.Min(float64(ht[i]), float64(ht[j]))) * (j - i)
        res = int(math.Max(float64(res), float64(capacity)))
        // 낮은 칸막이를 안쪽으로 이동한다
        if ht[i] < ht[j] {
            i++
        } else {
            j--
        }
    }
    return res
}

max_capacity.swift

/* 최대 용량: 탐욕 */
func maxCapacity(ht: [Int]) -> Int {
    // i와 j가 각각 배열의 양 끝을 가리키도록 초기화한다
    var i = ht.startIndex, j = ht.endIndex - 1
    // 최대 용량의 초깃값은 0이다
    var res = 0
    // 두 칸막이가 만날 때까지 탐욕적 선택을 반복한다
    while i < j {
        // 최대 용량을 갱신한다
        let cap = min(ht[i], ht[j]) * (j - i)
        res = max(res, cap)
        // 낮은 칸막이를 안쪽으로 이동한다
        if ht[i] < ht[j] {
            i += 1
        } else {
            j -= 1
        }
    }
    return res
}

max_capacity.js

/* 최대 용량: 탐욕 */
function maxCapacity(ht) {
    // i와 j가 각각 배열의 양 끝을 가리키도록 초기화한다
    let i = 0,
        j = ht.length - 1;
    // 최대 용량의 초깃값은 0이다
    let res = 0;
    // 두 칸막이가 만날 때까지 탐욕적 선택을 반복한다
    while (i < j) {
        // 최대 용량을 갱신한다
        const cap = Math.min(ht[i], ht[j]) * (j - i);
        res = Math.max(res, cap);
        // 낮은 칸막이를 안쪽으로 이동한다
        if (ht[i] < ht[j]) {
            i += 1;
        } else {
            j -= 1;
        }
    }
    return res;
}

max_capacity.ts

/* 최대 용량: 탐욕 */
function maxCapacity(ht: number[]): number {
    // i와 j가 각각 배열의 양 끝을 가리키도록 초기화한다
    let i = 0,
        j = ht.length - 1;
    // 최대 용량의 초깃값은 0이다
    let res = 0;
    // 두 칸막이가 만날 때까지 탐욕적 선택을 반복한다
    while (i < j) {
        // 최대 용량을 갱신한다
        const cap: number = Math.min(ht[i], ht[j]) * (j - i);
        res = Math.max(res, cap);
        // 낮은 칸막이를 안쪽으로 이동한다
        if (ht[i] < ht[j]) {
            i += 1;
        } else {
            j -= 1;
        }
    }
    return res;
}

max_capacity.dart

/* 최대 용량: 탐욕 */
int maxCapacity(List<int> ht) {
  // i와 j가 각각 배열의 양 끝을 가리키도록 초기화한다
  int i = 0, j = ht.length - 1;
  // 최대 용량의 초깃값은 0이다
  int res = 0;
  // 두 칸막이가 만날 때까지 탐욕적 선택을 반복한다
  while (i < j) {
    // 최대 용량을 갱신한다
    int cap = min(ht[i], ht[j]) * (j - i);
    res = max(res, cap);
    // 낮은 칸막이를 안쪽으로 이동한다
    if (ht[i] < ht[j]) {
      i++;
    } else {
      j--;
    }
  }
  return res;
}

max_capacity.rs

/* 최대 용량: 탐욕 */
fn max_capacity(ht: &[i32]) -> i32 {
    // i와 j가 각각 배열의 양 끝을 가리키도록 초기화한다
    let mut i = 0;
    let mut j = ht.len() - 1;
    // 최대 용량의 초깃값은 0이다
    let mut res = 0;
    // 두 칸막이가 만날 때까지 탐욕적 선택을 반복한다
    while i < j {
        // 최대 용량을 갱신한다
        let cap = std::cmp::min(ht[i], ht[j]) * (j - i) as i32;
        res = std::cmp::max(res, cap);
        // 낮은 칸막이를 안쪽으로 이동한다
        if ht[i] < ht[j] {
            i += 1;
        } else {
            j -= 1;
        }
    }
    res
}

max_capacity.c

/* 최대 용량: 탐욕 */
int maxCapacity(int ht[], int htLength) {
    // i와 j가 각각 배열의 양 끝을 가리키도록 초기화한다
    int i = 0;
    int j = htLength - 1;
    // 최대 용량의 초깃값은 0이다
    int res = 0;
    // 두 칸막이가 만날 때까지 탐욕적 선택을 반복한다
    while (i < j) {
        // 최대 용량을 갱신한다
        int capacity = myMin(ht[i], ht[j]) * (j - i);
        res = myMax(res, capacity);
        // 낮은 칸막이를 안쪽으로 이동한다
        if (ht[i] < ht[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}

max_capacity.kt

/* 최대 용량: 탐욕 */
fun maxCapacity(ht: IntArray): Int {
    // i와 j가 각각 배열의 양 끝을 가리키도록 초기화한다
    var i = 0
    var j = ht.size - 1
    // 최대 용량의 초깃값은 0이다
    var res = 0
    // 두 칸막이가 만날 때까지 탐욕적 선택을 반복한다
    while (i < j) {
        // 최대 용량을 갱신한다
        val cap = min(ht[i], ht[j]) * (j - i)
        res = max(res, cap)
        // 낮은 칸막이를 안쪽으로 이동한다
        if (ht[i] < ht[j]) {
            i++
        } else {
            j--
        }
    }
    return res
}

max_capacity.rb

### 최대 용량: 탐욕 ###
def max_capacity(ht)
  # i와 j가 각각 배열의 양 끝을 가리키도록 초기화한다
  i, j = 0, ht.length - 1
  # 최대 용량의 초깃값은 0이다
  res = 0

  # 두 칸막이가 만날 때까지 탐욕적 선택을 반복한다
  while i < j
    # 최대 용량을 갱신한다
    cap = [ht[i], ht[j]].min * (j - i)
    res = [res, cap].max
    # 낮은 칸막이를 안쪽으로 이동한다
    if ht[i] < ht[j]
      i += 1
    else
      j -= 1
    end
  end

  res
end

코드 시각화

전체 화면 >

3. 정확성 증명¶

탐욕 알고리즘이 모든 경우 열거보다 빠른 이유는 매번 일부 상태를 '건너뛰기' 때문이다.

예를 들어 상태 \(cap[i, j]\)에서 \(i\)가 낮은 칸막이, \(j\)가 높은 칸막이라고 하자. 낮은 \(i\)를 탐욕적으로 한 칸 안쪽으로 옮기면 아래 그림(15-12)의 상태들을 건너뛴다. 이는 이후에 그 상태들의 용량을 확인할 수 없다는 뜻이다.

\[ cap[i, i+1], cap[i, i+2], \dots, cap[i, j-2], cap[i, j-1] \]

낮은 칸막이를 옮겨 건너뛴 상태들

그림 15-12 낮은 칸막이를 옮겨 건너뛴 상태들

건너뛴 상태들은 사실 높은 칸막이 \(j\)를 안쪽으로 옮긴 모든 상태다. 앞에서 높은 칸막이를 안쪽으로 옮기면 용량이 반드시 줄어듦을 보였다. 따라서 건너뛴 상태는 최적해가 될 수 없으며, 이를 건너뛰어도 최적해를 놓치지 않는다.

이 분석은 낮은 칸막이를 옮기는 연산이 '안전'하며 탐욕 전략이 유효함을 보여 준다.

15.3 최대 용량 문제¶

1. 탐욕 전략 결정¶

2. 코드 구현¶

3. 정확성 증명¶

댓글로 의견이나 질문, 제안을 남겨 주세요