코딩무식자 전공생

문제출처: https://www.acmicpc.net/problem/11652

문제

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다.

준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다.

입력

첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 <= N <= 1000000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다.

출력

첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다.

풀이

정답률이 많이 낮습니다.. 문제분류가 정렬인데 사실 정렬은 sort함수만 써도되니 그건아닌것 같고.. 아마도 가장 많이 갖고있는 수를 구하는 과정에서 어려움을 겪으셨을겁니다. 

일단 입력범위를 보니, 그리고 많이갖고있을 떄 작은 수를 출력하라는 조건에 의해  long long 형의 100만크기의 배열을 선언합시다. 그리고 sort함수로 정렬해요.(퀵정렬은 최악의 경우 O(n^2)이므로 시간초과가 날 수 있지만 sort함수의 평균적 시간복잡도는 O(nlogn)입니다. 찝찝하시면 병합정렬쓰세요! 그리고 이제 답을구하기 위해 변수를 선언합시다. cnt는 연속된 수의 개수를(주의: 0으로 초기화 할시 1 1 1 2 일때 2개가됩니다.) , max는 가장 큰 연속된 개수의 수, index는 가장 큰 연속된 개수를 가질 때 그 위치의값을 나타냅니다. 그리고, 수가 연속될 때, 연속되지 않을 떄의 2가지경우로 나누어서 숫자를 세봅시다. 일단 연속되지않으면 무조건 cnt를 1로 초기화합니다.(0으로 초기화하면 안됩니다. 위에서 얘기했듯이 1 1 1 2 일때 2개가 되죠.)연속될 시, cnt를 한칸 증가시켜주고 max값을 갱신해줍니다. 갱신해 줄 때 그 때의 index를 저장합니다.최종적으로 반복문을 마치고 card[index]가 정답이됩니다. 최종적으로 시간복잡도는 O(nlogn)+O(n)입니다. 그리고 마지막으로,, 아래 채점결과에서 볼 수 있듯이 c++의 입출력함수가 시간을 많이 잡아먹으므로 cin.tie(0); cin.sync_with_stdio(false); 선언을 생활화 합시다.

주의 할것 : 

cnt= 1로 초기화하고 조건식에서 연속되지않을 시 0이 아닌 1로 초기화하기

c++ 입출력 사용 시 개행을 '\n', 입출력 시 cin.tie(0); cin.sync_with_stdio(false); 선언 생활화하기

코드

채점결과 순서대로 각각 

개행:'\n', cin.tie(0),cin.sync_with_stdio(false)선언했을 때 : 28ms

개행:'\n'만 썼을 때 : 120ms

c++입출력사용했을 때 : 136ms

#include<iostream>
#include<algorithm>
using namespace std;
long long card[1000000];
int main()
{
	int n;
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> card[i];
	sort(card, card + n);
	//세기위한 변수, 갯수를 비교하기위한변수
	int cnt = 1, max = 0, index = 0;
	for (int i = 0; i < n - 1; i++)
	{
		if (card[i] == card[i + 1])
		{
			cnt++;
			if (cnt > max)
			{
				max = cnt;
				index = i;
			}
		}
		else
			//0이아닌 1로초기화!
			cnt = 1;
	}
	cout << card[index] << '\n';
	
}

결과

문제출처: https://www.acmicpc.net/problem/2399

문제

수직선에 n개의 점이 찍혀 있다. 각각의 점의 x좌표가 주어졌을 때, n2개의 모든 쌍에 대해서 거리를 더한 값을 구하는 프로그램을 작성하시오.

즉, 모든 i, j에 대해서 |x[i] - x[j]|의 합을 구하는 것이다.

입력

첫째 줄에 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 x[1], x[2], x[3], …, x[n]이 주어진다. 각각은 0 이상 1,000,000,000 이하의 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이

이 문제로 효율적인 시간복잡도를 갖는 알고리즘의 설계의 중요성을 알 수 있습니다. 이 문제를 각각 O(n^2), 0(n^2/2), O(nlogn)으로 풀 수 있는데 엄밀히말해서 입력값이 1만이므로 최악의 경우 1억번의 연산을 해야하므로 O(nlogn)으로 풀어야만합니다. 하지만 이 문제는 O(n^2)의 연산풀이도 정답이되는것 같습니다.

O(n^2) : 입력한 수들을 모두 각각 비교하면서 총합을 구합니다. 쓸모없는 연산을 하는 단점이있습니다.(1,2,3,4,5일때 (1.1),(2,2),(3,3),(4,4),(5,5) )

O(n^2/2) : O(n^2)의 방식에서 언급한 쓸모없는연산(본인과 본인사이의 거리)을 하지않고 , 두번더하는연산((1,2),(2,1),(4,5),(5,4)...)을 한번으로줄입니다. 구해진 ans*2가 답입니다. 

O(n^2)의 방식은 n이 5일때 총 5*5=25번연산, O(n^2/2)의 방식은 입력값끼리 한번씩만 연산하므로(O(n^2)의 절반만 계산) 약 O(n^2/2)입니다.

그런데 시간복잡도 상 O(n^2)와 O(n^2/2)는 둘다 O(n^2)로, 여전히 시간초과가 날 우려가 있습니다.

더 좋은방법은 없을까요? 바로 O(nlogn)방법이있습니다. 

10,1,3,7 이있다고칠때, 가장 작은값부터 오름차순으로 좌표값의차이를 비교해가며  연산을 하기위해 1,3,7,10으로 정렬합니다.

(정렬하지않으면 연산식을 같게해도 답이다릅니다. ex) 10,3,1,7-> 94, 1,7,10,3-> 102

사실상 정렬하지않고 연산한 방식을 

여기서, 규칙을 발견할 수 있습니다. 1과 3의 간격 2, 1과 7 의 간격 6, 1과 10의 간격 9, 3과 7의 간격 4, 3과 10의간격 7, 7과 10의 간격3, 이값들을 모두더하고 *2를하면 그게답입니다. 즉,  1,3,7,10일 때 1에서 모든숫자간의 간격 + 3에서 남은 모든숫자의간격(1제외)+ 7과 남은 모든숫자의간격을 구하는겁니다.

여기서 O(n^2/2)와 O(nlogn)의 연산의 차이는 후자의 경우 각 숫자의 간격을 단 한번만 구하고 그 값이 간격을 계산할 때 나오는 경우만큼 곱해주는것입니다.

전자의 경우 10,1,3,7 일때 (1,2),(1,3),(1,4),(2,3),(2,4),(3,4)의 간격을구하죠. 그러나 후자는 3->3->1번씩 구하는게아니라 1->1->1번씩구하고 그 간격의 값들을 곱해주고 더해나갑니다. 위의 예로는 (1.2),(2,3),(3,4) 이렇게 딱 3번만연산합니다. 반복문으로 구해지는 i번째의 인덱스일때 간격 6=(1,3)+(3,7), 16=(1,10)+(3,10), 9=(1,7)+(7,10))

결론적으로 n이4일때 각 시간복잡도의 연산횟수는 16, 6, 3 이렇게되겠습니다.

코드

0~21행: O(nlogn), 38행(n^2/2), 37행(n^2)

#pragma warning(disable:4996)
#include<iostream>
#include<algorithm>
using namespace std;
int arr[10001];
int main()
{
	int n;
	scanf("%d", &n);
	long long ans = 0;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	sort(arr, arr + n);
	for (int i = 1; i < n; i++)
	{
		ans += (arr[i] - arr[i - 1]) * i * (n - i);
	}
	printf("%lld\n", ans * 2);
}

//#include<iostream>
//using namespace std;
//int arr[10001];
//int main()
//{
//	int n;
//	cin >> n;
//	long long ans = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> arr[i];
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = i + 1; j <= n; j++)
//		for(int j=1;j<=n;j++)///////
//		{
//			ans += abs(arr[i] - arr[j]);
//		}
//	}
//	cout << ans * 2 << endl;
//}

결과

문제출처: https://www.acmicpc.net/problem/1822

   문제

//#include<iostream>
//#include<set>
//using namespace std;
//int main()
//{
//	int a, b;
//	cin >> a >> b;
//	set<int>s;
//	set<int>::iterator it;
//	int x;
//	for (int i = 0; i < a; i++)
//	{
//		cin >> x;
//		s.insert(x);
//	}
//	for (int i = 0; i < b; i++)
//	{
//		cin >> x;
//		it = s.find(x);
//		if (it == s.end())
//			continue;
//		else
//			s.erase(x);
//	}
//	cout << s.size() << endl;
//	for (it = s.begin(); it != s.end(); it++)
//		cout<< *it<<" ";
//	cout << endl;
//}

#include<iostream>
#include<vector>
using namespace std;
int a[500001], b[500001], sorted[500001];
void merge(int a[], int start, int end);
void merge_sort(int a[], int start, int middle, int end);
int main()
{
	int n,m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < m; i++)
		cin >> b[i];
	merge(a, 0, n - 1);
	merge(b, 0, m - 1);
	vector<int>v;
	int a_start = 0;
	int b_start = 0;
	while (a_start < n && b_start < m)
	{
		if (a[a_start] < b[b_start])
		{
			v.push_back(a[a_start]);
			a_start++;
		}
		else if (a[a_start] > b[b_start])
			b_start++;
		else
		{
			a_start++, b_start++;
		}
	}
	if (a_start < n)
	{
		for (int i = a_start; i < n; i++)
			v.push_back(a[i]);
	}
	cout << v.size() << endl;
	for (int i = 0; i < v.size(); i++)
		cout << v[i] << " ";
	cout << endl;

}
void merge(int a[], int start, int end)
{
	if (start < end)
	{
		int middle = (start + end) / 2;
		merge(a, start, middle);
		merge(a, middle + 1, end);
		merge_sort(a, start, middle, end);
	}
}
void merge_sort(int a[], int start, int middle, int end)
{
	int i = start;
	int j = middle + 1;
	int k = start;
	while (i <= middle && j <= end)
	{
		if (a[i] <= a[j])
			sorted[k++] = a[i++];
		else sorted[k++] = a[j++];
	}
	if (i > middle)
	{
		for (int l = j; l <= end; l++)
			sorted[k++] = a[l];
	}
	else
		for (int l = i; l <= middle; l++)
			sorted[k++] = a[l];
	for (int l = start; l <= end; l++)
		a[l] = sorted[l];
}

문제출처: https://www.acmicpc.net/problem/1269

입력받는 수의 갯수가 최대 20만개이므로 정렬 연산 시 최악의 경우 4억번(약 4초) 연산을 할 수 있으므로

O(nlogn)의 효율적인 알고리즘을 써야합니다. 퀵 소트는 최악의 경우 O(n^2)이므로 통과가 안 될 수 있음을 유념합니다.

정렬 알고리즘 시간복잡도 및 분석: https://jow1025.tistory.com/20

문제

자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.

예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때,  A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.

입력

첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.

출력

첫째 줄에 대칭 차집합의 원소의 개수를 출력한다.

풀이

1. 차집합을 계산하기 위해 두 집합을 오름차순 정렬합니다.

( 이 때 시간복잡도가 O(nlogn)으로 안정적인 병합정렬을 사용합니다.

2. a집합과 b집합의 차집합 후 원소의 갯수는 각각 a와 b의 집합의 총 원소의 갯수에서 겹치는 수를 제외한 나머지 원소의 갯수입니다.(정답)

3. 병합정렬 후 A집합과 B집합에서 겹치는 원소의 개수를 찾아낸 뒤 정답을 출력합니다.

코드

#include<iostream>
using namespace std;
int a[200001], b[200001];
using namespace std;
void merge(int a[], int start, int end);
void merge_sort(int a[], int start, int middle, int end);
int sorted[200001];
int main()
{
	int n, m;
	cin >> n >> m;
	cin.tie(0);//시간을 줄이기위해 선언
	cin.sync_with_stdio(false);//시간을 줄이기위해 선언
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < m; i++)
		cin >> b[i];
	merge(a, 0, n - 1);
	merge(b, 0, m - 1);
	//정렬되어있는 상태
	int a_start = 0, b_start = 0;
	int cnt = 0;
	//a-b차집합의 원소갯수: a의전체원소 수 - 겹치는 수의 갯수
	//b-a차집합의 원소갯수: b의전체원소 수 -겹치는 수의 갯수
	while (a_start < n && b_start < m)
	{
		if (a[a_start] == b[b_start])
			a_start++, b_start++, cnt++;
		else if (a[a_start] < b[b_start])
			a_start++;
		else
			b_start++;
	}
	cout << (n - cnt) + (m - cnt) << endl;
}
void merge(int a[], int start, int end)
{
	if (start < end)
	{
		int middle = (start + end) / 2;
		merge(a, start, middle);
		merge(a, middle + 1, end);
		merge_sort(a, start, middle, end);
	}
}
void merge_sort(int a[], int start, int middle, int end)
{
	int i = start;
	int j = middle + 1;
	int k = start;
	while (i <= middle && j <= end)
	{
		if (a[i] <= a[j])
			sorted[k++] = a[i++];
		else
			sorted[k++] = a[j++];
	}
	if (i > middle) {
		for (int l = j; l <= end; l++)
			sorted[k++] = a[l];
	}
	else
	{
		for (int l = i; l <= middle; l++)
			sorted[k++] = a[l];
	}
	for (int l = start; l <= end; l++)
		a[l] = sorted[l];
}

결과