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, 클린코드, C#, dots, 추가 예정, clr, 메모리, 타입, 1.1, 대수학, AI, IL2CPP, C++, 그래픽스, CPP, 아키텍쳐, 스레딩, 디자인패턴,

Today :
Yesterday :

게임 클라 개발

2021년 2분기

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

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

티스토리툴바

« 2025/01 »
일	월	화	수	목	금	토
			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문제'의 다른글

관련글

티스토리툴바