[LeetCode] 11. Container With Most Water - 풀이와 증명

문제 설명

다음과 같이 막대가 일정 간격으로 배치되어 있다. 이 중 가장 많은 물을 담을 수 있는 컨테이너를 두 개의 막대를 이용해서 만드려고 한다. 이 때 들어가는 최대 물의 양은 얼마인가?

풀이

가장 기본적인 접근은 모든 막대 쌍을 brute-force로 완전 탐색하는 방법으로, \(O(n^2)\)만큼의 시간이 걸린다. 이것을 더 빠르게 작동하도록 계산할 수 있을까?

 

이 문제는 탐욕법을 통해서 O(n) 안에 푸는 알고리즘으로 해결 가능하다. (아직까지 탐욕법으로 접근해야 하는 이유에 대해서는 명확히 찾지 못하였다)

 

알고리즘은 다음과 같다:

1. 두 막대로 첫 번째 막대와 마지막 막대를 이용했을 때로 문제를 처음 시작한다.

2. 두 막대 중 짧은 쪽을 선택한다.

3. 선택한 막대 안쪽으로 한 칸씩 순회하며 그 막대의 길이보다 긴 막대가 나타나면 중지한다. 선택한 막대를 새로 찾은 더 긴 막대로 갱신한다.

4. 새롭게 선택된 막대들을 기준으로 물의 양을 계산하여 최대치를 갱신하고 2번으로 돌아간다. 두 막대가 만나면 알고리즘은 종료되고 지금까지 계산한 최대 물의 양을 반환한다.

 

Go로 다음과 같이 구현한다.

func maxArea(height []int) int {
    i := 0
    j := len(height) - 1
    max_area := 0

    for i < j {
        h1 := height[i]
        h2 := height[j]
        area := min(h1, h2) * (j - i)
        max_area = max(area, max_area)
        if h1 < h2 {
            for i < j {
                i += 1
                if h1 < height[i] { break }
            }
        } else {
            for i < j {
                j -= 1
                if h2 < height[j] { break }
            }
        }
    }
    return max_area
}

 

증명

'막대의 길이' 별로 가둘 수 있는 물의 최대 양을 기준으로 귀납 가설을 설정하면 탐욕법으로 언제나 최적의 해를 찾을 수 있음을 보일 수 있다.

Claim. 제안한 알고리즘에서 짧은 쪽의 길이가 h일 때까지 수행하여 찾은 최대 물의 양은 컨테이너의 세로 길이가 h 이하인 모든 가능한 물의 양의 최대이다.

 

귀납법을 통해 이 가설이 사실임을 증명할 것이다.

• Initialization. 초기 상태에서는, 짧은 쪽 막대의 높이를 가지는 컨테이너의 가로 길이가 배열 전체로 설정어 있으므로 찾을 수 있는 최대의 컨테이너에 해당한다. 따라서 Claim이 옳다.
• Assumption. Claim이 짧은 쪽 막대의 길이가 \(h_i\) 이하인 경우까지는 옳다고 확인되었다고 하자.
• Update. 짧은 쪽 막대의 길이가 \(h_i\)에서 \(h_{i+1}\)로 대체된 경우 (\(h_i < h_{i+1}\)), Claim이 아직도 성립하는가?
  물의 높이가 \(h_{i+1}\)일 때 가둘 수 있는 최대 물의 양은, 배열 전체에서 왼쪽에서 첫번째로 막대의 길이가 \(h_{i+1}\) 이상이고, 오른쪽에서 첫번째로 막대의 길이가 \(h_{i+1}\) 이상인 경우로 계산해야 최적이다. 이 알고리즘에서는 두 쌍의 막대에서 짧은 쪽 막대만 안쪽의 더 긴 막대로 대체하면서 수정하므로, 이 최적해를 계산하는 경우에 해당한다. 따라서 Claim이 옳다.

알고리즘이 종료되는 시점에서는 배열에 존재하는 최대 막대 길이 (정확히는 두번째 최대 막대 길이)까지 Claim이 검증되고, 이는 배열 전체에서 찾을 수 있는 모든 물의 양을 의미한다.