구르미의 개발 이야기 구르미의 개발 이야기

[알고스팟] 울타리 쳐내기(FENCE)목표 : 책 "알고리즘 문제 해결 전략 문제 풀이" 중 문제 "울타리 쳐내기"를 풀어보자문제 URL풀이이 문제를 푸는 열쇠는 스택과 스위핑 알고리즘입니다. 스위핑 알고리즘이란 간단히 말해서 이미 연산이 진행된 이전 공간에 대해서는 연산을 하지 않는다라고 생각하시면 됩니다. 개념 자체는 쉽습니다만... 굉장히 생각하기 어렵다는게 함정입니다. 이 문제를 예를 들어 설명하겠습니다. 이 문제에서 우리가 사각형을 구하기 위해 필요한 정보는 그 사각형의 왼쪽 끝과 오른쪽 끝 그리고 높이입니다. 높이가 오른쪽 끝점의 높이라고 했을 때, 왼쪽으로 연속된 판자들 중 이 높이를 포함하는 가장 낮은 지점이 왼쪽 끝 점이 되겠죠. 이 성질을 이용해서, 문제를 푸는 것이죠. 그래서 어떻게 ..