알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/DICTIONARY

 

algospot.com :: DICTIONARY

고대어 사전 문제 정보 문제 아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된

www.algospot.com

새롭게 정의된 사전순으로 입력된 단어들을 통해 새로운 사전순의 알파벳 순서를 알아내는 문제이다.

 

dfs를 이용한 위상 정렬을 사용하면 문제를 풀 수 있다.

dfs를 사용하면 어차피 우선순위가 낮은 알파벳 먼저 order에 push되므로 들어오는 간선이 하나도 없는 정점들을 굳이 먼저 탐색하지 않아도 된다.

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// 인접리스트를 위한 이차원 vector adj
vector<vector<int>>adj;
// 인접리스트 만들기
void makeGraph(vector<string>& words) {
adj = vector<vector<int>>(26);
// 주어진 차례대로 두개씩 비교
for (int j = 1; j < words.size(); j++) {
int i = j - 1;
int len = min(words[i].length(), words[j].length());
for (int k = 0; k < len; k++)
// 사전순서가 다른 이유가 되는 k번째 문자
if (words[i][k] != words[j][k]) {
// 계산하기 쉽게 문자를 정수로 변환
int a = words[i][k] - 'a';
int b = words[j][k] - 'a';
// a가 나타내는 문자가 b가 나타내는 문자보다 우선순위가 높음
adj[a].push_back(b);
break;
}
}
}
// 탐색 유무, 알파벳 사전 순서
vector<int> seen, order;
void dfs(int here) {
seen[here] = 1;
for (int i = 0; i < adj[here].size(); i++)
// 현재 알파벳보다 뒤에 나와야 하는게 있으면 dfs재귀
if (!seen[adj[here][i]])
dfs(adj[here][i]);
// 현재 알파벳보다 뒤에 나와야하는 알파벳을 모두 dfs완료했으면 자신도 order.push
order.push_back(here);
}
vector<int> topologicalSort() {
int m = adj.size();
seen = vector<int>(m, 0);
order.clear();
for (int i = 0; i < m; i++) if (!seen[i]) dfs(i);
// dfs를 실행하면 order가 사전순의 역순으로 정렬되 있으므로 뒤집어 준다.
reverse(order.begin(), order.end());
for (int i = 0; i < m; i++)
for (int j = i + 1; j < m; j++)
for(int k=0; k<adj[order[j]].size(); k++)
// 자신보다 뒤에 나와야하는 알파벳이 자신보다 먼저 나와야 하면 모순
if (adj[order[j]][k]==order[i])
return vector<int>();
return order;
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
int n;
cin >> n;
vector<string> words(n);
for (int i = 0; i < n; i++)
cin >> words[i];
makeGraph(words);
vector<int> result = topologicalSort();
if (result.empty())
cout << "INVALID HYPOTHESIS" << endl;
else {
for (int i = 0; i < result.size(); i++)
cout << char(result[i] + 'a');
cout << endl;
}
}
}
view raw algospot 고대어 사전 (문제 ID: DICTIONARY).cpp hosted with ❤ by GitHub

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

'Algorithm > algospot' 카테고리의 다른 글

algospot Sorting Game(문제 ID: SORTGAME) c++  (0) 2021.10.27
algospot 단어 제한 끝말잇기 (문제 ID: WORDCHAIN) c++  (0) 2021.10.22
algospot 에디터 전쟁 (문제 ID: EDITORWARS) c++  (0) 2021.10.18
algospot 삽입 정렬 시간 재기 (문제 ID: MEASURETIME)c++  (0) 2021.10.15
algospot 족보 탐험 (문제 ID: FAMILYTREE) c++  (0) 2021.10.14

알고스팟 문제 링크: https://algospot.com/judge/problem/read/EDITORWARS

 

algospot.com :: EDITORWARS

에디터 전쟁 문제 정보 문제 에디터 전쟁은 가장 유명한 자유 소프트웨어 텍스트 편집기인 vi와 Emacs 중 어느 쪽이 더 우월한가를 놓고 인터넷에서 자주 벌어지는 논쟁을 말합니다. 이 논쟁에 참

algospot.com

n개의 노드에 관한 m개의 관계가 주어진다.

만약 ack a b 라고 하면 a, b 가 같은 집합에 속해야 하고 만약 dis a b 라고 하면 a, b 가 서로 다른 집합에 속해야 한다.

이때 어떤 집합에 속할 수 있는 노드의 최대 갯수를 구하는 문제이다.

 

상호배타적집합을 사용하면 문제를 풀 수 있다.

한가지 주의할 점은 enemy라는 vector를 이용하여 적대관계(서로 다른 집하에 속해야만 하는)에 있는 집합의 루트 정보를 유지해야한다.

동지의 적은 적이므로 ack일때 merge할 상대와 적대관계에 있는 집합끼리 merge를 해야한다.

적의 적은 동지이므로 dis일때 dis인 상대의 적과 merge를 해야한다. 

 

#include<iostream>
#include<vector>
using namespace std;
// 트리구조를 이용해 상호배타적 집합 구현
struct BipartiteUnionFind {
// parent[i] = i의 부모 노드, 루트라면 i
// rank[i] = i가 루트인 경우, i를 루트로 하는 트리의 랭크
// enemy[i] = i가 루트인 경우, 해당 집합과 적대 관계인 집합의 루트의 번호(없으면 -1)
// size[i] = i가 루트인 경우, 해당 집합의 크기
vector<int> parent, rank, enemy, size;
BipartiteUnionFind(int n) : parent(n), rank(n, 0), enemy(n, -1), size(n, 1) {
for (int i = 0; i < n; i++)
parent[i] = i;
}
// u가 속한 트리의 루트를 찾는 함수
int find(int u) {
if (parent[u] == u)return u;
return parent[u] = find(parent[u]);
}
// u가 속한 트리와 v가 속한 트리를 병합
int merge(int u, int v) {
if (u == -1 || v == -1)return max(u, v);
u = find(u); v = find(v);
if (u == v)return u;
// 균일한 트리를 유지하기 위해서 트리의 높이가 큰 쪽이 루트
if (rank[u] > rank[v])swap(u, v);
parent[u] = v;
size[v] += size[u];
return v;
}
// u와 v가 서로 적대하는 집합
bool dis(int u, int v) {
u = find(u); v = find(v);
// 모순발생
if (u == v)return false;
// 적의 적은 나의 동지
int a = merge(u, enemy[v]);
int b = merge(v, enemy[u]);
enemy[a] = b; enemy[b] = a;
return true;
}
// u와 v가 같은 집합
bool ack(int u, int v) {
u = find(u); v = find(v);
// 모순발생
if (enemy[u] == v)return false;
// 동지의 적은 나의 적
int a = merge(u, v);
int b = merge(enemy[u], enemy[v]);
enemy[a] = b;
// 두 집합 다 적대하는 집합이 없으면 b는 -1일 수도 있기 때문에 예외처리
if (b != -1)enemy[b] = a;
return true;
}
};
int n;
// 한 파티에 올 가능성이 있는 최대 인원 구하기
int maxParty(const BipartiteUnionFind& buf) {
int ret = 0;
for (int node = 0; node < n; node++)
if (buf.parent[node] == node) {
int enemy = buf.enemy[node];
// 중복으로 세는것을 막기 위해 enemy < node인 경우에만 계산
if (enemy > node)continue;
int mySize = buf.size[node];
int enemySize = (enemy == -1 ? 0 : buf.size[enemy]);
ret += max(mySize, enemySize);
}
return ret;
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
int comments;
cin >> n >> comments;
BipartiteUnionFind uf(n);
string relation;
bool isContradiction = true;
int a, b, isContradictionIndex = -1;
for (int i = 0; i < comments; i++) {
cin >> relation >> a >> b;
if (relation == "ACK")
isContradiction = isContradiction && uf.ack(a, b);
else
isContradiction = isContradiction && uf.dis(a, b);
if (isContradictionIndex == -1 && !isContradiction)
isContradictionIndex = i;
}
if (isContradiction)
cout << "MAX PARTY SIZE IS " << maxParty(uf) << endl;
else
cout << "CONTRADICTION AT " << isContradictionIndex + 1 << endl;
}
}
view raw algospot 에디터 전쟁 (문제 ID: EDITORWARS).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/25.%20disjointSet/EDITORWARS.cpp

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

'Algorithm > algospot' 카테고리의 다른 글

algospot 단어 제한 끝말잇기 (문제 ID: WORDCHAIN) c++  (0) 2021.10.22
algospot 고대어 사전 (문제 ID: DICTIONARY) c++  (0) 2021.10.21
algospot 삽입 정렬 시간 재기 (문제 ID: MEASURETIME)c++  (0) 2021.10.15
algospot 족보 탐험 (문제 ID: FAMILYTREE) c++  (0) 2021.10.14
algospot 등산로 (문제 ID: MORDOR) c++  (0) 2021.10.14

알고스팟 문제 링크: https://algospot.com/judge/problem/read/MEASURETIME

 

algospot.com :: MEASURETIME

삽입 정렬 시간 재기 문제 정보 문제 유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다. 주어진 정수 배열 A를 정렬하는

algospot.com

길이 N인 수열 A[]가 주어지고, A[]를 삽입정렬했을때 정렬 과정에서 숫자들을 총 몇 번이난 옮기는지 계산하는 문제이다.

 

일단 모든 노드의 값이 0인 팬윅트리를 생성한다. A[]의 요소를 왼쪽부터 탐색해서 각 값에 해당하는 팬윅트리 노드들의 값을 1씩 증가시킨다. 또한 자신보다 큰 값이 나왔던 횟수를 구하기 위해 전체 횟수 합에서 자신이하의 값이 나온 횟수합을 뺀다.

 

#include<iostream>
#include<vector>
using namespace std;
// 팬윅트리의 구현
// 초기화시 A[]의 원소가 전부 0이라 생각
struct FenwickTree {
vector<int> tree;
FenwickTree(int n) : tree(n + 1) {}
// A[0,pos]의 부분 합을 계산
int sum(int pos) {
int ret = 0;
pos++;
while (pos > 0) {
ret += tree[pos];
pos &= (pos - 1);
}
return ret;
}
// A[pos]에 val을 더함
void add(int pos, int val) {
pos++;
while (pos < tree.size()) {
tree[pos] += val;
pos += (pos & -pos);
}
}
};
// 팬윅트리를 이용해 문제를 해결
long long countMoves(const vector<int>& A) {
FenwickTree tree(1000000);
long long ret = 0;
// 배열의 요소를 하나씩 추가하면서 자기보다 큰 요소의 갯수를 구함
for (int i = 0; i < A.size(); i++) {
ret += tree.sum(999999) - tree.sum(A[i]);
tree.add(A[i], 1);
}
return ret;
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
int n;
cin >> n;
vector<int> arr;
int element;
for (int i = 0; i < n; i++) {
cin >> element;
arr.push_back(element);
}
cout << countMoves(arr) << endl;
}
}
view raw algospot 삽입 정렬 시간 재기 (문제 ID: MEASURETIME).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/24.%20segmentTree/MEASURETIME.cpp

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

'Algorithm > algospot' 카테고리의 다른 글

algospot 고대어 사전 (문제 ID: DICTIONARY) c++  (0) 2021.10.21
algospot 에디터 전쟁 (문제 ID: EDITORWARS) c++  (0) 2021.10.18
algospot 족보 탐험 (문제 ID: FAMILYTREE) c++  (0) 2021.10.14
algospot 등산로 (문제 ID: MORDOR) c++  (0) 2021.10.14
algospot 변화하는 중간 값 (문제 ID: RUNNINGMEDIAN)c++  (0) 2021.10.11

알고스팟 문제 링크: https://algospot.com/judge/problem/read/FAMILYTREE

 

algospot.com :: FAMILYTREE

족보 탐험 문제 정보 문제 촌수는 혈연관계의 멀고 가까움을 의미하는 숫자로, 고려 말에 들어와 조선 시대에 정착된 것으로 알려져 있습니다. 촌수를 세는 계촌법은 부모와 자식간이 1촌이 되

algospot.com

0번 노드는 루트이고 1번부터 n-1번까지 각 노드의 parent의 번호가 주어진다.

정수로 노드의 번호 a, b가 주어질때 a와 b사이의 촌수(거리)를 구하는 문제이다.

 

문제에 제시된 트리를 전위탐색하면서 노드를 방문할때마다 trip이라는 vector안에 넣는다. 이때 depth와 현재 노드의 최초 방문 순서를 저장한다.

trip을 활용하여 RMQ를 생성하고 a, b의 공통조상을 찾는데 활용한다.

a, b의 거리는 ( a의 depth - 공통조상의 depth ) + ( b의 depth - 공통조상의 depth) 이다.

 

#include<iostream>
#include<vector>
#include<limits>
using namespace std;
const int INF_MAX = numeric_limits<int>::max();
// 구간 최소 쿼리를 위한 구조체
struct RMQ {
int n;
// 각 구간의 최소치
vector<int> rangeMin;
RMQ(vector<int>& arr) {
n = arr.size();
rangeMin.resize(4 * n);
init(arr, 0, n - 1, 1);
}
// node번째 노드가 arr[left, right] 배열을 표현할 때
// node번째 노드를 루트로 하는 서브트리를 초기화하고, 이 구간의 최소치를 반환
int init(vector<int>& arr, int left, int right, int node) {
// 리프노드까지 오면 자기 rangeMin에 자기 자신 저장후 return
if (left == right)
return rangeMin[node] = arr[left];
int mid = (left + right) / 2;
// 두 구간의 최소값중 작은값이 두구간을 합친 구간의 최솟값
rangeMin[node] = min(init(arr, left, mid, node * 2),
init(arr, mid + 1, right, 2 * node + 1));
return rangeMin[node];
}
// node가 표현하는 범위 arr[nodeLeft, nodeRight]가 주어질 때
// 이 범위와 arr[left, right]의 교집합의 최소치 구하기
int query(int left, int right, int node, int nodeLeft, int nodeRight) {
// 구하고자 하는 범위를 벗어나면 엄청나게 큰 값을 return
if (left > nodeRight || right < nodeLeft)
return INF_MAX;
// 구하고자 하는 범위에 완전히 속해있으면 구간 최솟값 return
if (left <= nodeLeft && right >= nodeRight)
return rangeMin[node];
// 둘다 아니면 양쪽 구간을 쪼개서 풀고 그 결과를 합친다
int mid = (nodeLeft + nodeRight) / 2;
return min(query(left, right, node * 2, nodeLeft, mid),
query(left, right, node * 2 + 1, mid + 1, nodeRight));
}
// query를 외부애서 호출하기 위한 overloading
int query(int left, int right) {
return query(left, right, 1, 0, n - 1);
}
};
const int MAX_N = 100000;
int n;
vector<int> child[MAX_N];
// 트리의 번호와 일련번호(전위탐색순서) 사이의 대응관계
int no2serial[MAX_N], serial2no[MAX_N];
// 각 노드가 trip에 처음 등장하는 위치, 각 노드의 깊이
int locInTrip[MAX_N], depth[MAX_N];
// 다음 일련번호
int nextSerial;
// 깊이가 d인 노드 here에 자식들을 전위 탐색
void traverse(int here, int d, vector<int>& trip) {
// traverse가 처음 방문하자마자 일련 번호 부여
no2serial[here] = nextSerial;
serial2no[nextSerial] = here;
nextSerial++;
// 깊이 저장
depth[here] = d;
// 현재 노드가 trip에 처음 등장하는 위치 = 현재 trip의 끝
locInTrip[here] = trip.size();
trip.push_back(no2serial[here]);
// 자식들을 방문
for (int i = 0; i < child[here].size(); i++) {
traverse(child[here][i], d + 1, trip);
// 자식 방문이 끝날때마다 다시 자기 자신으로 돌아옴
trip.push_back(no2serial[here]);
}
}
// trip에 대한 RMQ트리를 생성
RMQ* prepareRMQ() {
nextSerial = 0;
vector<int> trip;
// trip 생성
traverse(0, 0, trip);
return new RMQ(trip);
}
// u와 v사이의 거리를 계산
int distance(RMQ* rmq, int u, int v) {
int lu = locInTrip[u];
int lv = locInTrip[v];
if (lu > lv)swap(lu, lv);
// rmq에서 u와 v의 공통 조상를 찾아서
int lca = serial2no[rmq->query(lu, lv)];
// u와 v 사이의 거리 계산
return depth[u] + depth[v] - 2 * depth[lca];
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
for (int i = 0; i < MAX_N; i++)
child[i].clear();
int q;
cin >> n >> q;
for (int i = 1; i < n; i++) {
int parent;
cin >> parent;
child[parent].push_back(i);
}
RMQ* rmq = prepareRMQ();
for (int i = 0; i < q; i++) {
int a, b;
cin >> a >> b;
cout << distance(rmq, a, b) << endl;
}
}
}
view raw algospot 족보 탐험 (문제 ID: FAMILYTREE).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/24.%20segmentTree/FAMILYTREE.cpp

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

'Algorithm > algospot' 카테고리의 다른 글

algospot 에디터 전쟁 (문제 ID: EDITORWARS) c++  (0) 2021.10.18
algospot 삽입 정렬 시간 재기 (문제 ID: MEASURETIME)c++  (0) 2021.10.15
algospot 등산로 (문제 ID: MORDOR) c++  (0) 2021.10.14
algospot 변화하는 중간 값 (문제 ID: RUNNINGMEDIAN)c++  (0) 2021.10.11
algospot 삽입 정렬 뒤집기 (문제 ID: INSERTION) c++  (0) 2021.10.09

알고스팟 문제 링크: https://algospot.com/judge/problem/read/MORDOR

 

algospot.com :: MORDOR

등산로 문제 정보 문제 모르도르 지방의 아름다운 경치를 한 눈에 볼 수 있는 명산 오로드루인에는 길기로 유명한 등산로가 있습니다. 이 등산로는 산등성이를 따라 오르락내리락하며 구성되어

algospot.com

등산로에는 일정 간격으로 해발고도를 나타내는 표지판이 있다. 

등산로의 부분구간을 등산하는 등산로가 있다. 등산중에 만나는 표지판중 최대 해발고도와 최소해발고도의 차이가 등산로의 난이도이다.

표지판 정보와 등산로의 구간이 주어질때 해당 등산로의 난이도를 구하는 문제이다.

 

등산로의 표지판 정보들을 선형탐색해서는 최대 최소를 찾는다면 시간안에 문제를 풀 수 없다.

구간 최소 쿼리(range minimun query, RMQ)를 이용하여 문제를 풀어보자.

 

#include<iostream>
#include<vector>
#include<limits>
using namespace std;
const int INF_MAX = numeric_limits<int>::max();
// 구간 최소 쿼리를 위한 구조체
struct RMQ {
int n;
// 각 구간의 최소치
vector<int> rangeMin;
RMQ(vector<int>& arr) {
n = arr.size();
rangeMin.resize(4 * n);
init(arr, 0, n - 1, 1);
}
// node번째 노드가 arr[left, right] 배열을 표현할 때
// node번째 노드를 루트로 하는 서브트리를 초기화하고, 이 구간의 최소치를 반환
int init(vector<int>& arr, int left, int right, int node) {
// 리프노드까지 오면 자기 rangeMin에 자기 자신 저장후 return
if (left == right)
return rangeMin[node] = arr[left];
int mid = (left + right) / 2;
// 두 구간의 최소값중 작은값이 두구간을 합친 구간의 최솟값
rangeMin[node] = min(init(arr, left, mid, node * 2),
init(arr, mid + 1, right, 2 * node + 1));
return rangeMin[node];
}
// node가 표현하는 범위 arr[nodeLeft, nodeRight]가 주어질 때
// 이 범위와 arr[left, right]의 교집합의 최소치 구하기
int query(int left, int right, int node, int nodeLeft, int nodeRight) {
// 구하고자 하는 범위를 벗어나면 엄청나게 큰 값을 return
if (left > nodeRight || right < nodeLeft)
return INF_MAX;
// 구하고자 하는 범위에 완전히 속해있으면 구간 최솟값 return
if (left <= nodeLeft && right >= nodeRight)
return rangeMin[node];
// 둘다 아니면 양쪽 구간을 쪼개서 풀고 그 결과를 합친다
int mid = (nodeLeft + nodeRight) / 2;
return min(query(left, right, node * 2, nodeLeft, mid),
query(left, right, node * 2 + 1, mid + 1, nodeRight));
}
// query를 외부애서 호출하기 위한 overloading
int query(int left, int right) {
return query(left, right, 1, 0, n - 1);
}
};
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
int n, q;
cin >> n >> q;
// 최솟값을 구하기 위한 vector a
// 최댓값을 구하기 위한 vector b
vector<int> a, b;
int sign;
for (int i = 0; i < n; i++) {
cin >> sign;
a.push_back(sign);
// 최댓값을 구하기 위해서 원소에 부호를 반대로
b.push_back(-sign);
}
RMQ rmqA(a);
RMQ rmqB(b);
for (int i = 0; i < q; i++) {
int left, right;
cin >> left >> right;
cout << -rmqB.query(left, right) - rmqA.query(left, right) << endl;
}
}
}
view raw algospot 등산로 (문제 ID: MORDOR).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/24.%20segmentTree/MORDOR.cpp

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

'Algorithm > algospot' 카테고리의 다른 글

algospot 삽입 정렬 시간 재기 (문제 ID: MEASURETIME)c++  (0) 2021.10.15
algospot 족보 탐험 (문제 ID: FAMILYTREE) c++  (0) 2021.10.14
algospot 변화하는 중간 값 (문제 ID: RUNNINGMEDIAN)c++  (0) 2021.10.11
algospot 삽입 정렬 뒤집기 (문제 ID: INSERTION) c++  (0) 2021.10.09
algospot 너드인가, 너드가 아닌가? 2 (문제 ID: NERD2) c++  (0) 2021.10.07

알고스팟 문제 링크: https://algospot.com/judge/problem/read/RUNNINGMEDIAN

 

algospot.com :: RUNNINGMEDIAN

변화하는 중간값 문제 정보 문제 한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다. 예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이지요. 수열의 길이가 짝수일 때

algospot.com

수열을 다음과 같은 방법으로 추가한다고 하자.

A[0] = 1983

A[ i ] = (A[ i-1 ] * a + b) % 20090711

한 수열의 중간값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있다.

수열에 새로운 수가 추가될 때마다 해당 수열의 중간값의 다 더한 중간값의 합을 20090711로 나눈 나머지를 구하는 문제이다.

 

수열을 추가해 나갈때 다음과 같은 불변식을 지키며 최대, 최소 힙을 유지한다면 최대 힙의 top값이 현재 수열의 중간값이 된다.

1. 최대힙의 크기는 최소힙의 크기와 같거나 1 더 크다.

2. 최대힙의 top값 <= 최소힙의 top값

 

#include<iostream>
#include<queue>
using namespace std;
int n;
// 수열의 입력값 생성을 위한 구조체
struct RNG {
int a, b, seed;
RNG(int _a, int _b) :a(_a), b(_b), seed(1983) {}
int next() {
int ret = seed;
seed = (seed * (long long)a + b) % 20090711;
return ret;
}
};
int runningMedian(RNG rng) {
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
int ret = 0;
// 반복문 불변식
// 1. maxHeap의 크기는 minHeap의 크기와 같거나 1 더 크다.
// 2. maxHeap.top() <= minHeap.top()
for (int i = 0; i < n; i++) {
// 최대힙과 최소힙의 크기가 같은경우 최대힙에 push
if (maxHeap.size() == minHeap.size())
maxHeap.push(rng.next());
// 최대힙이 큰경우 최소힙에 push
else
minHeap.push(rng.next());
// 2번 불변식이 깨졌을 경우 복구
if (!minHeap.empty() && !maxHeap.empty() && minHeap.top() < maxHeap.top()) {
int a = minHeap.top();
int b = maxHeap.top();
minHeap.pop(); maxHeap.pop();
minHeap.push(b); maxHeap.push(a);
}
ret = (ret + maxHeap.top()) % 20090711;
}
return ret;
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
int a, b;
cin >> n >> a >> b;
RNG rng(a, b);
cout << runningMedian(rng) << endl;
}
}
view raw algospot 변화하는 중간 값 (문제 ID: RUNNINGMEDIAN).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/23.%20priorityQueue%20and%20Heap/RUNNINGMEDIAN.cpp

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

'Algorithm > algospot' 카테고리의 다른 글

algospot 족보 탐험 (문제 ID: FAMILYTREE) c++  (0) 2021.10.14
algospot 등산로 (문제 ID: MORDOR) c++  (0) 2021.10.14
algospot 삽입 정렬 뒤집기 (문제 ID: INSERTION) c++  (0) 2021.10.09
algospot 너드인가, 너드가 아닌가? 2 (문제 ID: NERD2) c++  (0) 2021.10.07
algospot 요새 (문제 ID: FORTRESS) c++  (0) 2021.10.06

알고스팟 문제 링크: https://algospot.com/judge/problem/read/INSERTION

 

algospot.com :: INSERTION

삽입 정렬 뒤집기 문제 정보 문제 유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다. 주어진 정수 배열 A를 정렬하는 삽

algospot.com

크기가 n이고 1~n까지의 순서없이 섞여있는 수열이 있다.

해당 수열의 원래 형태는 알 수 없지만, 수열을 삽입 정렬하는 경우 각 원소가 왼쪽으로 몇 칸이나 이동했는지가 입력으로 주어진다.

이때 원래 수열을 찾아내는 문제이다.

 

원래수열이 A[]라 할때 마지막 숫자 A[n-1]이 왼쪽으로 몇 칸 움직였는지를 알면 A[n-1]이 어떤 숫자인지 알 수 있다.

만약 n이 5이고 마지막 숫자가 왼쪽으로3칸 움지였다면, 1~5의 숫자중 마지막 숫자보다 큰게 3개 있다는 것이고

이것은 마지막 숫자가 2라는것을 의미한다.

이러한 방법으로 트립을 이용해 k번째 숫자를 찾고 해당 노드를 삭제하는 방식으로 끝에서부터 수열을 맞춰갈 수 있다.

 

#include<iostream>
using namespace std;
// 트립을 구성하느 노드
struct Node {
// 노드의 원소
int key;
// 노드의 우선순위, 해당 노드를 루트로하는 트리의 크기
int priority, size;
Node* left, * right;
Node(const int _key) : key(_key), priority(rand()),
size(1), left(NULL), right(NULL) {}
void setLeft(Node* newLeft) { left = newLeft; calcSize(); }
void setRight(Node* newRight) { right = newRight; calcSize(); }
// 자식노트가 바뀔때마다 size를 갱신
void calcSize() {
size = 1;
if (left) size += left->size;
if (right) size += right->size;
}
};
typedef pair<Node*, Node*> NodePair;
// root를 루트로 하는 트립의 key 미만의 값과 이상의 값을 갖는
// 두개의 트립으로 분리
NodePair split(Node* root, int key) {
// 리프노드에 도달할 경우
if (root == NULL)return NodePair(NULL, NULL);
// 루트가 key미만이면 오른쪽 서브트리를 다시 split
if (root->key < key) {
NodePair rs = split(root->right, key);
root->setRight(rs.first);
return NodePair(root, rs.second);
}
// 루트가 key 이상이면 왼쪽 서브트리를 다시 split
NodePair ls = split(root->left, key);
root->setLeft(ls.second);
return NodePair(ls.first, root);
}
// root를 루트로 하는 트립에서 새 노드 node를 삽입한 뒤 결과 트립의
// 루트를 반환한다.
Node* insert(Node* root, Node* node) {
if (root == NULL) return node;
// node가 루트를 대체하는 경우
// 해당 트리를 node->key기준으로 split해서 각각 자손으로 한다.
if (root->priority < node->priority) {
NodePair splitted = split(root, node->key);
node->setLeft(splitted.first);
node->setRight(splitted.second);
return node;
}
else if (node->key < root->key)
root->setLeft(insert(root->left, node));
else
root->setRight(insert(root->right, node));
return root;
}
// a와 b가 두 개의 트립이고, max(a) < min(b)일 때 이 둘을 합친다.
Node* merge(Node* a, Node* b) {
if (a == NULL)return b;
if (b == NULL)return a;
if (a->priority < b->priority) {
b->setLeft(merge(a, b->left));
return b;
}
a->setRight(merge(a->right, b));
return a;
}
// root를 루트로 하는 트립에서 key를 지우고 결과 트립의 루트를 반환
Node* erase(Node* root, int key) {
if (root == NULL) return root;
// root를 지우고 양 서브트리를 합친 뒤 반환
if (root->key == key) {
Node* ret = merge(root->left, root->right);
delete root;
return ret;
}
if (key < root->key)
root->setLeft(erase(root->left, key));
else
root->setRight(erase(root->right, key));
return root;
}
// root를 루트로 하는 트리 중에서 k번째 원소를 반환
Node* kth(Node* root, int k) {
int leftSize = 0;
// 왼쪽 서브트리의 크기를 먼저 계산
if (root->left != NULL) leftSize = root->left->size;
if (k <= leftSize)return kth(root->left, k);
if (k == leftSize + 1)return root;
return kth(root->right, k - leftSize - 1);
}
// shifted[i] = A[i]가 왼쪽으로 몇칸 움직이는가?
int n, shifted[50000];
int A[50000];
// n, shifted[]를 보고 A[]에 값을 저장
void solve() {
Node* candidates = NULL;
// 트립 형성
for (int i = 0; i < n; i++)
candidates = insert(candidates, new Node(i + 1));
// 뒤에서부터 A[]채우기
for (int i = n - 1; i >= 0; i--) {
int larger = shifted[i];
Node* k = kth(candidates, i + 1 - larger);
A[i] = k->key;
candidates = erase(candidates, k->key);
}
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
cin >> n;
for (int i = 0; i < n; i++)
cin >> shifted[i];
solve();
for (int i = 0; i < n; i++)
cout << A[i] << " ";
cout << endl;
}
}
view raw algospot 삽입 정렬 뒤집기 (문제 ID: INSERTION).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/22.%20BinarySearchTree/INSERTION.cpp

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

'Algorithm > algospot' 카테고리의 다른 글

algospot 등산로 (문제 ID: MORDOR) c++  (0) 2021.10.14
algospot 변화하는 중간 값 (문제 ID: RUNNINGMEDIAN)c++  (0) 2021.10.11
algospot 너드인가, 너드가 아닌가? 2 (문제 ID: NERD2) c++  (0) 2021.10.07
algospot 요새 (문제 ID: FORTRESS) c++  (0) 2021.10.06
algospot 트리 순회 순서 변경 (문제 ID: TRAVERSAL) c++  (0) 2021.10.05

알고스팟 문제 링크: https://algospot.com/judge/problem/read/NERD2

 

algospot.com :: NERD2

너드인가, 너드가 아닌가? 2 문제 정보 문제 대 성황이었던 지난 알고스팟 연간 모의고사 이후 프로그래밍 대회의 열기는 날로 뜨거워져 올해는 10만명이 넘는 사람들이 참가 신청을 할 것으로

algospot.com

p와 q가 다음과 같이 정의된다.

p: 알고스팟 온라인 채점 시스템에서 푼 문제의 수

q: 밤 새면서 지금까지 끓여먹은 라면 그릇 수

대회에 참가하려는 신청자 a의 문제 수 pa와 그릇 수 qa를 다른 참가 신청자 b의 문제 수 pb와 그릇 수 qb에 비교한다.

이때, pa < pb && qa < qb 이면 신청자 a는 대회에 참가할 수 없다.

한 사람의 참가 가능 여부는 다른 사람들의 문제와 라면 그릇 수에 의해 결정 되기 때문에,

대회에 참가할 수 있는 사람의 수는 새로운 사람이 참가 신청을 할 때마다 계속 바뀐다.

 

신청자들 각각의 p와 q를 x, y로 바꿔서 이차원 평면의 점들로 생각해보자.

대회에 참가하기 위해서는 기존의 점들보다 x값이 크거나 y값이 크거나 둘중 하나는 해야된다.

이는 곧 신청자의 (p,q)에서 p에 바로 오른쪽 점의 y좌표가 q보다 작아야 한다.

위 기준에 맞아서 새 신청자를 참가시킬시에는 새점 (p,q)에서 p에 왼쪽에 있는점의 y좌표가 q보다 작다면 더 이상 대회에 참가할 수 없다.

 

#include<iostream>
#include<map>
using namespace std;
// <x, y>를 점으로 추상화
map<int, int> coords;
// 새로운 점 (x,y)가 기존의 다른 점들에 지배당하는지 확인
bool isDominated(int x, int y) {
// x보다 오른쪽에 있는 점중에 가장 왼쪽에 있는점
map<int, int>::iterator it = coords.lower_bound(x);
// 없으면 지배당하지 않는다
if (it == coords.end())return false;
// 이 점은 x보다 오른쪽에 있는 점들 중 가장 왼쪽에 -> 가장 위에 있는 점
// 이 점 보다 밑에 있으면 이점보다 x값도 작고 y값도 작은게 됨 -> 너드 아님
return y < it->second;
}
// 새로운 점 (x, y)에 지배당하는 점들을 map에서 지움
void removeDominated(int x, int y) {
map<int, int>::iterator it = coords.lower_bound(x);
// x보다 왼쪽에 있는 점이 없는 경우
if (it == coords.begin())return;
--it;
while (true) {
// it가 가르키는 점보다 y가 작으면 더 이상 지울게 없음
if (it->second > y)break;
// it다음 점이 없으므로 it가 가르키는 점만 지우고 종료
if (it == coords.begin()) {
coords.erase(it);
break;
}
// it를 지우고 다음 왼쪽 점을 가르킨다.
else {
map<int, int>::iterator jt = it;
jt--;
coords.erase(it);
it = jt;
}
}
}
// (x,y)가 추가되었을 때 coords를 갱신하고 남아있는 점의 갯수 반환
int registered(int x, int y) {
// 새 점이 지배당하면 그냥 새 점을 버리고 끝
if (isDominated(x, y))return coords.size();
// 새 점에 의해 지워지는 점들을 제거하고 coords갱신
removeDominated(x, y);
coords[x] = y;
return coords.size();
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
coords.clear();
int n, x, y, sum = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x >> y;
sum += registered(x, y);
}
cout << sum << endl;
}
}
view raw algospot 너드인가, 너드가 아닌가? 2 (문제 ID: NERD2).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/22.%20BinarySearchTree/NERD2.cpp

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

'Algorithm > algospot' 카테고리의 다른 글

algospot 변화하는 중간 값 (문제 ID: RUNNINGMEDIAN)c++  (0) 2021.10.11
algospot 삽입 정렬 뒤집기 (문제 ID: INSERTION) c++  (0) 2021.10.09
algospot 요새 (문제 ID: FORTRESS) c++  (0) 2021.10.06
algospot 트리 순회 순서 변경 (문제 ID: TRAVERSAL) c++  (0) 2021.10.05
algospot 말버릇 (문제 ID: HABIT) c++  (0) 2021.10.04

+ Recent posts

티스토리툴바