WantAirpod

Pair

bool cmp 함수가 가장 중요하다.

bool cmp(pair<int, int> a, pair<int, int> b)
{
	if (a.first < b.first)
		return true;

	else if (a.first == b.first)
	{
		if (a.second < b.second)
		{
			return true;
		}
	}
	return false;
}

• true이면 조건문그대로 정렬 하는 것
• false이면 swap 해주는 것 
• 위의 조건문은 first기준 오름차순이며 같을 경우 second 값을 오름차순으로 결정한다..

	v.push_back({ 1,3 });
	v.push_back({ 1,4 });
	v.push_back({ 10,3 });
	v.push_back({ 12,3 });
	v.push_back({ 14,3 });
	v.push_back({ 14,2 });

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

Struct

if(a.z>b.z) 면 true라는 것은 내림차순 정렬이다.! a.z>b.z가 큰 것이 맞다!

using namespace std;
struct abc
{
	int x;
	int y;
	int z;
};
 
bool cmp(abc a, abc b)
{
	if (a.z > b.z)
		return true;
	else
		return false;
}
int main()
{
 
	vector<abc> v;
	v.push_back({ 1,2,1 });
	v.push_back({ 1,2,2 });
	v.push_back({ 1,2,3 });
	v.push_back({ 1,2,4 });

	//1,2,4->1,2,3->1,2,2->1,2,1로 정렬해라
	sort(v.begin(), v.end(), cmp); 
	

	return 0;
}

priority_queue<자료형, 구현체(container), 비교 연산자(compare 함수)> 

구현하기전 필수사항

#include <algorithm>
#include <queue>
#include <functional>

최소 힙 (= queue에 가장 top이 가장 작은 값으로 올라 오는 경우)

	priority_queue<int, vector<int>, greater<int>> min_pq; //오름차순
	min_pq.push(3);
	min_pq.push(4);
	min_pq.push(5);
	min_pq.push(6); //3,4,5,6

최대 힙 (= queue에 가장 top이 가장 큰 값으로 올라는 오는 경우)

	priority_queue<int, vector<int>, less<int >> max_pq;// 내림차순
	max_pq.push(1);
	max_pq.push(10);
	max_pq.push(100);
	max_pq.push(33); //100,33,10,1

www.acmicpc.net/problem/2110

• dfs 조합으로 풀었는데 실패가 뜸...

• 집의 좌표가 엄청 길다... 이분탐색으로 풀어야함. !!!!!!

• 간격 표

  • low는 간격 1, high는 간격 9 (사실상 최대 간격은 9-1=8이다.)
  • mid는 간격 조절 ex) mid =5 이면 cnt가 2다 (집간의 간격을 5로 두면 공유기를 설치 할 수 있는 갯수는 2개다.)
    • mid 간격 조절을 다시한다.(1) 간격이 너무 커서 공유기 설치 갯수가 2개 밖에 안나오니깐 간격을 줄인다.
      • right = mid -1;
    • mid 간격 조절을 다시한다.(2) 반대로 간격이 너무 좁아서 갯수가 3을 초과한다.
      • left = mid + 1;

• 공유기가 설치된 집의 간격 >= mid 이상일 경우 cnt++ 해준다
  • cnt++이 공유기의 최소갯수보다 크면 답이 될 후보이다.
• C++ 코드
  • 왜 Left가 1부터 시작인지는 모르겠음.. house[0]은 실패뜸...

#include <iostream>

#include <algorithm>

/*
5 3
1
2
8
4
9
*/
using namespace std;
int n, m;
int house[200000];
bool solution(int mid)
{
	int cnt = 1;
	int now = house[0];
	//cout << "mid:" << mid << endl;
	for (int i = 1; i < n; i++)
	{
		if (house[i] - now >= mid)
		{
			cnt++;
			now = house[i];
			//cout << "mid:" << mid << endl;
			//cout <<"now:" <<now << endl;
		}
		//cout << "cnt:" << cnt << endl;

	}
	if (cnt >= m)
		return true;
	return false;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> house[i];
	}
	sort(house, house + n);
	//for (int i = 0; i < n; i++)
	//	cout << house[i] << " ";
	//int Left = house[0];
	int Left = house[0];
	int mid;
	int right = house[n - 1] - house[0];

	int result = 0;
	//cout <<"right : " <<right << endl;
	while (Left <= right)
	{
		//cout << "Left : " << Left << endl;
		//cout << "right : " << right << endl;
		mid = (Left + right) / 2;

		if (solution(mid))
		{
			result = max(result, mid);
			Left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}

	}

	cout << result << endl;


	return 0;
}

SOL)

다익스트라 알고리즘 조건

• 모든 간선의 가중치가 양수
• 간선+ 가중치

dist배열 ( - : 2147000000) 무한대

pq

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


/*
6 9
1 2 12
1 3 4
2 1 2
2 3 5
2 5 5 
3 4 5
4 2 2
4 5 5 
6 4 5
*/
using namespace std;
struct Edge {
	int vex;
	int dis;
	Edge(int a, int b)
	{
		vex = a;
		dis = b;
	}
	bool operator<(const Edge &b) const
	{//최소힙 가장 작은 값이 상위에 있게함.
		return dis > b.dis;
	}
};
 

int main()
{ 
	priority_queue<Edge> Q;
	vector<pair<int, int>> graph[30];
	int i, n, m, a, b, c;
	cin >> n >> m;
	vector<int> dist(n + 1, 21470000);

	for (i = 1; i <= m; i++)
	{
		cin >> a >> b >> c;
		graph[a].push_back({ b,c });
	}
	Q.push(Edge(1, 0));
	dist[1] = 0;
	while (!Q.empty())
	{
		int now = Q.top().vex;
		int cost = Q.top().dis;
		Q.pop();
		if (cost > dist[now]) continue;
		for (i = 0; i < graph[now].size(); i++)
		{
			int next = graph[now][i].first;
			int nextdis = cost + graph[now][i].second;
			if (dist[next] > nextdis)
			{
				dist[next] = nextdis;
				Q.push(Edge(next, nextdis));
			}
		}


	}//end while

	for (i = 2; i <= n; i++)
	{
		if (dist[i] < 100000)
			cout << i << " : " << dist[i] << endl;
		else
			cout << i << " : " << "IMPOSSIBLE" << endl;

	}


	return 0;
} 

stringstream string(arr[i])

vector<string> info;

다음과 같이 vector에 문자가 있고 각각의 문자들을 짤라서 배열에 담기

코드

for (int i = 0; i < info.size(); i++)
	{
		stringstream ss(info[i]);
		string s;
		vector<int> v;
		while (ss >> s)
		{
        	//s는 abcd로 빈칸마다 짤라준다.
        }

소문자를 대문자로 변환

• toupper(char)

 for (i=0; i<str.size(); i++)

{

str[i]=toupper(str[i]); //소문자를 대문자로 교환.

}

 

• tolower(char)

#include <cctype>
 
char c = 'a';
 
toupper(c);    // c를 대문자로 변경한 값을 반환
tolower(c);    // c를 소문자로 변경한 값을 반환

 

위상정렬

• 일의 선후관계를 유지하면서 그래프를 짜는 알고리즘
• Degree (진입차수배열)을 만든다. 
  • 진입차수의 배열 값은 선행되는 작업의 갯수 
  • 진입차수배열 값이 0이면 선행되는 작업이 없다는 뜻
• Queue를 만들어서 진입차수가 0인 노드를 넣는다.(선행되는작업이없는노드)

dgree

즉, 일을 순서대로 지키면서 BFS를 돌리는 알고리즘이다.

#include <algorithm>
#include <queue>
#include <functional>
#include <vector>
#include <iostream>
using namespace std;
/*
6 6
1 4
5 4
4 3
2 5
2 3
6 2 
*/

int n, m, a, b, score;
int main()
{
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	
	
	vector<vector<int>>graph(n + 1, vector<int>(n + 1, 0)); 
	vector<int> degree(n + 1);
	queue<int> q;
	for (int i = 0; i < m; i++)
	{ 
		cin >> a >> b;
		graph[a][b] = 1;
		degree[b]++;
	}
	for (int i = 1; i <= n; i++)
	{
		if (degree[i] == 0)
			q.push(i);
	}
	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		cout << now << " ";
		for (int i = 1; i <= n; i++)
		{
			if (graph[now][i] == 1)
			{
				degree[i]--;
				if (degree[i] == 0)
					q.push(i);
			}

		}
	}
	return 0;
}

투포인트 알고리즘

• 이중 포문으로 O(N^2)이 아닌 1초안에 답이 나오게 하기 위한 알고리즘

예제)

풀이

• STEP1)A배열, B배열, C배열(교집합배열)을 만든다.
• STEP2)A배열 0번째, B배열 0번째 비교해서  (A[0] < B[0])이면 A 배열의 포인터를 +1 만큼 증가 시킨다. 즉 더 작은 값의 배열을 +1 증가 시킨다.
• STEP2,3)A[1] == B[0] 이면 그 값을 C[0]에 넣고 C[cnt++]해준다. 또한, A배열, B배열 포인터를 +1 만큼 증가시킨다.
• STEP4)누군가 하나의 배열이 끝나면 종료.

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

using namespace std;


int main()
{
	int n, m, i, p1 = 0, p2 = 0, p3 = 0;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	sort(a.begin(), a.end());
	cin >> m;
	vector<int> b(m), c(n + m);

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

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

	//2point
	while (p1 < n && p2 < m)
	{
		if (a[p1] == b[p2])
		{
			c[p3++] = a[p1++];
			p2++;
		}
		else if (a[p1] < b[p2])
			p1++;
		else
			p2++;

	}
	for (int i = 0; i < p3; i++)
		cout << c[i] << " " ;
	return 0;
}