탐욕 알고리즘
- 최적해를 구하는 상황에서 사용하는 방법.
- 여러 경우 중 하나를 선택할 때 그것이 그 상황에서 가장 좋다고 생각하는 것을 선택해 나가는 방식으로 진행하여 답을 구한다.
- 늘 최적해를 보장해주진 못한다.
- 그러나, 계산 속도가 매우 빠르다는 장점이 있다.
- Dynamic Programming과 서로 보완의 개념에 있다.
풀이법
1. 해 선택 (Selection Procedure)
- 지금 당시에 가장 최적인 해를 구한 후, 이를 부분해 집합에 추가
2. 적절성 검사 (Feasibility Check)
- 새로운 부분해 집합이 적절한지 검사
3. 해 검사 (Solution Check)
- 새로운 부분해 집합이 문제의 해가 되는지 검사
- 아직 문제의 해가 완성되지 않았다면 1번부터 다시 시작.
예제
프로그래머스 _ 체육복 문제
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42862
접근
🆗 수업에 무조건 참여가 가능한 학생이 몇 명일까?
➡️ 전체 학생수(n) - 잃어버린 학생 수(lost.length) + 여벌이 있으나 도둑맞은 학생 수
1️⃣ 여분이 있는 학생의 index값을 1씩 더하고 뺀 값이 lost 배열에 있을까?
2️⃣ 검사해서 true -> true인 reverse 배열의 값을 임의의 음수로 바꾸자.
3️⃣ 들을 수 있는 학생 수를 ++한 후, 다음 reverse를 진행하면 되나?
코드
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
int[] student = new int[n+1];
//student의 수 만큼 1을 넣은 배열을 생성
for(int i=1; i<=n; i++){
student[i] = 1;
}
//잃어버린 애들은 0으로 만들어줘
for(int l : lost){
student[l]--;
}
//여벌이 있는 학생은 2로 만들어줘
for(int r : reserve){
student[r]++;
}
//빌려주자 없는애들
for(int i=1; i<=n; i++){
if(student[i]==0){
if(i+1<=n && student[i+1]==2){
student[i+1]--;
student[i]++;
}else if( i-1>=1 && student[i-1]==2){
student[i-1]--;
student[i]++;
}
}
}
//수업 참여 가능 친구 수 세자.
for(int a : student){
if(a>=1){
answer++;
}
}
return answer;
}
}
developer