Chap6 그리디 알고리즘

1. 개념

현재 상태에서 보는 최선의 선태이 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘

2. 대표 코드

코드 작동 원리

• 해 선택: 현재 상태에서 최선이라고 생각되는 해를 선택
• 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에서 벗어나지 않는지 검사
• 해검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사
  -> 전체 문제를 해결하지 못한다면 처음으로 돌아가 '해 선택'부터 반복

3. 문제1: 동전 0 11047번

1. 문제: https://www.acmicpc.net/problem/11047
   

2. 코드

• 가격이 큰 것부터 k보다 작거나 같은 동전이 나올 때까지 탐색
• 예제코드1로 설명해보면(k=4200)
  4200/1000=4 -> sum=4, k=200
• 아직 k가 0보다 크니까, 이 과정을 반복
• 200/100=2 -> sum+=2, k=0
• 결과(sum)는 6이 됨

#include<iostream>
#include<vector> 
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	cin >> n >> k;

	vector <int> coin(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> coin[i];
	}

	int sum = 0;
	for (int i = n - 1; i >= 0; i--) {
		if (k >= coin[i]) {
			sum += (k / coin[i]); //4200/1000=4
			k = k % coin[i]; //4200%1000=200
		}
	}

	
	cout << sum;
	return 0;
}

4. 문제2: 잃어버린 괄호 1541번

1. 문제: https://www.acmicpc.net/problem/1541
   

2. 코드

• atoi() -> 문자열을 정수형으로 바꿔주는 기능
• 20-50+40 -> 20-(50+40) 이어야 최솟값이 됨
  20-50+40-30+20 -> 20-(50+40)-(30+20) -> 최솟값
  => 덧셈을 최대한 뺄셈으로 바꿔주는 것이 중요
• '-' 를 만난뒤에 나오는 '+' 는 '-' 처리되어야함
  '-' 를 만나기 전에 나오는 + 는 그대로 + 처리
• 문제에 - 를 한번만 써야한다는 제약은 없으므로 - 뒤에 나오는 모든 + 를 - 로 계속 바꿔주면 됨

#include<iostream>
#include<string> //문자열을 숫자로 바꿔줄 수 있는 기능!
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string number = "";
	int res = 0;
	string s;
	cin >> s;
	bool isMinus = false;

	for (int i = 0; i <= s.length(); i++) {
		if (s[i] == '+' || s[i] == '-' || i == s.length()) {
			if (isMinus) {
				res -= stoi(number); //문자열을 정수형으로 바꿔줌
				number = "";
			}
			else {
				res += stoi(number);
				number = "";
			}
		}
		else { //숫자를 만난 경우
			number += s[i];
		}

		if (s[i] == '-') {
			isMinus = true;
		}

	}
	cout << res;
	return 0;
}

5 못푼 문제들

https://www.acmicpc.net/problem/1931
https://www.acmicpc.net/problem/1744
https://www.acmicpc.net/problem/1715