문제 설명다음과 같이 막대가 일정 간격으로 배치되어 있다. 이 중 가장 많은 물을 담을 수 있는 컨테이너를 두 개의 막대를 이용해서 만드려고 한다. 이 때 들어가는 최대 물의 양은 얼마인가?풀이가장 기본적인 접근은 모든 막대 쌍을 brute-force로 완전 탐색하는 방법으로, \(O(n^2)\)만큼의 시간이 걸린다. 이것을 더 빠르게 작동하도록 계산할 수 있을까? 이 문제는 탐욕법을 통해서 O(n) 안에 푸는 알고리즘으로 해결 가능하다. (아직까지 탐욕법으로 접근해야 하는 이유에 대해서는 명확히 찾지 못하였다) 알고리즘은 다음과 같다:1. 두 막대로 첫 번째 막대와 마지막 막대를 이용했을 때로 문제를 처음 시작한다.2. 두 막대 중 짧은 쪽을 선택한다.3. 선택한 막대 안쪽으로 한 칸씩 순회하며 그 막..
