그리디 알고리즘 다음을 수행하는 알고리즘 클래스입니다. 국소적으로 최적 각 단계에서 선택을 찾고 전역 최적 해결책. 이러한 알고리즘에서는 미래 결정의 결과를 고려하지 않고 현재 이용 가능한 정보를 기반으로 결정이 내려집니다. 핵심 아이디어는 각 단계에서 가능한 최상의 선택을 선택하여 항상 가장 최적이 아닐 수도 있지만 종종 많은 문제에 대해 충분히 좋은 솔루션을 찾는 것입니다.
이번 글에서는 예시를 통해 그리디 알고리즘을 이해해보겠습니다. 그리디 접근법을 활용한 문제와 해결책도 살펴보겠습니다.
그리디 알고리즘
내용의 테이블
- 그리디 알고리즘이란 무엇입니까?
- 그리디 알고리즘을 생성하는 단계
- 그리디 알고리즘 예
- 그리디 알고리즘의 응용
- 탐욕 알고리즘 사용의 단점/한계
- 그리디 알고리즘의 기본
- 표준 탐욕 알고리즘
- 어레이의 탐욕스러운 문제
- 운영 체제의 탐욕스러운 문제
- 그래프의 그리디 문제
- NP Complete에 대한 대략적인 탐욕 알고리즘
- DP의 특별한 경우에 대한 욕심
- 그리디 알고리즘의 쉬운 문제
- 그리디 알고리즘의 중간 문제
- 그리디 알고리즘의 어려운 문제
그리디 알고리즘이란 무엇입니까?
ㅏ 그리디 알고리즘 전역적으로 최적의 솔루션을 찾기 위해 각 단계에서 지역적으로 최적의 선택을 하는 최적화 알고리즘의 일종입니다. 장기적인 결과를 고려하지 않고 지금 최선의 선택을 한다는 원칙에 따라 운영됩니다.
그리디 방법이 무엇인지, 그리디 접근 방식을 사용하는 방법을 알아보려면 Greedy 알고리즘에 대한 튜토리얼을 읽어보세요.
그리디 알고리즘을 생성하는 단계
그리디 알고리즘을 정의하는 단계는 다음과 같습니다.
- 문제를 정의하십시오: 해결해야 할 문제와 최적화해야 할 목표를 명확하게 설명합니다.
- 탐욕스러운 선택을 식별하십시오. 현재 상태를 기반으로 각 단계에서 국소적으로 최적의 선택을 결정합니다.
- 탐욕스러운 선택을 하세요: 욕심 많은 선택을 선택하고 현재 상태를 업데이트합니다.
- 반복하다: 해결책이 나올 때까지 탐욕스러운 선택을 계속하십시오.
주어진 단계에 따라 그리디 알고리즘을 사용하여 최적의 솔루션을 찾는 방법을 배울 수 있습니다.
그리디 알고리즘 예
그리디 알고리즘의 예는 알고리즘을 이해하는 가장 좋은 방법입니다. 그리디 알고리즘의 실제 사례는 다음과 같습니다.
- 분수 배낭 : 제한된 용량의 배낭에 부분적으로 포함될 수 있는 품목의 가치를 최적화합니다.
- Dijkstra의 알고리즘 : 가중치 그래프의 소스 정점에서 다른 모든 정점까지의 최단 경로를 찾습니다.
- 크루스칼의 알고리즘 : 가중치 그래프의 최소 스패닝 트리를 찾습니다.
- 허프만 코딩 : 더 자주 사용되는 기호에 더 짧은 코드를 할당하여 데이터를 압축합니다.
그리디 알고리즘의 응용
많이있다 DAA에 탐욕적 방법을 적용 . 몇 가지 중요한 탐욕 알고리즘 응용 프로그램은 다음과 같습니다.
- 대기 시간을 최소화하거나 효율성을 극대화하기 위해 리소스에 작업을 할당합니다.
- 제한된 용량의 배낭에 들어갈 가장 귀중한 품목을 선택합니다.
- 이미지를 유사한 특성을 가진 영역으로 분할합니다.
- 중복된 정보를 제거하여 데이터 크기를 줄입니다.
탐욕 알고리즘 사용의 단점/한계
Greedy 알고리즘의 몇 가지 단점은 다음과 같습니다.
- 그리디 알고리즘이 항상 최상의 솔루션을 찾는 것은 아닙니다.
- 요소가 고려되는 순서는 결과에 큰 영향을 미칠 수 있습니다.
- 그리디 알고리즘은 로컬 최적화에 중점을 두며 더 넓은 맥락을 고려해야 하는 더 나은 솔루션을 놓칠 수 있습니다.
- 탐욕스러운 선택이 최적의 솔루션으로 이어지지 않는 문제에는 탐욕 알고리즘을 적용할 수 없습니다.
그리디 알고리즘의 기본:
- 그리디 알고리즘(일반 구조 및 응용)
- 탐욕 알고리즘과 분할 정복 알고리즘의 차이점
- 욕심 많은 접근 방식과 동적 프로그래밍
- Greedy, Divide and Conquer와 동적 프로그래밍 알고리즘의 비교
표준 탐욕 알고리즘:
- 활동 선택 문제
- 작업 순서 문제
- 허프만 코딩
- 허프만 디코딩
- 물 연결 문제
- 브래킷 밸런싱을 위한 최소 스왑
- 이집트 분수
- 경찰이 도둑을 잡는다
- 피팅 선반 문제
- 구멍에 마우스 할당
어레이의 탐욕스러운 문제:
- 배열의 최소 제품 하위 집합
- 정렬을 사용하여 K개의 부정 후 배열 합계 최대화
- 두 배열의 곱의 최소 합
- 두 배열 쌍의 절대 차이의 최소 합
- 배열을 증가하지 않게 만드는 최소 증가/감소
- 중간을 중심으로 역순으로 배열 정렬
- 배열에 가능한 직사각형 면적의 합
- 최대 K개 연속 스왑을 포함하는 최대 사전식 배열
- 합의 차이가 최대가 되도록 길이가 k와 (N – k)인 두 개의 하위 배열로 분할합니다.
운영 체제의 탐욕스러운 문제:
- 메모리 관리의 First Fit 알고리즘
- 메모리 관리의 최적합 알고리즘
- 메모리 관리의 최악 맞춤 알고리즘
- 최단 작업 우선 스케줄링
- 한 번에 두 개의 작업이 허용되는 작업 예약
- 최적의 페이지 교체 알고리즘을 위한 프로그램
그래프의 그리디 문제:
- 크루스칼의 최소 스패닝 트리
- Prim의 최소 스패닝 트리
- Boruvka의 최소 스패닝 트리
- Dijkastra의 최단 경로 알고리즘
- 다이얼의 알고리즘
- 모든 도시를 연결하는 데 필요한 최소 비용
- 최대 흐름 문제 소개
- 무방향 그래프의 단일 주기 구성 요소 수
NP 완전을 위한 대략적인 탐욕 알고리즘:
- 표지 문제 설정
- 빈 포장 문제
- 그래프 색칠
- K-센터 문제
- 최단 슈퍼스트링 문제
- MST를 사용하여 여행하는 외판원 문제에 대한 대략적인 솔루션
DP의 특별한 경우에 대한 욕심:
- 분수 배낭 문제
- 필요한 최소 코인 수
Greedy의 쉬운 문제 연산 :
- n을 최대 합성수로 나누기
- i번째 날에 i주식을 구매할 수 있는 경우 최대 주식을 구매하세요.
- N개 사탕을 모두 구매하기 위한 최소 및 최대 금액을 구하세요.
- 가능한 최대 합계는 3개 스택의 합계와 같습니다.
- 부피의 합이 최대가 되도록 직육면체를 큐브로 나눕니다.
- 주어진 수량으로 만족할 수 있는 최대 고객 수
- 원형 자물쇠를 잠금 해제하기 위한 최소 회전
- 주어진 일정에 따라 n개 배치로 구성된 m개 이벤트를 위한 최소 공간
- 더 큰 쌍을 제거하여 배열 크기를 1로 만드는 데 드는 최소 비용
- 모든 코인에 허용되는 k개의 추가 코인으로 모든 코인을 획득하기 위한 최소 비용
- 모든 요소를 동일하게 만들기 위한 k 연산의 최소 증분
- 주어진 금액에 합산되는 최소 통화 메모 수와 가치를 찾습니다.
- 합이 다른 모든 요소보다 큰 가장 작은 부분 집합
Greedy의 중간 문제 연산 :
- 정차가 가능한 최대 열차수
- 합이 K인 최소 피보나치 항
- 1~n을 최소 합계 차이를 갖는 두 그룹으로 나눕니다.
- 최소 정사각형 수로 자른 용지
- 크기가 2인 그룹 간의 최소 차이
- 최소 비용으로 n개의 로프 연결
- 철도/버스 정류장에 필요한 최소 플랫폼 수
- 주어진 조건으로 전체 행렬을 순회하는 최소 초기 정점
- 숫자를 치환하여 가장 큰 회문수
- 주어진 자릿수와 자릿수 합계로 가장 작은 수 찾기
- 모든 문자가 최소한 k 번 발생하도록 사전순으로 가장 큰 부분 수열
Greedy의 어려운 문제 연산 :
- k 업데이트와 동일하게 만들 수 있는 최대 요소
- 친구들 사이의 현금 흐름을 최소화하세요
- 보드를 사각형으로 자르는 데 드는 최소 비용
- 전환 비용이 발생하는 m개 작업을 처리하는 데 필요한 최소 비용
- 주어진 제약 조건이 있는 모든 작업을 완료하는 데 필요한 최소 시간
- 타워 높이 차이 최대 최소화
- 소스에서 대상까지의 경로를 만들기 위해 반전해야 할 최소 간선
- 숫자에서 최소 자릿수를 삭제하여 형성된 가장 큰 큐브 찾기
- 인접한 두 개가 동일하지 않도록 문자열의 문자를 재배열합니다.
- 모든 동일한 문자가 d 거리만큼 멀어지도록 문자열을 재배열합니다.
빠른 링크:
- 데이터 구조와 알고리즘 배우기 | DSA 튜토리얼
- 그리디 알고리즘 인터뷰 질문 상위 20개
- 그리디 알고리즘의 '연습 문제'
- 그리디 알고리즘에 관한 '퀴즈'