그 유명한 탐욕스러운 알고리즘이 드디어 출시되었습니다.
살아남는 법을 배워야 한다
Greedy의 알고리즘은 각 단계에서 로컬 최적 선택을 선택합니다.
local 의 의미는 반복할 때마다 즉시 할 수 있는 선택을 의미하며, Optimal은 문제가 요구하는 바에 따라 다르지만, 문제가 두 요소의 최대 합을 원할 때 가장 큰 두 값을 선택하는 것과 같습니다.
대부분의 욕심 많은 문제는 무언가의 최대 또는 최소를 요구합니다.
네트워크 문제는 단어에서 알 수 있듯이 “욕구”로 가득 찬 선택으로 볼 수 있습니다.
이것은 내가 계속해서 지역 이익을 극대화하는 결정을 내리는 것을 의미합니다.
다음과 같이 해석할 수 있습니다.
많은 힙 관련 문제를 그리드 문제라고 합니다.
이는 힙 문제가 최대 및 최소 요소를 고려하므로 각 단계에서 최상의 선택을 고려하기 때문입니다.
Greedy는 데이터 구조도 알고리즘도 아닌 문제에 대한 접근 방식입니다.
욕심은 매우 일반적이며 문제를 식별할 수 있는 것이 매우 중요합니다!
예를 들어 전에 풀었던 문제
당신은 정수 배열을 얻을 것이다 키 길이 N. 있다 N 의 두 끝점이 되도록 수직선을 그립니다.
~와 함께 라인은 (나, 0) 그리고 (i, 높이(i)).
x축과 함께 상자를 형성하는 두 개의 선을 찾습니다.
용기에 대부분의 물이 담기도록 합니다.
돌려 주다 탱크가 저장할 수 있는 최대 물의 양.
메모 용기를 기울이면 안 됩니다.
예 1:
Input: height = (1,8,6,2,5,4,8,3,7)
Output: 49
Explanation: The above vertical lines are represented by array (1,8,6,2,5,4,8,3,7). In this case, the max area of water (blue section) the container can contain is 49.
예 2:
Input: height = (1,1)
Output: 1
답변
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size()-1;
int maxarea = 0;
while(left<right)
{
int width = (right-left);
maxarea=max(maxarea,min(height(left),height(right))*width );
if (height(left) < height(right))
{
left ++;
}
else
{
right --;
}
}
return maxarea;
}
};보시다시피 특별한 데이터 구조를 사용하지 않고, 일종의 사고력과 문제 해결 능력… 많이 풀 수밖에 없습니다.