[C++]第11次


#ルーティングアルゴリズム

  • 完全ナビゲーションアルゴリズム
  • シーケンシャルナビゲーション、深度優先探索(DFS)、割り込み優先探索(BFS)
  • #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;
    }