그리디

*이 글은 2022년 1월~2월 노션으로 진행한 알고리즘 스터디를 옮긴 글입니다. 나동빈 저자 이것이 취업을 위한 코딩테스트다를 사용해 학습했습니다.

220201 그리디 알고리즘

• 이후의 결과를 생각하지 않고 당장 가장 최선의 것을 고르는 알고리즘
• 탐욕법과 같은 뜻
• 대체로 정렬 알고리즘과 함께 사용할 때 기준을 만족시킬 수 있음.

---

거스름돈(예제3-1) (220204내용추가)

• 풀이 동전을 큰 순서대로 배열에 저장한 뒤 큰 숫자부터 나눔.
  
• 코드

  #include<iostream>
  using namespace std;
  
  int main() {
  	int A[4] = { 500,100,50,10 };
  	int n, answer;
  	answer = 0;
  	cin >> n;
  
  	for (int i = 0; i < 4; i++) {
  		answer = answer + (n / A[i]);
  		n = n % A[i];
  	}
  
  	cout << answer;
  }

---

숫자 카드 게임(220204내용추가)

• 풀이
  1. 첫번째 열의 0부터 N까지의 행 중 가장 작은 행을 찾아서 저장함
  2. 저장한 행의 0부터 M까지의 열 중 가장 작은 열을 찾아서 출력함
• 코드

  #include<iostream>
  using namespace std;
  
  int main() {
  	int a, b, c, answer=10001, idx=0, min=10001;
  	int data[100][1000];
  	cin >> a >> b;
  	for (int i = 0; i < a ; i ++ ) {
  		for (int j = 0; j < b; j++) {
  			cin >> c;
  			data[i][j] = c;
  		}
  	}
  	for (int i = 0; i < a; i++) {
  		if (data[i][0] < min) {
  			min = data[i][0];
  			idx = i;
  		}
  	}
  	for (int i = 0; i < b; i++) {
  		if (data[idx][i] < answer) {
  			answer = data[idx][i];
  		}
  	}
  	cout << answer;
  	return 0;
  }

---

큰 수의 법칙 (220204내용추가)

• 풀이
  1. 인덱스 내에서 가장 큰 수 찾음
  2. 그다음으로 큰 수 찾음 ← 정렬쓰는게 좋을듯
  3. 가장 큰 수 k번만큼 반복함. 그다음으로 큰 수 한번 씀
  4. 3번 반복
• 코드

  #include<iostream>
  #include<algorithm>
  using namespace std;
  
  bool compare(int a, int b) {
  	return a < b;
  }
  
  int main() {
  	int a, b, c, d, answer=0;
  	int data[10000];
  	cin >> a >> b >> c;
  	for (int i = 0; i < a; i++) {
  		cin >> d;
  		data[i] = d;
  	}
  	sort(data, data+a);
  
  	while (b != 0) {
  		for (int i = 0; i < c; i++) {
  			answer += data[a - 1];
  			b -= 1;
  		}
  		answer += data[a - 2];
  		b -= 1;
  	}
  	cout << answer;
  	return 0;
  }

---

1이 될 때까지 (220204내용추가)

• 풀이
  1. n이 k의 배수가 아니면 될때까지 빼줌(카운트변수사용)
  2. 배수가 되면 n이 1이 될때까지 반복해서 나눔(카운트변수사용)
  3. 카운트변수 출력
• 코드

  #include<iostream>
  using namespace std;
  
  int main() {
  	int a, b, count=0;
  	cin >> a >> b;
  	while (a != 1) {
  		if (a % b == 0) {
  			count += 1;
  			a /= b;
  		}
  		else {
  			count += 1;
  			a -= 1;
  		}
  	}
  	cout << count;
  	return 0;
  }