[c++] 백준 11단계

알감자·2022년 3월 21일

백준알고리즘

목록 보기

11/52

#브루트포스(Brute Force) 알고리즘

완전 탐색 알고리즘
순차탐색, DFS(Depth First Search), BFS(Breadth First Search)

#2798

#include <iostream>
using namespace std;

int main() 
{
	int N, M, sum, ans;
	int min = 99999;
	cin >> N >> M;

	int *arr = new int[N];

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	for (int i = 0; i < N-2; i++) //최소 3개의 숫자를 더해야하므로 N-2까지
	{
		for (int j = i+1; j < N - 1; j++) //두번째 수까지 더해야하므로 i+1 부터 N-1
		{
			for (int k = j + 1; k < N; k++) //세번째 수는 두번째 수 다음이므로 j+1 부터 N까지
			{
				sum = arr[i] + arr[j] + arr[k];
				if (M - sum < min && M - sum >= 0) //합은 M을 넘으면 안됨
				{
					min = M - sum;
					ans = sum;
				}
			}
		}
	}

	delete[] arr;
	cout << ans;
	return 0;
}

#2231

#include <iostream>
using namespace std;

int main() 
{
	//todo
	//1. 자릿수 구하기
	//2. sum구하기 -> 자기자신 + 각 자릿수의 합
	//3. sum == N 이면 출력하기

	int N, temp;
	int digit = 0;
	int sum = 0;

	cin >> N;
	temp = N;

	while (temp)
	{
		temp /= 10;
		digit++;
	}

	for (int i = N - (9 * digit); i <= N - 1; i++)
	{
		int temp = i;
		sum += temp;

		while (temp)
		{
			sum += (temp%10);
			temp /= 10;
		}

		if (sum == N)
		{
			cout << i << "\n";
			return 0;
		}

		sum = 0;
	}

	cout << "0";
	return 0;
}

#7568

//앞에서부터 뒤까지 순차적으로 비교해주며 덩치가 작을때마다 순위를 ++해주어야함. (i가 바뀔때마다 처음부터 끝까지 다시 비교)

#include <iostream>
using namespace std;

int main() 
{
	int N;
	int score = 1;
	cin >> N;

	/*2차원 배열 동적할당*/
	int** arr = new int *[N];
	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[2];
	}

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i][0] >> arr[i][1];
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1])   //x1 < x2 && y1 < y2
			{
				score++;
			}
		}
		cout << score << " ";
		score = 1;
	}

	/*2차원 배열 해제*/
	for (int i = 0; i < N; i++)
	{
		delete[] arr[i];
	}
	delete[] arr;

	return 0;
}

#1018

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

char white[8][8] = {
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W'
};

char black[8][8] = {
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B',
	'B','W','B','W','B','W','B','W',
	'W','B','W','B','W','B','W','B'
};

char arr[51][51];

int check_white(int x, int y)
{
	int count = 0;

	for(int i=0; i<8; i++)
		for (int j = 0; j < 8; j++)
		{
			if (arr[x + i][y + j] != white[i][j])
				count++;
		}

	return count;
}

int check_black(int x, int y)
{
	int count = 0;

	for (int i = 0; i<8; i++)
		for (int j = 0; j < 8; j++)
		{
			if (arr[x + i][y + j] != black[i][j])
				count++;
		}

	return count;
}

int main() 
{
	int N, M, b, w;
	int minimum = 10000;
	int black_cnt = 0;
	int white_cnt = 0;
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> arr[i][j];

	for (int k = 0; k+8 <= N; k++)
	{
		for (int l = 0; l+8 <= M; l++)
		{
			int tmp;
			b = check_black(k, l);
			w = check_white(k, l);

			tmp = min(b, w);
			if (tmp < minimum)
				minimum = tmp;
		}
	}
	cout << minimum;
	return 0;
}

#1427

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

bool compare(char a, char b)
{
	return a > b;
}

int main() 
{
	string str;
	cin >> str;

	sort(str.begin(), str.end(), compare);
	
	cout << str;
	
	return 0;
}

#11650

//처음에 struct로 풀어보다가 vector에 pair로 풀 수 있다해서 바꿨다,,

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

int main() 
{
	int N, x, y;
	vector<pair<int,int>> arr;

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> x >> y;
		arr.push_back({ x,y });
	}

	sort(arr.begin(), arr.end());


	for (int i = 0; i < N; i++)
	{
		cout << arr[i].first << " " << arr[i].second << "\n";
	}

	return 0;
}

#11651

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

bool compare(pair<long, long> a, pair<long, long> b)
{
	if (a.second == b.second)
		return a.first < b.first;
	else
		return a.second < b.second;
}

int main() 
{
	int N, x, y;
	vector<pair<long,long>> arr;

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> x >> y;
		arr.push_back({ x,y });
	}

	sort(arr.begin(), arr.end(), compare);

	for (int i = 0; i < N; i++)
	{
		cout << arr[i].first << " " << arr[i].second << "\n";
	}

	return 0;
}

#1181

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

bool compare(string a, string b)
{
	if (a.length() == b.length())
	{
		for (int i = 0; i < a.length(); i++)
		{
			if (a[i] != b[i])  //alphabet순 정렬
				return a[i] < b[i];
		}
	}

	return a.length() < b.length();
}

int main() 
{
	int N;
	string str;
	vector<string> arr;
	
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> str;
		arr.push_back(str);
	}

	sort(arr.begin(), arr.end(), compare);

	for (int i = 0; i < N; i++)
	{
		if (i > 0 && arr[i] == arr[i - 1])
			continue;

		cout << arr[i] << "\n";
	}

	return 0;
}

#10814

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

struct person {
	int index;
	int age;
	string name;
};

bool compare(person a, person b)
{
	if (a.age < b.age)
		return true;
	else if (a.age == b.age)
		return a.index < b.index;
	else
		return false;
}

int main() 
{
	//저장해야 하는 것 : 들어온 순서, 나이, 이름
	//struct 사용해서 풀어보기
	int N;
	cin >> N;
	vector<person> p(N);

	for (int i = 0; i < N; i++)
	{
		cin >> p[i].age >> p[i].name;
		p[i].index = i;
	}

	sort(p.begin(), p.end(), compare);

	for (int i = 0; i < N; i++)
	{
		cout << p[i].age << " " << p[i].name << "\n";
	}

	return 0;
}

#18870

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


int main() 
{
	//Todo
	//input값들을 오름차순으로 정렬
	//중복을 제거하고 index값 리턴
	//들어온 순서대로 index값을 리턴해야하므로 input값을 복사해두기

	vector<int> a, b;
	int temp, N;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> temp;
		a.push_back(temp);
		b.push_back(temp);
	}

	sort(a.begin(), a.end());
	a.erase(unique(a.begin(), a.end()), a.end()); 
    //중복되는 값 제거

	for (int i = 0; i < N; i++)
	{
		//index값 리턴
		//lower_bound의 리턴값이 iterator이므로 index값을
		//알고 싶다면 배열의 첫번째 주소인 a.begin()을 빼준다.
		cout << lower_bound(a.begin(), a.end(), b[i]) - 
        									a.begin() << " ";
	}
	
	return 0;
}