알고리즘 스터디 2일차

박경록 저자님의 코딩 테스트 합격자 되기 c++ 편을 완독 하는 것을 목표로 남기는 공부 일지

1. 실패율

1) 문제

문제 설명
실패율은 다음과 같이 정의한다.
스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

제한사항
스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
stages의 길이는 1 이상 200,000 이하이다.
stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

2) 풀이

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<int> visited(N+2,0);
    multimap<double, int, greater<double>> failpercentage;

    for (int i=0; i < stages.size(); i++)
    {
        visited[stages[i]]++;
    }

    int visitN = stages.size();

    for (int i=1; i <= N; i++)
    {
        double percent = 0;
        if (visitN != 0)
            percent = static_cast<double>(visited[i]) / visitN;

        failpercentage.insert({percent, i});
        visitN -= visited[i];
    }

    for (auto e : failpercentage)
    {
        answer.push_back(e.second);
    }

    return answer;
}

• 각 스테이지에 멈춰있는 사람의 수(도달은 했지만 클리어는 하지 못한)를 visited에 기록
• 제한 사항에 의해 모든 사용자는 최소 1스테이지는 도달 함.
  • (int visitN = stages.size();)
  • 1 스테이지 도달인원 = 사용자 크기
• 실패율 계산
  • 각 스테이지에 멈춰있는 사람의 수 / 각 스테이지에 도달한 사람의 수 (visitN)
    • 도달한 사람의 수 : (이전 스테이지 도달 인원 - 이전 스테이지에 멈춰있는 인원)
• 정렬을 위해서 multimap을 사용했다.
  • map과 다르게 중복가능
  • key 값을 기반으로 정렬
    • key 값이 다른 경우 삽입순서대로.
    • 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다. 라는 부분이 자연스레 해결
    • 스테이지가 작은 순으로 실패율 계산하고 삽입함.

3. 이분 그래프

1) 문제

문제 설명
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.

출력
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

2) 풀이

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define COLOR_R 1
#define COLOR_B 2

int K, V, E;
vector<vector<int>> graph;
vector<int> visited;

bool BFS(int start)
{
	queue<int> q;
	q.push(start);
	visited[start] = COLOR_R;

	while (true)
	{
		if (q.size() == 0)
			break;
		int front = q.front();
		q.pop();

		for (int i = 0; i < graph[front].size(); i++)
		{
			int v = graph[front][i];
			if (visited[v] == 0)
			{
				if (visited[front] == COLOR_R)
				{
					visited[v] = COLOR_B;
					q.push(v);
				}
				else if (visited[front] == COLOR_B)
				{
					visited[v] = COLOR_R;
					q.push(v);
				}
			}
			else if (visited[v] == visited[front])
			{
				return false;
			}
		}
	}
	return true;
}

bool isBipartite()
{
	bool done = false;
	while (true)
	{
		if (done)
			break;

		for (int i = 1; i <= V; i++)
		{
			if (!visited[i])
			{
				bool res = BFS(i);
				if (!res)
					return false;
				else
					i = 0;
			}
			else
			{
				if (i == V)
					done = true;
			}
		}
	}
	return true;
}

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

	cin >> K;
	for (int i = 0; i < K; i++)
	{
		cin >> V >> E;
		graph.assign(V + 1, vector<int>());
		visited.assign(V + 1, 0);

		for (int j = 0; j < E; j++)
		{
			int from, to;
			cin >> from >> to;
			graph[from].push_back(to);
			graph[to].push_back(from);
		}
		cout << (isBipartite() ? "YES" : "NO") << "\n";
	}
}

• 이분 그래프를 알아 볼 수 있었던 문제.
• 모든 노드를 방문할 때 까지 BFS를 돌려야함
• BFS
  • queue에서 뽑은 노드가 갈 수 있는 노드들을 순회
  • 방문하지 않은 경우 뽑은 노드와 다른 색상 정보를 기입
  • 이미 방문한 경우
    • 뽑은 노드와 색이 동일하면 이분 그래프가 아님