Algorithm C++ [220118] :: Greedy - 2 (이것이 코딩테스트다 학습 정리) ... 추가 수정 예정...

난이도 하 Greedy

---

✔ min, max, minmax function in C++

• {}를 사용하여 3개 이상 값들에 대해서도 최대, 최소값을 구할 수 있음
• vector 같은 container에 저장되어 있다면, max_element, min_element func 사용 가능

#include <iostream>
#include <algorithm>
int main(void){
	int a,b;
    int result;
    cin>>a>>b;
    result = max(a,b); // a,b 중 큰 값 반환
    cout >> result >> endl;
}

 

✔ Class를 min, max에 넣는 방법 => operator< 재정의 필요!

예제 참고 :: https://blockdmask.tistory.com/366

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

class Animal
{
private:
	int age;    
	int legs; 

public:
	Animal(int _age, int _legs) : age(_age), legs(_legs) {};    //생성자

	//나이 확인, 나이 같으면 다리개수 확인
	bool operator<(const Animal& _animal) const
	{
		if (age != _animal.age)
			return age < _animal.age;
		return legs < _animal.legs;
	}

	// cout 출력을 위한 "<<" 재정의.
	friend ostream& operator<<(ostream& _os, const Animal& _animal);
};

// cout 출력을 위한 "<<" 재정의.
ostream& operator<<(ostream& _os, const Animal& _animal)
{
	_os << _animal.age << '/' << _animal.legs;
	return _os;
}

int main(void) {
	cout << "강아지 vs 새" << endl << endl;
	Animal puppy1(15, 4);
	Animal puppy2(10, 4);
	Animal bird1(10, 2);
	Animal bird2(14, 2);

	cout << "min(puppy1, bird2) :: " << min(puppy1, bird2) << endl; // bird2
	cout << "max(puppy2, bird1) :: " << max(puppy2, bird1) << endl; // puppy2
}

 

 

✔ Vector에서 min, max 사용 방법

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> vecnum = { 40,58,2,6,7,92 };
int main(void) {
	int len = vecnum.size();

	// min, max 비교위해 벡터 맨 처음 요소 저장
	int small = vecnum[0];
	int large = vecnum[0];

	for (int i = 1; i < len; i++) {
		small = min(small, vecnum[i]); // 비교하여 작은 값 small에 넣기
		large = max(large, vecnum[i]); // 비교하여 큰 값 large에 넣기
	}
	cout << small << endl;
	cout << large << endl;
}

 

✔ minmax func

 

1. auto :: 자동으로 변수 type 지정해주는 키워드

auto a = 1; // a는 int type
auto b = "Hello"; // b는 string type

 

2. pair class :: 두개의 type -> 한개의 type으로 묶어주는 클래스

pair<int, int> p;           //int 타입과 int 타입을 하나의 타입으로 묶음

pair<string, int> p;      //string 타입과 int 타입을 하나의 타입으로 묶음

pair<int, float> p;        //int 타입과 float 타입을 하나의 타입으로 묶음

pair<string, string> p; //int 타입과 string 타입을 하나의 타입으로 묶음

** 나중에 수정/추가 예정

너무 정리, 설명 완벽한 블로그 ㅠㅠㅠ 
출처: https://blockdmask.tistory.com/367 [개발자 지망생]

 

---

[문제 3] 숫자 카드 게임 

문제 이해 안 됨... ㅋㅎ

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

int main() {
	int n, m;
	cin >> n >> m; // 행, 열 입력받기
	int result;

	for (int i = 0; i < n; i++) {
		// 현재 줄에서 가장 작은 수 찾기
		int min_num = 10001;
		for (int j = 0; j < m; j++) {
			int x;
			cin >> x; // 숫자 카드 입력받기
			min_num = min(min_num, x);
		}
		//가장 작은 수 중에서 가장 큰 수 찾기
		result = max(result, min_num);
	}
	cout << result << endl;
}

 

 

[문제 4] 1이 될 때까지 

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

int main() {
	int n, k;
	cin >> n >> k;
	int result;
	while (1) {
		// n이 k로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
		int target = (n / k) * k;
		result += (n - target);
		n = target;

		// n<k break
		if (n < k)
			break;

		//k로 나누기
		result += 1;
		n /= k;
	}
	result += (n - 1); // 남은 수에 대해서 1씩 빼기
	cout << result << endl;
}