2021년 2분기

알고리즘/1주일 1문제

2021년 2분기

tsyang 2021. 10. 22. 00:12

백준 9248 - Suffix Array (문자열 - 맨버 마이어스 알고리즘)

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

//https://www.acmicpc.net/problem/9248 - Suffix Array
//종만북보고 재현함

using namespace std;

//#define DEBUG

#ifdef DEBUG
void DebugSuffixArr(const vector<int> & suffixArr, const string & s, int t = -1)
{
	cout << "===========SUFFIX ARRAY===============" << endl;
	if (t != -1)
		cout << "t : " << t << endl;
	for (int i = 0; i < suffixArr.size(); ++i)
	{
		cout << s.substr(suffixArr[i]) << endl;
	}
	cout << "======================================" << endl << endl;;
}

void DebugSuffixArr(const vector<int> & suffixArr, const string & s,  const vector<int> & group, int t = -1)
{
	cout << "===========SUFFIX ARRAY===============" << endl;
	if (t != -1)
		cout << "t : " << t << endl;
	cout << "-------------------------------------" << endl;
	cout << s.substr(suffixArr[0]) << endl;
	for (int i = 1; i < suffixArr.size(); ++i)
	{
		if(group[suffixArr[i-1]] != group[suffixArr[i]])
			cout << "-------------------------------------" << endl;
		cout << s.substr(suffixArr[i]) << endl;
	}
	cout << "======================================" << endl << endl;
}
#endif


//비교용 클래스
class Compararer
{
private:
	const vector<int>& group;
	int t;

public :
	Compararer(const vector<int> & group, int t) : group(group), t(t) {}

	bool operator() (int suffixA, int suffixB)
	{
		if (group[suffixA] != group[suffixB])
			return group[suffixA] < group[suffixB];
		else
			return group[suffixA + t] < group[suffixB + t];
		//return group[suffixA] == group[suffixB] ? 
		//	group[suffixA + t] < group[suffixB + t] : group[suffixA] < group[suffixB];
	}
};

vector<int> getSuffixArray(const string & s)
{
	int len = s.size();
	vector<int> suffixArr(len);
	for (int i = 0; i < len; ++i)
		suffixArr[i] = i;

	int t = 1;
	vector<int> group(len + 1);
	
	for (int i = 0; i < len; ++i)
		group[i] = s[i];
	group[len] = -1;

	while (true)
	{
		Compararer comparer(group, t);
		sort(suffixArr.begin(), suffixArr.end(), comparer);

		t *= 2;
		if (t >= len)
			break;

		vector<int> newGroup(len + 1);
		newGroup[suffixArr[0]] = 0;
		newGroup[len] = -1;
		for (int i = 1; i < len; ++i)
		{
			//비교자는 그룹을 비교하므로.. 이게 참이면 i의 그룹이 더 번호가 크다는 뜻.
			if(comparer(suffixArr[i-1], suffixArr[i]))
			{
				newGroup[suffixArr[i]] = newGroup[suffixArr[i - 1]] + 1;
			}
			else
			{
				newGroup[suffixArr[i]] = newGroup[suffixArr[i - 1]];
			}
		}
		group = newGroup;

		//그룹이 다 쪼개져서 더이상 비교 무의미
		if (group[suffixArr[len - 1]] == len - 1)
			break;

#ifdef DEBUG
		DebugSuffixArr(suffixArr, s, group, t);
#endif
	}

	return suffixArr;
}

vector<int> getLCP(const vector<int> & suffixArr, const string & S)
{
	int n = suffixArr.size();
	vector<int> lcp(n);
	vector<int> rank(n);

	int len = 0;

	for (int i = 0; i < n; i++)
		rank[suffixArr[i]] = i;
	
	//기본적으로 문자열이 banana라면 banana , anana, nana, ana 이렇게 하나씩 이동하며 검사한다고 보면 된다.
	for (int i = 0; i < n; i++)
	{
		int k = rank[i];	// step 1) substr(i..) 가 접미사 배열의 몇번째인지를 찾아서
		if (k > 0)
		{
			int j = suffixArr[k - 1]; // step 2) 그놈의 이전 접미사를 찾는다. (substr(j...))

			while (S[j + len] == S[i + len])	//step 3) 몇 개가 겹치는지 본다.
				len++;

			lcp[k] = len;	//step 4) 쓴다

			if (len > 0)	//step 5) 이거는 비교했던 접미사의 맨 처음글자를 지워준다고 생각하면 된다. 
				len--;
		}
	}

	return lcp;
}

int main()
{
	string S;
	cin >> S;
	int t = 1;
	
	auto suffixArr = getSuffixArray(S);
	auto lcp = getLCP(suffixArr, S);

	for (int i = 0; i < suffixArr.size(); ++i)
	{
		cout << suffixArr[i]+1 << ' ';
	}
	cout << endl;
	cout << "x ";
	for (int i = 1; i < lcp.size(); ++i)
	{
		cout << lcp[i] << ' ';
	}	
	return 0;
}

백준 3665 - 최종 순위 (위상 정렬)

//백준 3665번 : 최종 순위 (https://www.acmicpc.net/problem/3665)
//위상 정렬

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

using namespace std;

constexpr int MAX = 501;

int V[MAX][MAX]{ 0 };
int indegree[MAX]{ 0 }; //그래프에서 화살표 꽂히는 갯수

int numTest, N, M;

void ReadDefaultOrder();
void ReadAndSwap();
void CalcIndegree();
void Old_PrintAnswer();
void PrintAnswer();
void Reset();

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

	cin >> numTest;
	
	for (int cntTest = 0; cntTest < numTest; ++cntTest)
	{		
		ReadDefaultOrder();
		ReadAndSwap();
		CalcIndegree();
		PrintAnswer();
		Reset();
	}

	return 0;
}


//보니까 이번 문제는 무조건 indegree가 0,1,2,3,..,N-1 이렇게 순차적으로 나옴, 이걸 이용
void PrintAnswer()
{
	vector<int> newOrder;
	newOrder.resize(N);

	for (int num = 1; num <= N; ++num)
	{
		int deg = indegree[num];
		if (newOrder[deg] == 0)
			newOrder[deg] = num;

		//indegree가 같은 애가 있다? => 잘못됨
		else
		{
			cout << "IMPOSSIBLE" << endl;
			return;
		}
	}

	for (int i = 0; i < newOrder.size(); ++i)
		cout << newOrder[i] << ' ';
	cout << endl;
}

void Reset()
{
	for (int i = 0; i < MAX; ++i)
		for (int j = 0; j < MAX; ++j)
			V[i][j] = 0;
	for (int i = 0; i < MAX; ++i)
		indegree[i] = 0;
}

void CalcIndegree()
{
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
		{
			if (V[i][j] == 1)
			{
				indegree[j]++;
			}
		}
}

void ReadDefaultOrder()
{
	cin >> N;

	vector<int> prevOrder(N);
	for (int i = 0; i < N; ++i)
		cin >> prevOrder[i];

	for (int i = 0; i < N; ++i)
		for (int j = i + 1; j < N; ++j)
			V[prevOrder[i]][prevOrder[j]] = 1; // i to j 연결
}

void ReadAndSwap()
{
	cin >> M;
	for (int cntM = 0; cntM < M; ++cntM)
	{
		int n1, n2;
		cin >> n1 >> n2;
		swap(V[n1][n2], V[n2][n1]);	//그래프 간선 방향 바꿔줌.
	}
}

//전형적인 위상정렬
void Old_PrintAnswer()
{
	vector<int> newOrder;
	for (int n = 0; n < N; ++n)
	{
		int target = -1;

		//indegree 0인애를 찾아줌
		for (int i = 1; i <= N; ++i)
		{
			if (indegree[i] == 0)
			{
				target = i;
				indegree[i]--; //이제 안쓰는 노드라는 뜻
				break;
			}
		}

		//없다? 그럼 사이클생긴거
		if (target == -1)
		{
			cout << "IMPOSSIBLE" << endl;
			return;
		}

		newOrder.push_back(target);
		for (int j = 1; j <= N; ++j)
		{
			//간선 없애줌
			if (V[target][j] == 1)
			{
				V[target][j] = 0;
				indegree[j]--;
			}
		}
	}

	for (int i = 0; i < newOrder.size(); ++i)
		cout << newOrder[i] << ' ';
	cout << endl;
}

리트코드 133 - Clone Graph (그래프)

class Solution {
public:
	Node* cloneGraph(Node* node) {
		if (node == nullptr)
			return nullptr;

		queue<Node*> nodeQueue;
		unordered_map<Node*, Node*> nodeMap;

		nodeQueue.push(node);
		nodeMap.insert({ node, new Node(node->val) });

		while (false == nodeQueue.empty())
		{
			Node * curNode = nodeQueue.front();
			nodeQueue.pop();

			for (const auto neighbor : curNode->neighbors)
			{
				//맵에 없음: 노드를 큐에 넣는다, 맵에도 추가한다.
				if (nodeMap.find(neighbor) == nodeMap.end()) 
				{
					nodeQueue.push(neighbor);

					nodeMap[neighbor] = new Node(neighbor->val);
					//nodeMap.insert({ neighbor, new Node(neighbor->val) }); // 왜 안 됨????????????????????????
				}
				nodeMap[curNode]->neighbors.push_back(nodeMap[neighbor]);
			}
		}

		return nodeMap[node];
	}
};

백준 1613 - 역사 (최단경로 - 플로이드 와샬)

//https://www.acmicpc.net/problem/1613 
//풀이 : 위상정렬 알고리즘 응용..? (O(V^3))
//비고 : 원래는 플로이드 와샬 알고리즘으로 풀어야함

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_set>

using namespace std;

short outDegree[401] = { 0, };
unordered_set<int> nextEvents[401];
vector<int> prevEvents[401];
queue<int> zeroOutDegrees;

int n, k, s;

void CaclGraph();
void PushEventsWithZeroOutDegree();
void PropagateNextEvents(int curEvent);
void DecreaseOutDegreeOfPrevEvents(int curEvent);
void OptimizeIO();
void ReadAndInitEvents();
void AnswerTheQuestions();

int main()
{
	OptimizeIO();
	ReadAndInitEvents();
	CaclGraph();
	AnswerTheQuestions();

	return 0;
}

//위상정렬이랑 비슷한데.. inDegree가 아닌 outDegree를 이용한다.
void CaclGraph()
{
	PushEventsWithZeroOutDegree();

	while (false == zeroOutDegrees.empty())
	{
		int curEvent = zeroOutDegrees.front();
		zeroOutDegrees.pop();

		PropagateNextEvents(curEvent);
		DecreaseOutDegreeOfPrevEvents(curEvent);
	}
}

void PushEventsWithZeroOutDegree()
{
	for (int i = 1; i <= n; ++i)
		if (outDegree[i] == 0)
			zeroOutDegrees.push(i);
}

void PropagateNextEvents(int curEvent)
{
	if (nextEvents[curEvent].bucket_count() == 0)
		return;

	auto nextEventIter = nextEvents[curEvent].begin();
	for (; nextEventIter != nextEvents[curEvent].end(); ++nextEventIter)
	{
		for (int i = 0; i < prevEvents[curEvent].size(); ++i)
		{
			int prev = prevEvents[curEvent][i];
			nextEvents[prev].insert(*nextEventIter);
		}
	}
}

void DecreaseOutDegreeOfPrevEvents(int curEvent)
{
	for (int i = 0; i < prevEvents[curEvent].size(); ++i)
	{
		int prevEvent = prevEvents[curEvent][i];
		--outDegree[prevEvent];
		if (outDegree[prevEvent] == 0)
			zeroOutDegrees.push(prevEvent);
	}
}

void OptimizeIO()
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);
}

void ReadAndInitEvents()
{
	cin >> n >> k;
	for (int i = 0; i < k; ++i)
	{
		int pastEvent, futureEvent;
		cin >> pastEvent >> futureEvent;

		nextEvents[pastEvent].insert(futureEvent);
		prevEvents[futureEvent].push_back(pastEvent);

		++outDegree[pastEvent];
	}
}

void AnswerTheQuestions()
{
	cin >> s;
	for (int i = 0; i < s; ++i)
	{
		int event1, event2;
		cin >> event1 >> event2;

		if (nextEvents[event1].find(event2) != nextEvents[event1].end()) //event1이 event2보다 먼저 일어났다.
			cout << -1 << "\n";
		else if (nextEvents[event2].find(event1) != nextEvents[event2].end()) //event2가 event1보다 먼저 일어났다.
			cout << 1 << "\n";
		else
			cout << 0 << "\n";
	}
}

백준 1865 - 웜홀 (최단경로 - 벨먼 포드)

//https://www.acmicpc.net/problem/1865
//벨먼 포드 알고리즘

#include <iostream>
#include <vector>

using namespace std;
constexpr int INF = 987654321;

struct Edge
{
	int u, v, t;

	Edge(int u,int v, int t) : u(u), v(v), t(t) 
	{}
};

class BellmanFordSolver
{
public:
	void Answer()
	{
		read();
		if (Solve())
			cout << "YES\n";
		else
			cout << "NO\n";
	}

private:
	void read()
	{
		cin >> numNodes >> numRoads >> numWormholes;

		dist.resize(numNodes, INF);
		dist[0] = 0;	//출발 지점은 소요 시간이 0임
		edges.reserve(numRoads + numWormholes);
		//도로를 받음
		for (int i = 0; i < numRoads; ++i)
		{
			int S, E, T;
			cin >> S >> E >> T;
			edges.emplace_back(S - 1, E - 1, T);
		}
		for (int i = 0; i < numWormholes; ++i)
		{
			int S, E, T;
			cin >> S >> E >> T;
			edges.emplace_back(S - 1, E - 1, -T);
		}
	}

	bool Solve()
	{
		for (int i = 0; i < numNodes - 1; ++i)
			if (TryRelaxEdges() == false)
				return false;	//완화된 간선이 없다 => 음의 사이클 없음으로 최단경로 완성
		
		return TryRelaxEdges();	// 간선 완화를 다 했는데 또 완화가 된다 => 음의 사이클이 있다.
	}

	bool TryRelaxEdges()
	{
		int relaxed = false;
		for (auto e : edges)
			if (TryRelax(e))
				relaxed = true;
		return relaxed;
	}

	bool TryRelax(const Edge & edge)
	{
		int relaxed = false;
		int newDist = dist[edge.u] + edge.t;
		if (dist[edge.v] > newDist)
		{
			dist[edge.v] = newDist;
			relaxed = true;
		}

		//도로인 경우 양방향이므로
		if (edge.t > 0)
		{
			newDist = dist[edge.v] + edge.t;
			if (dist[edge.u] > newDist)
			{
				dist[edge.u] = newDist;
				relaxed = true;
			}
		}
		return relaxed;
	}

private:
	int numNodes, numRoads, numWormholes;
	vector<Edge> edges;
	vector<int> dist;
};

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

	int numTestCase;
	cin >> numTestCase;

	for (int i = 0; i < numTestCase; ++i)
	{
		BellmanFordSolver solver;
		solver.Answer();
	}
	return 0;
}

백준 1708 - 볼록 껍질 (기하, Convex hull)

//https://www.acmicpc.net/problem/1708
//Convex Hull 알고리즘 (그라함 스캔)

/*
 *	1. 가장 아래의 점을 기준점으로 잡는다.
 *	2. 기준점으로부터 다른 점들을 +x 축과의 각도순으로 정렬한다. (반시계방향으로 정렬)
 *  3. 스택에 1,2번째 점을 넣는다. next는 정렬한 점의 3번째를 가리킨다.
 *  4. 스택에서 점 두개를 꺼낸다, 뽑은 순서대로 second, first라고 부른다. (first 는 pop 하지 않는다.)
 *  5. first-second와 second-next의 각도가 반시계 방향인지 (좌회전하는지) 체크
 *  5-1. 좌회전 한다면 convex hull이 될 후보이다. second와 next를 스택에 넣는다. 그리고 next++
 *  5-2. 우회전한다면 스택에서 하나를 다시 pop한다음 second라 부른다. 5번을 다시 수행한다.
 *  6. 더 이상 next가 가리킬게 없으면 끝났다. 스택의 점들이 convex hull이다.
 */

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

using namespace std;

constexpr int inf = 100000;
struct point;
class sort_point_ccw;
void read();
bool is_ccw(const point& first, const point& second, const point& next);
long long external_product(const point& a, const point& b);
point find_pivot();
void grahamScan();

struct point
{
	int x, y;

	point(const int x, const int y) : x(x), y(y)
	{
	}

	point()
	{
		x = 0, y = 0;
	}
};

class sort_point_ccw
{
public :
	sort_point_ccw(point pivot) : pivot_(pivot)	{	}

	bool operator()(point a, point b)
	{
		bool result;
		const point vector1(a.x - pivot_.x, a.y - pivot_.y);
		const point vector2(b.x - pivot_.x, b.y - pivot_.y);
		auto product = external_product(vector1, vector2);
		if(product == 0)
		{
			return a.y != b.y ? a.y < b.y : a.x < b.x;
		}
		else
		{
			return product > 0;
		}
	}

private :
	point pivot_;
};

int N;
vector<point> points;
stack<point> candidates;

int main()
{

	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	read();
	auto pivot = find_pivot();
	sort_point_ccw ccwCmp(pivot);
	sort(points.begin(), points.end(), ccwCmp);

	grahamScan();

	cout << candidates.size();

	return 0;
}

void grahamScan()
{
	int nextIdx = 0;
	candidates.emplace(points[0]);
	candidates.emplace(points[1]);
	nextIdx = 2;

	while (nextIdx < points.size())
	{
		const point& next = points[nextIdx];
		if (candidates.size() >= 2)
		{
			const point& second = candidates.top();
			candidates.pop();
			const point& first = candidates.top();

			if (is_ccw(first, second, next))
			{
				candidates.push(second);
				candidates.push(next);
				++nextIdx;
			}
		}
		else
		{
			candidates.push(next);
			++nextIdx;
		}
	}
}

void read()
{
	cin >> N;
	points.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		int x, y;
		cin >> x >> y;
		points.emplace_back(x, y);
	}
}

point find_pivot()
{
	if (points.empty())
		return point(0, 0);

	point minPoint = points[0];
	for (const auto point : points)
	{
		if (point.y < minPoint.y ||
			(point.y == minPoint.y && point.x < minPoint.x))
		{
			minPoint = point;
		}
	}
	return minPoint;
}

long long external_product(const point& a, const point& b)
{
	return static_cast<long long>(a.x) * b.y - static_cast<long long>(a.y) * b.x;
}

//first -> second , second -> next가 반시계 방향인지를 반환한다.
//벡터의 외적으로 판단.. (https://bowbowbow.tistory.com/14)
bool is_ccw(const point& first, const point& second, const point& next)
{
	const point vector1(second.x - first.x, second.y - first.y);
	const point vector2(next.x - second.x, next.y - second.y);
	return external_product(vector1, vector2) > 0;
}

백준 6086 - 최대 유량 (네트워크 유량)

//https://www.acmicpc.net/problem/6086 (최대 유량)
//포드 풀커슨 BFS 알고리즘 (= 에드몬드-카프 알고리즘)

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;
const int INF = 987654321;

class network_flow
{
public:
	network_flow()
	{
		init();
	}
	void solve()
	{
		read_input();
		cout << get_max_flow() << endl;
	}
private:
	void init()
	{
		memset(capacity_, 0, sizeof(capacity_));
		memset(flow_, 0, sizeof(flow_));
	}

	void read_input()
	{
		int N;
		cin >> N;
		for (int i = 0; i < N; ++i)
		{
			char pipe1, pipe2;
			int capacity;
			cin >> pipe1 >> pipe2 >> capacity;
			int here, there;
			here = alphabetToIndex(pipe1);
			there = alphabetToIndex(pipe2);
			capacity_[here][there] += capacity;
			capacity_[there][here] += capacity;
		}
	}

	int alphabetToIndex(char alphabat)
	{
		if (alphabat >= 'a')
			return alphabat - 'a' + 26;
		else
			return alphabat - 'A';
	}
	

	int get_max_flow()
	{
		int max_flow = 0;

		while (true)
		{
			vector<int> parent(get_available_path());
			if (parent[GOAL] == NONE)
				break;

			int amount = INF;
			for (int p = GOAL; p != START; p = parent[p])
			{
				amount = min(capacity_[parent[p]][p] - flow_[parent[p]][p], amount);
			}

			for (int p = GOAL; p != START; p = parent[p])
			{
				flow_[parent[p]][p] += amount;
				flow_[p][parent[p]] -= amount;
			}
			max_flow += amount;
		}

		return max_flow;
	}

	vector<int> get_available_path()
	{
		vector<int> parent(MAX_PIPE, NONE);
		queue<int> q;

		parent[START] = START;
		q.push(START);
		while (false == q.empty() && parent[GOAL] == NONE)
		{
			int here = q.front(); q.pop();
			for (int there = 0; there < MAX_PIPE; ++there)
			{
				if (capacity_[here][there] - flow_[here][there] > 0 && parent[there] == NONE)
				{
					parent[there] = here;
					q.push(there);
				}
			}
		}
		return parent;
	}

private:
	const static int MAX_PIPE = 52; // START to GOAL
	const static int START = 0, GOAL = 25, NONE = -1;
	int capacity_[MAX_PIPE][MAX_PIPE], flow_[MAX_PIPE][MAX_PIPE];
};

int main()
{
	network_flow nf;
	nf.solve();

	return 0;
}

백준 2580 - 스도쿠 (백트래킹)

//https://www.acmicpc.net/problem/2580 (스도쿠)
//백트래킹

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;
const int INF = 987654321;

void init();
void read_board();
void backtracking(int cell_idx);
void print_board();

struct point
{
	point() { x = 0, y = 0; }
	point(int x, int y) : x(x), y(y) {}

	int x, y;
};

vector<point> emptyPoints;
int board[9][9];
bool has_found_answer = false;

//row, col, square 검사를 빠르게하기위해 해당 row,col,square에 값이 있는지를 캐싱
//예 : (row[1][3] == true) 이면 1번째 row에 값4가(=3+1) 이미 들어있다는 뜻
bool row[9][9];
bool col[9][9];
bool square[3][3][9];

int main()
{
	init();
	read_board();
	backtracking(0);
	print_board();
	return 0;
}

void print_board()
{
	for (int i = 0; i < 9; ++i)
	{
		for (int j = 0; j < 9; ++j)
		{
			cout << board[i][j] << ' ';
		}
		cout << "\n";
	}

}

void set_cache(int y, int x, int val, bool cache_val)
{
	if (val <= 0)
		return;
	row[y][val - 1] = cache_val;
	col[x][val - 1] = cache_val;
	square[(y / 3)][(x / 3)][val - 1] = cache_val;
}

void read_board()
{
	for (int i = 0; i < 9; ++i)
		for (int j = 0; j < 9; ++j)
		{
			cin >> board[i][j];

			set_cache(i, j, board[i][j], true);

			if (board[i][j] == 0)
				emptyPoints.emplace_back(j, i);
		}
}

bool can_place_val(const point & p, int val)
{
	if (row[p.y][val - 1] == true)
		return false;
	else if (col[p.x][val - 1] == true)
		return false;
	else if (square[(p.y / 3)][(p.x / 3)][val - 1] == true)
		return false;

	return true;
}

void place_val(const point& p, int val)
{
	if (has_found_answer)
		return;

	if (board[p.y][p.x] != 0)
	{
		set_cache(p.y, p.x, board[p.y][p.x], false);
	}
	
	set_cache(p.y, p.x, val, true);
	board[p.y][p.x] = val;
}

void remove_val(const point& p)
{
	place_val(p, 0);
}

void backtracking(int cell_idx)
{
	if (cell_idx >= emptyPoints.size())
		has_found_answer = true;

	if (has_found_answer)
		return;

	const point& p = emptyPoints[cell_idx];
	for (int val = 1; val <= 9; ++val)
	{
		if (can_place_val(p, val))
		{
			place_val(p, val);
			backtracking(cell_idx + 1);
		}
		else
			continue;
	}

	remove_val(p);
}

void init()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);
	memset(board, 0, sizeof(board));
	memset(row, false, sizeof(row));
	memset(col, false, sizeof(col));
	memset(square, false, sizeof(square));
}

백준 2188 - 축사 배정 (이분 매칭)

// https://www.acmicpc.net/problem/2188 (축사 배정)
// 이분 매칭 알고리즘

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

void init();
void read();
void bipartite_match();
bool try_match(int a, std::vector<bool> & visited_b);


const int MAX = 201;
int N, M;
bool adj[MAX][MAX];
vector<int> aMatch(MAX, -1), bMatch(MAX, -1);
int answer = 0;

int main()
{
	init();
	read();
	bipartite_match();
	cout << answer;
	return 0;
}

void bipartite_match()
{
	for (int a = 0; a < N; ++a)
	{
		vector<bool> visited_b(MAX, false);
		if (try_match(a, visited_b))
		{
			++answer;
		}
	}
}

bool try_match(int a, vector<bool> & visited_b)
{
	for (int b = 1; b <= M; ++b)
	{
		if (visited_b[b] == false && adj[a][b])
		{
			visited_b[b] = true;
			if (bMatch[b] == -1 || try_match(bMatch[b], visited_b))
			{
				aMatch[a] = b;
				bMatch[b] = a;
				return true;
			}
		}
	}
	
	return false;
}

void init()
{
	memset(adj, false, sizeof(adj));
}


void read()
{
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	{
		int cnt;
		cin >> cnt;
		while (cnt > 0)
		{
			int b;
			cin >> b;
			adj[i][b]  = true;
			cnt--;
		}
	}
}

백준 1422 - 숫자의 신

// https://www.acmicpc.net/problem/1422 (숫자의 신)

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

using namespace std;

int K, N;
vector<int> nums;
int max_num = 0;

void read()
{
	cin >> K >> N;
	for (int i = 0; i < K; ++i)
	{
		int num;
		cin >> num;
		nums.emplace_back(num);
		if (max_num < num)
			max_num = num;
	}
}

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

bool cmp(int a, int b)
{
	return compare(to_string(a), to_string(b));
}

void print_answer()
{
	string answer;
	for (auto num : nums)
	{
		string str_num = to_string(num);
		answer.append(str_num);
		if (num == max_num)
		{
			for (int i = 0; i < N - K; ++i)
				answer.append(str_num);
			max_num = -1; //최대값이 중복인 경우를 대비해
		}
	}
	cout << answer;
}

int main()
{
	read();
	sort(nums.begin(), nums.end(), cmp);
	print_answer();
	return 0;
}

백준 1717 - 집합의 표현 (유니온 파인드 트리)

// https://www.acmicpc.net/problem/1717 (집합의 표현)
// Union-Find set (Disjoint set)

#include <iostream>
#include <vector>

using namespace std;

vector<int> _rank;
vector<int> parent;

int find(int a)
{
	if (a == parent[a])
		return a;
	else
		return find(parent[a]);
}

void merge(int a, int b)
{
	a = find(a);
	b = find(b);

	if (a == b)
		return;

	//a가 랭크가 낮거나 같게 만들어줌
	if (_rank[a] > _rank[b])
		swap(a, b);

	parent[a] = b;

	if (_rank[a] == _rank[b])
		_rank[b]++;
}

void print_is_same_set(int a, int b)
{
	if (find(a) == find(b))
		cout << "YES\n";
	else
		cout << "NO\n";
}


int main()
{
	int N, M;
	cin >> N >> M;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	_rank.resize(N + 1, 0);
	parent.resize(N + 1, 0);
	for (int i = 0; i <= N; ++i)
		parent[i] = i;

	while (M-- > 0)
	{
		int op, a, b;
		cin >> op >> a >> b;
		if (op == 0)
			merge(a, b);
		else if (op == 1)
			print_is_same_set(a, b);
	}
	return 0;
}

백준 2156 - 포도주 시식 (DP)

// https://www.acmicpc.net/problem/2156 (포도주 시식)
// DP

#include <iostream>
#include <algorithm>

using namespace std;

int wine[10000];
int dp[10001];
int n;

void calc_dp(int i)
{
	dp[i] = max(dp[i - 2] + wine[i - 1], dp[i - 3] + wine[i - 2] + wine[i - 1]);
	dp[i] = max(dp[i], dp[i - 1]);
}

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

	cin >> n;
	for (int i = 0; i < n ; ++i)
		cin >> wine[i];

	dp[0] = 0;
	dp[1] = wine[0];
	dp[2] = wine[0] + wine[1];

	for (int i = 3; i < n+1 ; ++i)
		calc_dp(i);
	
	cout << dp[n];
	return 0;
}

백준 2150 - SCC (SCC)

// https://www.acmicpc.net/problem/2150 (Strongly Connected Component)
// 타잔 알고리즘

#include <iostream>
#include <algorithm>
#include <stack>
#include <string.h>
#include <vector>

using namespace std;

constexpr int MAX = 10001;
vector<vector<int>> SCC;
vector<int> graph[MAX];
int id[MAX];
bool hasGroup[MAX];
stack<int> v_stack;
int visit_order = 1;

int V, E;


bool has_visited(int idx)
{
	return id[idx] != 0;
}

int dfs(int idx)
{
	id[idx] = visit_order++;
	v_stack.push(idx);

	int parent_id = id[idx];

	for (int i = 0; i < graph[idx].size(); ++i)
	{
		int to = graph[idx][i];

		if (false == has_visited(to))
			parent_id = min(parent_id, dfs(to));
		else if (false == hasGroup[to])
			parent_id = min(parent_id, id[to]);
	}

	if (id[idx] == parent_id)
	{
		vector<int> newSCC;
		while (true)
		{
			int top = v_stack.top(); v_stack.pop();
			hasGroup[top] = true;
			newSCC.emplace_back(top);

			if (idx == top)
				break;
		}
		sort(newSCC.begin(), newSCC.end());
		SCC.emplace_back(newSCC);
	}

	return parent_id;
}

void init()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	memset(id, 0, sizeof(id));
	memset(hasGroup, 0, sizeof(hasGroup));
}

void read()
{
	cin >> V >> E;
	while (E-- > 0)
	{
		int from, to;
		cin >> from >> to;
		graph[from].emplace_back(to);
	}
}

void solve()
{
	for (int i = 1; i <= V; ++i)
		if (false == has_visited(i))
			dfs(i);
	sort(SCC.begin(), SCC.end());
}

void print()
{
	cout << SCC.size() << "\n";
	for (int i = 0; i < SCC.size(); ++i)
	{
		for (int j = 0; j < SCC[i].size(); ++j)
		{
			cout << SCC[i][j] << ' ';
		}
		cout << "-1\n";
	}
}


int main()
{
	init();
	read();
	solve();
	print();

	return 0;
}

3665번: 최종 순위

올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에

www.acmicpc.net

'알고리즘 > 1주일 1문제' 카테고리의 다른 글

2022년 1분기 (0)	2023.01.23
2021년 4분기 (0)	2022.02.20
2021년 3분기 (0)	2021.10.22
2021년 1분기 (1)	2021.01.24
2020년 4분기 (0)	2021.01.24

현재글2021년 2분기

타입, 스레딩, 메모리, GameAI, 클린코드, clr, CPP, 유니티, 1.1, 추가 예정, 디자인패턴, C#, IL2CPP, C++, 아키텍쳐, dots, 동기화, AI, 그래픽스, 대수학,

Today :
Yesterday :

게임 클라 개발

2021년 2분기

'알고리즘 > 1주일 1문제' 카테고리의 다른 글

'알고리즘/1주일 1문제'의 다른글

티스토리툴바

« 2024/05 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

2021년 2분기

'알고리즘 > 1주일 1문제' 카테고리의 다른 글

'알고리즘/1주일 1문제'의 다른글

관련글

티스토리툴바