박경록 저자님의 코딩 테스트 합격자 되기 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)
- 도달한 사람의 수 : (이전 스테이지 도달 인원 - 이전 스테이지에 멈춰있는 인원)
- 각 스테이지에 멈춰있는 사람의 수 / 각 스테이지에 도달한 사람의 수 (visitN)
- 정렬을 위해서 multimap을 사용했다.
- map과 다르게 중복가능
- key 값을 기반으로 정렬
- key 값이 다른 경우 삽입순서대로.
- 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다. 라는 부분이 자연스레 해결
- 스테이지가 작은 순으로 실패율 계산하고 삽입함.
2. 방문 길이
1) 문제
문제 설명
게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.
U: 위쪽으로 한 칸 가기
D: 아래쪽으로 한 칸 가기
R: 오른쪽으로 한 칸 가기
L: 왼쪽으로 한 칸 가기캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.
이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길입니다)
단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.
제한사항
dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.
dirs의 길이는 500 이하의 자연수입니다.
2) 풀이
#include <string> #include <vector> using namespace std; vector<vector<vector<bool>>> visited; struct Pos { int x; int y; }; // 목표 좌표에 갈 수 있는지 bool CanGo(Pos nPos) { int x = nPos.x; int y = nPos.y; if (x < -5 || x > 5) return false; if (y < -5 || y > 5) return false; return true; } bool isVisitedBySamePath(Pos bPos, Pos nPos, int dir) { // 벡터 탐색을 위한 인덱스 int bx, by; int nx, ny; bx = (bPos.x + 5); by = (bPos.y + 5); nx = (nPos.x + 5); ny = (nPos.y + 5); //양방향 검사 //이전 좌표에서 목표 좌표로 방문한 적 있는지 //목표 좌표에서 이전 좌표로 방문한 적 있는지 if (visited[by][bx][dir] || visited[ny][nx][(dir + 2)%4]) return true; else { visited[by][bx][dir] = true; return false; } } void move(char c, Pos& currentpos, int& answer) { Pos nPos = currentpos; int dir=0; // 목표 좌표 설정 if (c == 'U') { nPos.y += 1; dir=0; } else if (c == 'D') { nPos.y -= 1; dir=2; } else if (c == 'R') { nPos.x += 1; dir=1; } else if (c == 'L') { nPos.x -= 1; dir=3; } if (CanGo(nPos)) { // 목표 좌표에 갈 수 있으면 // 이미 방문한 경로인지 확인 아니라면 count 증가 if (!isVisitedBySamePath(currentpos, nPos, dir)) answer++; // 현재 좌표 갱신 currentpos = nPos; } } int solution(string dirs) { int answer = 0; //각 좌표에서 갈 수 있는 4가지 경로를 방문 했는지 저장하는 벡터 visited.resize(11, vector<vector<bool>>(11, vector<bool>(4))); Pos currentPos = Pos{0,0}; for (auto c : dirs) { move(c, currentPos ,answer); } return answer; }
- visited 벡터를 통해서 해당 좌표에서 어떤 방향으로 방문 했는지 기록.
- 현재 좌표->목표 좌표, 목표 좌표->현재 좌표로 방문 했는지 체크
- 현재 좌표에서 목표 dir 방향 방문 확인
- 목표 좌표에서 (dir + 2)%4 방향 (dir과 반대 방향) 방문 확인
- ex) (1,2) -> (1,3) 혹은 (1,3) -> (1,2) 둘 중 하나라도 있으면 이미 방문한 경로.
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에서 뽑은 노드가 갈 수 있는 노드들을 순회
- 방문하지 않은 경우 뽑은 노드와 다른 색상 정보를 기입
- 이미 방문한 경우
- 뽑은 노드와 색이 동일하면 이분 그래프가 아님
