구종만의 알고리즘 문제해결 책을 본 후 파이썬으로 짜봤다.
def brute_force(h):
ret = 0
N = len(h)
for left in range(N):
minHeight = h[left]
for right in range(left, N):
minHeight = min(minHeight, h[right])
ret = max(minHeight*(right-left+1), ret)
return ret
print(brute_force([7,1,5,9,6,7,3]))
print(brute_force([1,4,4,4,4,1,1]))
def divide_conquer(h):
def solve(left, right):
if left == right: return h[left]
# 이 둘이 중요.
mid = (left + right) // 2 # divide
ret = max(solve(left, mid), solve(mid+1, right)) # divide and conquer
lo , hi = mid, mid+1 # 중앙에 걸치는 녀석들을 잡기 위해
height = min(h[lo], h[hi]) # 중앙에서 낮은 판자높이를 구함. (초기값)
ret = max(ret, height*2) # [mid,mid+1]만 포함하는 너비 2인 사각형 고려
# 후처리작업 병합정렬처럼 반으로 잘라서 각개격파를 했지만
# 병합정렬과는 다르지만 부족한 면을 반복문으로 메꾸는 것.
# 사각형이 입력 전체를 덮을 때까지 확장한다.
while (left < lo or hi < right):
# 더 높은 판자를 향해 확장한다. (낮은 판자로 가면 최대값을 구할 수 없다.)
if (hi < right and (lo == left or h[lo-1] < h[hi+1])):
hi += 1
height = min(height, h[hi])
else:
lo -= 1
height = min(height, h[lo])
ret = max(ret, height*(hi-lo+1))
return ret
return solve(0, len(h)-1)
print('divide_conquer')
print(divide_conquer([7,1,5,9,6,7,3]))
print(divide_conquer([1,4,4,4,4,1,1]))
