C++

백준 알고리즘 문제로 C++ 기초 학습 - 정렬 1

우잉~ 2024. 12. 11. 00:57
  • Sort(start, end): start ~ end 범위에 있는 인자를 오름차순(기본값)으로 정렬한다. 내림차순으로 정렬하고 싶으면 'greater<T>()'를 세번째 인자에 넣어준다.
  • begin(): 첫번째 요소의 주소를 반환
  • end(): 마지막 요소의 다음 주소를 반환

https://www.acmicpc.net/problem/1427

 

1427번: 소트인사이드

첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    string n;
    cin >> n;
    sort(n.begin(), n.end(), greater<int>());
    cout << n;
}

https://www.acmicpc.net/problem/2309

 

2309번: 일곱 난쟁이

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

www.acmicpc.net

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int arr[10];
	int sum = 0;

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

	sort(arr, arr + 9);

	for (int i = 0; i < 9; i++)
	{
		for (int j = i + 1; j < 9; j++)
		{
			if (sum - (arr[i] + arr[j]) == 100)
			{
				for (int k = 0; k < 9; k++)
				{
					if (i == k || j == k)
						continue;
					cout << arr[k] << endl;
				}
				return 0;
			}
		}
	}
	return 0;
}

https://www.acmicpc.net/problem/2751

 

2751번: 수 정렬하기 2

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

www.acmicpc.net

 

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;

    cin >> n;

	int* arr = new int[n];

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

	sort(arr, arr + n);

	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << '\n';
	}
}

 

 

https://www.acmicpc.net/problem/11004

 

11004번: K번째 수

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

  • ios::sync_with_stdio(false): c 표준 stream과 c++ 표준 stream 동기화 끊기 - cin/cout 속도가 c의 입출력 속도에 비해 떨어지기 때문에 동기화를 비활성화함으로써 c++만의 독립적인 버퍼가 생성 -> 사용되는 버퍼 수 감소 -> 속도 향상
  • cin.tie(NULL): cin과 cout 묶음을 풀어줌 -> 입력 요청 전에 출력 작업이 있었을 경우 버퍼를 지우는 과정이 이루어지면서 시간이 오래 걸린다. 
#include <iostream>
#include <algorithm>

using namespace std;

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

    int n, k;

    cin >> n >> k;

    int* arr = new int[n];

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

    sort(arr, arr + n);
    cout << arr[k-1];
}

https://www.acmicpc.net/problem/11650

 

11650번: 좌표 정렬하기

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

www.acmicpc.net

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n, x, y;

    cin >> n;

    vector<pair<int, int>> v;

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

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

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

}

https://www.acmicpc.net/problem/11651

 

11651번: 좌표 정렬하기 2

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

www.acmicpc.net

1. 사용자 정의 함수 Comp 만들어 sort()에 사용

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool Comp(pair<int, int> p1, pair<int, int> p2) 
{
    if (p1.second < p2.second)
        return true;
    else if (p1.second == p2.second)
    {
        if (p1.first < p2.first)
            return true;
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n, x, y;

    cin >> n;

    vector<pair<int, int>> v;

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

    sort(v.begin(), v.end(), Comp);

    for (int i = 0; i < n; i++)
    {

        cout << v[i].first << ' ' << v[i].second << '\n';
    }
}

2. y, x로 push_back

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

    int n, x, y;

    cin >> n;

    vector<pair<int, int>> v;

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

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

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

}