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

 

algospot.com :: GALLERY

감시 카메라 설치 문제 정보 문제 전세계의 유명한 인물화들을 모아 두는 미술관에 괴도 콩의 도전장이 날아들었습니다. 2022년 2월 2일을 기념하여, 미술관에 전시된 인물화 중 하나의 얼굴을 모

algospot.com

그래프에서 인접한 노드중에 적어도 하나의 노드에 감시카메라가 설치되어있지 않으면 해당 노드에 감시카메라를 설치 해야한다.

이때 필요한 최소한의 감시카메라의 개수를 구하는 문제이다.

 

문제 조건에서 "미술관은 한 번 관람한 갤러리를 다시 가기 위해서는 이전에 지나왔던 복도를 반드시 한 번 지나야 하는 구조로 설계되어 있으며"가 있으므로 해당 그래프는 트리형태임을 알 수 있다.

따라서 자손 노드들의 상태를 보고 하나라도 UNWATCHED상태라면 해당 노드에 감시카메라를 설치하는 알고리즘을 사용할 수 있다.

또한 "모든 갤러리가 서로 연결되어 있지 않을 수도 있습니다."라는 조건이 있으므로 모든 노드가 방문되었는지 확인하는 절차도 필요하다.

 

view raw algospot 감시 카메라 설치(문제 ID: GALLERY).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/28.%20DFS/GALLERY.cpp

 

GitHub - sbl133/JongmanBook

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

github.com

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

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

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

algospot 소방차(문제ID: FIRETRUCKS) c++  (0) 2022.03.08
algospot 회의실 배정(문제 ID: MEETINGROOM) c++  (0) 2022.03.05
algospot 보안종결자(문제 ID: NH) c++  (0) 2022.03.01
algospot 안녕히, 그리고 물고기는 고마웠어요!(문제 ID: SOLONG) c++  (0) 2021.12.22
algospot 신호 라우팅 (문제 ID: ROUTING) c++  (0) 2021.10.29

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

 

algospot.com :: NH

보안종결자 문제 정보 문제 음지에서 살아가는 보안 초전문가 슈퍼코더 K 는 이번에 새로운 은행의 전산망을 해킹하려고 합니다. 그에게는 원래 은행의 전산망을 해킹하는 것은 손바닥 뒤집는

algospot.com

입력으로 주어지는 특정한 문자열 패턴들이 나타나지 않게 알파벳 소문자로만 이뤄진 n자리 암호를 만들 수 있는 모든 경우의 수를 10007로 나눈 나머지를 구하는 문제이다.

bruteforce로 풀게되면 26^n의 시간복잡도를 가지게 되므로 제한시간 안에 문제를 푸는것이 불가하다.

동적계획법을 이용하면 문제를 풀 수 있는데 그 방법이 매우 어렵고 까다롭다. (종만북의 연습문제중 가장 어려웠던것 같다.) 

먼저 입력으로 주어진 문자열 패턴들을 트라이로 만들고 각 노드마다 상태를 부여한다.

앞으로 만들어야하는 글자의 갯수 length, 현재 트라이의 상태를 state라 했을때 cache[length][state]형태의 캐시를 이용한다.

하지만 이렇게 트라이를 이용한 동적계획법을 구현하기 위해서는

먼저 트라이의 각 노드들이 실패연결과 출력문자열을 가지고 있어야하고, 각 노드마다 상태 번호가 부여되야 한다.

 

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int ALPHABETS = 26;
int toNumber(char ch) { return ch - 'a'; }
struct TrieNode {
TrieNode* children[ALPHABETS];
// 이 노드에서 종료하는 문자열의 번호. 없으면 -1
int terminal;
// 실패 연결: 이 노드에서 매칭이 실패했을 때 이 곳으로 가서 계속진행
// 이 노드에 대응되는 문자열의 접미사이면서 트라이에 포함된 최대 문자열
TrieNode* fail;
// 출력 문자열 목록: 이 노드가 방문되었을 때 등장하는 바늘 문자열들의 번호
vector<int> output;
// 해당 노드의 번호
int no;
// 해당 노드 뒤에 어떤 문자가 붙었을때 어떤 노드를 가지는지
TrieNode* next[ALPHABETS];
TrieNode() : terminal(-1) {
memset(children, 0, sizeof(children));
};
~TrieNode() {
for (int i = 0; i < 26; i++)
if (children[i])
delete children[i];
}
// 이 노드를 루트로 하는 트라이에 번호 id인 문자열 key를 추가
void insert(const char* key, int id) {
if (*key == 0)
terminal = id;
else {
int next = toNumber(*key);
// 해당 자식 노드가 없다면 생성한다.
if (children[next] == NULL)
children[next] = new TrieNode();
// 해당 자식 노드로 재귀 호출
children[next]->insert(key + 1, id);
}
}
};
TrieNode* readInput(int words) {
vector<string> input;
TrieNode* trie = new TrieNode();
for (int i = 0; i < words; i++) {
char buf[11];
cin >> buf;
trie->insert(buf, i);
}
return trie;
}
void computeFailFunc(TrieNode* root) {
// 루트에서 시작해 한 단계씩 아래로 내려가며 각 노드의 실패 연결 계산
queue<TrieNode*> q;
// 루트 실패 연결은 자기 자신
root->fail = root;
q.push(root);
while (!q.empty()) {
TrieNode* here = q.front();
q.pop();
// here의 모든 자손에 대해 실패 연결을 계산하고 큐에 삽입
for (int edge = 0; edge < ALPHABETS; edge++) {
TrieNode* child = here->children[edge];
if (!child) continue;
// 1레벨 노드의 실패 연결은 항상 루트
if (here == root)
child->fail = root;
else {
// 아닌 경우 부모의 실패 연결을 따라가면서 실패 연결 탐색
TrieNode* t = here->fail;
while (t != root && t->children[edge] == NULL)
t = t->fail;
if (t->children[edge])t = t->children[edge];
child->fail = t;
}
// 출력 문자열 목록: 실패 연결을 따라간 노드에서 복사 and
// 이 위치에서 끝나는 바늘 문자열이 있으면 추가
child->output = child->fail->output;
if (child->terminal != -1)
child->output.push_back(child->terminal);
q.push(child);
}
}
}
// 상태간의 전이 테이블을 next[]에 채운다
void computeTransition(TrieNode* here, int& nodeCounter) {
// 0에서 시작하는 번호를 매긴다.
here->no = nodeCounter++;
// here 뒤에 글자 chr를 붙였을때 어느 상태로 가는지
for (int chr = 0; chr < ALPHABETS; chr++) {
// next[] 값을 계산해 저장
TrieNode* next = here;
while (next != next->fail && next->children[chr] == NULL)
next = next->fail;
if (next->children[chr])next = next->children[chr];
here->next[chr] = next;
// 재귀적으로 모든 노드에 대해 전이 테이블 계산
if (here->children[chr])
computeTransition(here->children[chr], nodeCounter);
}
}
const int MOD = 10007;
int cache[101][1001];
// 앞으로 length글자를 더 만들어야 하는데, 아호-코라식 알고리즘의
// 현재 상태가 state에 주어질 때 ids에 걸리지 않는 문자열의 갯수
int count(int length, TrieNode* state) {
// 기저 사례: 이 상태에 문자열이 출현하면 곧장 종료
if (state->output.size())return 0;
// 기저 사례: 문자열을 전부 만든 경우
if (length == 0)return 1;
int& ret = cache[length][state->no];
if (ret != -1)return ret;
ret = 0;
// 다음으로 letter글자를 넣은 경우
for (int letter = 0; letter < ALPHABETS; letter++) {
ret += count(length - 1, state->next[letter]);
ret %= MOD;
}
return ret;
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
int n, m;
cin >> n >> m;
int nodeCounter = 0;
TrieNode* trie = readInput(m);
computeFailFunc(trie);
computeTransition(trie, nodeCounter);
memset(cache, -1, sizeof(cache));
cout << count(n, trie) << endl;
}
}
view raw algospot 보안종결자(문제 ID: NH).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/26.%20Trie/nh.cpp

 

GitHub - sbl133/JongmanBook

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

github.com

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

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

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

algospot 회의실 배정(문제 ID: MEETINGROOM) c++  (0) 2022.03.05
algospot 감시 카메라 설치(문제 ID: GALLERY) c++  (0) 2022.03.03
algospot 안녕히, 그리고 물고기는 고마웠어요!(문제 ID: SOLONG) c++  (0) 2021.12.22
algospot 신호 라우팅 (문제 ID: ROUTING) c++  (0) 2021.10.29
algospot 하노이의 탑 (문제 ID: HANOI4B) c++  (0) 2021.10.29

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

 

algospot.com :: SOLONG

안녕히, 그리고 물고기는 고마웠어요! 문제 정보 문제 문자 입력이 불편한 핸드폰이나 타블렛 같은 기계에서는 빠른 타이핑을 위해 강력한 자동 완성 기능을 제공합니다. 시리우스 사이버네틱

algospot.com

사전에 들어있는 단어들이 빈도수와 함께 주어진다. 특정한 문장을 완성시키려할때 탭키를 사용하여 사전을 참조한 자동완성 기능을 사용할 수 있다.

타이핑한 알파벳을 접두사로 갖는 단어들의 빈도수를 우선순위로 하고 빈도수가 같은  단어가 두개 이상있으면 사전순을 우선순위로 한다.

이때 특정한 문장을 완성시키기 위한 총 타이핑 횟수를 구하는 문제이다.

 

일단 사전에 들어갈 문자들을 트라이 형태로 삽입한다. 이때 삽입하는 단어들을 빈도수와 사전순을 고려하여 정렬한 후 차례로 삽입한다.

이런식으로 삽입할 경우 자동완성을 위한 first를 한번만 갱신하면 되므로 자동완성 단어를 계산하기 위한 메모리와 시간이 최소화 된다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
// 알파벳 대문자를 숫자로 표현
int toNumber(char ch) { return ch - 'A'; }
// 트라이의 한 노드를 나타내는 객체
struct TrieNode {
// 자식이 알파벳 개수만큼 있을 수 있음
TrieNode* children[26];
// 해당 노드가 종료 노드이면 id값 아니면 -1
int terminal;
// 해당 노드를 루트로 했을때 자동완성가능한 단어 id값
int first;
TrieNode(): terminal(-1), first(-1) {
memset(children, 0, sizeof(children));
};
~TrieNode() {
for (int i = 0; i < 26; i++)
if (children[i])
delete children[i];
}
// key 문자열을 id값으로 삽입
void insert(const char* key, int id) {
// 해당 접두사로 자동완성되는 단어가 없으면 first 갱신
if (first == -1) first = id;
// 단어의 끝일경우 terminal 갱신
if (*key == 0)terminal = id;
// 단어가 끝이 아닐경우 알맞은 자식노드로 재귀
else {
int next = toNumber(*key);
if (children[next] == NULL)
children[next] = new TrieNode();
children[next]->insert(key + 1, id);
}
}
// 해당 노드를 루트로하는 트라이에서 key와 대응되는 노드를 찾기
TrieNode* find(const char* key) {
if (*key == 0) return this;
int next = toNumber(*key);
// key가 트라이에 없으면 NULL 반환
if (children[next] == NULL)return NULL;
return children[next]->find(key + 1);
}
// 해당 노드까지 왔을때, id값이 id인 문자열 key를 완성시키기 위해서 쳐야되는 타자횟수
int type(const char* key, int id) {
// 단어의 끝이면 다 완성된것이므로 return 0
if (*key == 0) return 0;
// 자동완성되는 단어가 치고자 하는 단어면 탭키
if (first == id)return 1;
int next = toNumber(*key);
// 아직 못찾았으면 재귀
return 1 + children[next]->type(key + 1, id);
}
};
// 주어진 트라이에서 단어 word를 완성시키기 위해 필요한 타자 횟수
int countKeys(TrieNode* trie, const char* word) {
TrieNode* node = trie->find(word);
if (node == NULL || node->terminal == -1) return strlen(word);
return trie->type(word, node->terminal);
}
// 입력으로 주어진 단어들을 빈도수, 사전순으로 정렬하여 트라이 형태로 삽입
// 정렬을 한 후 차례대로 트라이에 삽입하게 되면 자동완성에 우선순위가 반영된다.
TrieNode* readInput(int words) {
vector<pair<int, string>> input;
for (int i = 0; i < words; i++) {
string buf;
int freq;
cin >> buf >> freq;
input.push_back(make_pair(-freq, buf));
}
sort(input.begin(), input.end());
TrieNode* trie = new TrieNode();
for (int i = 0; i < input.size(); i++)
trie->insert(input[i].second.c_str(), i);
trie->first = -1;
return trie;
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
int n, m, result = 0;
string tmp;
cin >> n >> m;
TrieNode* trie = readInput(n);
for (int i = 0; i < m; i++) {
cin >> tmp;
result += countKeys(trie, tmp.c_str());
}
cout << result + m - 1 << endl;
}
}
view raw algospot 안녕히, 그리고 물고기는 고마웠어요!(문제 ID: SOLONG.cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/26.%20Trie/solong.cpp

 

GitHub - sbl133/JongmanBook

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

github.com

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

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

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

algospot 감시 카메라 설치(문제 ID: GALLERY) c++  (0) 2022.03.03
algospot 보안종결자(문제 ID: NH) c++  (0) 2022.03.01
algospot 신호 라우팅 (문제 ID: ROUTING) c++  (0) 2021.10.29
algospot 하노이의 탑 (문제 ID: HANOI4B) c++  (0) 2021.10.29
algospot 어린이날 (문제 ID: CHILDRENDAY) c++  (0) 2021.10.28

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

 

algospot.com :: ROUTING

신호 라우팅 문제 정보 문제 위 그림은 여러 개의 컴퓨터들과 각 컴퓨터들을 잇는 회선을 나타냅니다. 각 회선들은 각각 품질이 다르며, 각 회선을 지날 때마다 신호에 있던 노이즈가 증폭될 수

algospot.com

정점에서 다른정점으로 가기 위한 회선을 지날 때 노이즈가 회선에 부여된 수 만큼 곱으로 증폭 된다.

0번째 정점에서 n-1번째 정점으로 가는 최소 증폭량을 구하는 문제이다.

 

다익스트라 알고리즘을 이용하면 쉽게 문제를 해결할 수 있다.

주의할 점은 곱연산으로 dist를 계산하기 때문에 초기 증폭값을 0이 아닌 1.0으로 두어야 한다.

 

#include<iostream>
#include<vector>
#include<queue>
#include<limits>
using namespace std;
// 정점의 갯수
int V;
// 인접리스트
vector<pair<int, double>> adj[10000];
// 각 정점까지의 최소 증폭량 구하는 다익스트라 알고리즘
vector<double> dijkstra(int src) {
vector<double> dist(V, numeric_limits<double>::max());
// 간선을 지날때마다 곱 연산을 해야하므로 초기 값 1.0
dist[src] = 1.0;
// priority_queue<해당 정점까지의 증폭량, 정점번호>
priority_queue<pair<double, int>> pq;
// 우선순위 큐는 디폴트가 내림차순이므로 -1 곱해서 넣어준다
pq.push(make_pair(-1.0, src));
while (!pq.empty()) {
double cost = -pq.top().first;
int here = pq.top().second;
pq.pop();
if (dist[here] < cost)continue;
for (int i = 0; i < adj[here].size(); i++) {
int there = adj[here][i].first;
// here에서 there로 갔을때 증폭량
double nextDist = cost * adj[here][i].second;
// 이제까지 구한것 중에서 가장 작으면 우선순위큐에 넣는다.
if (dist[there] > nextDist) {
dist[there] = nextDist;
pq.push(make_pair(-nextDist, there));
}
}
}
return dist;
}
int main() {
cout << fixed;
cout.precision(10);
int testcase;
cin >> testcase;
while (testcase--) {
int edges;
cin >> V >> edges;
for (int i = 0; i < V; i++)
adj[i].clear();
int a, b;
double c;
for (int i = 0; i < edges; i++) {
cin >> a >> b >> c;
adj[a].push_back(make_pair(b, c));
adj[b].push_back(make_pair(a, c));
}
vector<double> output = dijkstra(0);
cout << output[V - 1] << endl;
}
}
view raw algospot 신호 라우팅 (문제 ID: ROUTING).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/30.%20ShortestPath/ROUTING.cpp

 

GitHub - sbl133/JongmanBook

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

github.com

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

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

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

algospot 보안종결자(문제 ID: NH) c++  (0) 2022.03.01
algospot 안녕히, 그리고 물고기는 고마웠어요!(문제 ID: SOLONG) c++  (0) 2021.12.22
algospot 하노이의 탑 (문제 ID: HANOI4B) c++  (0) 2021.10.29
algospot 어린이날 (문제 ID: CHILDRENDAY) c++  (0) 2021.10.28
algospot Sorting Game(문제 ID: SORTGAME) c++  (0) 2021.10.27

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

 

algospot.com :: HANOI4

하노이의 네 탑 문제 정보 문제 하노이의 탑은 세 개의 기둥에 꽂혀 있는 N개의 원반을 가지고 하는 게임입니다. N개의 원반은 크기가 모두 다르며, 게임의 시작 때는 그림과 같이 맨 왼쪽의 기둥

algospot.com

기둥이 4개인 하노이의 탑 문제이다. 단 초기 상태는 입력으로 주어진다.

 

양방향 BFS를 이용하여 문제를 풀 수 있다. 이때 각 디스크가 위치할 수 있는 기둥은 총 4개이므로 두개의 비트로 각 디시크의 위치를 표현가능하다.

따라서 총 12*2개의 비트로 디스크의 전체 위치를 표현 가능하므로 비트마스크 기법을 이용하여 int로 디스크의 전체 위치를 표현할 수 있다.

 

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
// index번째 디스크가 몇번째 기둥에 있는지
int get(int state, int index) {
return (state >> (index * 2)) & 3;
}
// index번째 디스크를 value번째 기둥으로 옮기기
int set(int state, int index, int value) {
return (state & ~(3 << (index * 2))) | (value << (index * 2));
}
// x 부호 반환
int sgn(int x) { if (!x)return 0; return x > 0 ? 1 : -1; }
// x의 절대값 1증가
int incr(int x) { if (x < 0) return x - 1; return x + 1; }
int c[1 << (12 * 2)];
// discs개의 디스크가 begin상태에서 end상태로 가기위한 최소 움직임 수
int bidir(int discs, int begin, int end) {
if (begin == end)return 0;
queue<int> q;
memset(c, 0, sizeof(c));
// 정방향 탐색은 양수, 역방향 탐색은 음수로 양방향 탐색
q.push(begin); c[begin] = 1;
q.push(end); c[end] = -1;
while (!q.empty()) {
int here = q.front();
q.pop();
int top[4] = { -1,-1,-1,-1 };
// 각 기둥에 제일 위에 있는 disc계산
for (int i = discs - 1; i >= 0; i--)
top[get(here, i)] = i;
// i번째 기둥 맨 위에 있는 disc를 j번째 기둥으로 옮기기
for (int i = 0; i < 4; i++)
if(top[i]!=-1)
for(int j=0; j<4; j++)
// j번째 기둥은 비어 있거나, 맨 위의 disc가 제일 거야함
if (i != j && (top[j] == -1 || top[j] > top[i])) {
int there = set(here, top[i], j);
if (c[there] == 0) {
c[there] = incr(c[here]);
q.push(there);
}
else if (sgn(c[there]) != sgn(c[here]))
return abs(c[there]) + abs(c[here]) - 1;
}
}
return -1;
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
int n, begin = 0, end = 0;
cin >> n;
for (int i = 0; i < 4; i++) {
int num;
cin >> num;
for (int j = 0; j < num; j++) {
int discNum;
cin >> discNum;
begin |= i << ((discNum - 1) * 2);
}
}
for (int i = 0; i < n; i++) {
end |= 3 << (i * 2);
}
cout << bidir(n, begin, end) << endl;
}
}
view raw algospot 하노이의 탑 (문제 ID: HANOI4B).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/29.%20BFS/HANOI4B.cpp

 

GitHub - sbl133/JongmanBook

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

github.com

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

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

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

algospot 안녕히, 그리고 물고기는 고마웠어요!(문제 ID: SOLONG) c++  (0) 2021.12.22
algospot 신호 라우팅 (문제 ID: ROUTING) c++  (0) 2021.10.29
algospot 어린이날 (문제 ID: CHILDRENDAY) c++  (0) 2021.10.28
algospot Sorting Game(문제 ID: SORTGAME) c++  (0) 2021.10.27
algospot 단어 제한 끝말잇기 (문제 ID: WORDCHAIN) c++  (0) 2021.10.22

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

 

algospot.com :: CHILDRENDAY

어린이날 문제 정보 문제 어린이집을 경영하는 원석이는 어린이날을 맞아 어린이집에 다니는 N 명의 아이들에게 장난감을 나눠 주기로 마음먹었습니다. 모든 아이들에게 같은 수의 장난감을 주

algospot.com

문자열로 주어진 특정 십진수(0~9)로만 장난감 갯수를 확보할 수 있다.

장난감을 n명의 아이들에게 나눠주는데 그 중 m명은 같은 개수의 장난감을 받으면 삐지므로 한 개 더 주려 한다.

위 조건을 만족하면서 가능한 적은 수의 장난감의 갯수 c를 계산하는 문제이다.

 

문제에 주어진 c에 대한 조건을 정리하면 다음과 같다.

1. n+m 이상이어야 한다.

2. n으로 나눈 나머지가 m이어야 한다.

3. d에 포함된 숫자들로만 구성되어 있어야 한다.

먼저 3번 조건을 만족하는 숫자들 중에서 2번을 만족하는 경우를 계산하는 방법을 생각해보면,

c의 뒤에 숫자 x를 붙여나가는 방식으로 c를 확장한다면 ((c mod n)*10+x) mod n = (c*10+x) mod n 이므로 c를 n으로 나눈 나머지가 m인 최소 숫자를 찾을 수 있다.

이때 주의할 점은 n+m이상인 조건도 만족시켜야 하므로 n+m미만인 나머지값 정점이랑 n+m이상인 나머지값 정점을 구분해야 한다.

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n, m;
// here에서 edge를 통하면 나오는 정점
int append(int here, int edge, int mod) {
int there = here * 10 + edge;
if (there >= mod)return mod + there % mod;
return there;
}
// C mod n == m인 최소 C 찾기
string gifts(string digits) {
// 간선의 번호를 오름차순으로 정렬하면 장난감이 가장 적은순으로 경로 탐색 가능
sort(digits.begin(), digits.end());
// parent[i] = i의 부모, choice[i] = parent[i]에서 i로 연결된 간선의 번호
vector<int> parent(2 * n, -1), choice(2 * n, -1);
queue<int> q;
// n+m미만이고 나머지가 0인 경우(맨 처음 경우)
parent[0] = 0;
q.push(0);
while (!q.empty()) {
int here = q.front();
q.pop();
for (int i = 0; i < digits.size(); i++) {
int there = append(here, digits[i] - '0', n);
// there이 될수 있는 가장 빠른(장난감 수가 제일 적은) 경우 하나만 고려해도 됨
if (parent[there] == -1) {
parent[there] = here;
choice[there] = digits[i] - '0';
q.push(there);
}
}
}
// 장난감 갯수가 n+m이상이고 나머지가 m인 경우가 없음
if (parent[n + m] == -1)return "IMPOSSIBLE";
// 부모로 가는 연결을 따라가면서 C를 계산
string ret;
int here = n + m;
while (parent[here] != here) {
ret += char('0' + choice[here]);
here = parent[here];
}
reverse(ret.begin(), ret.end());
return ret;
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
string str;
cin >> str >> n >> m;
cout << gifts(str) << endl;
}
}
view raw algospot 어린이날 (문제 ID: CHILDRENDAY).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/29.%20BFS/CHILDRENDAY.cpp

 

GitHub - sbl133/JongmanBook

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

github.com

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

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

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

algospot 신호 라우팅 (문제 ID: ROUTING) c++  (0) 2021.10.29
algospot 하노이의 탑 (문제 ID: HANOI4B) c++  (0) 2021.10.29
algospot Sorting Game(문제 ID: SORTGAME) c++  (0) 2021.10.27
algospot 단어 제한 끝말잇기 (문제 ID: WORDCHAIN) c++  (0) 2021.10.22
algospot 고대어 사전 (문제 ID: DICTIONARY) c++  (0) 2021.10.21

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

 

algospot.com :: SORTGAME

Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다.

algospot.com

중복이 없는 정수 수열에 임의의 구간을 선택해서 뒤집는 작업을 반복하여 수열을 정렬시킨다 했을때 필요한 최소 뒤집기 횟수를 구하는 문제이다.

 

상대적 크기가 같은 배열의 최소 뒤집기 횟수는 같다.

예를들어 {1, 3, 2, 4}와 {10, 30, 20, 40}의 최소 뒤집기 횟수는 같다. 따라서 크기가 n인 수열은 원소가 1~n인 경우만 고려하면 된다.

수열의 배치가 다른 각각의 경우의 수는 n!이므로 n!개의 정점과 현재 상태에서 뒤집기 한번 했을때의 수열이 서로 연결된 형태의 그래프를 이용하여 문제를 풀 수 있다.

이때 테스트케이스의 최대가 1000이므로 크기가 1~n인 경우들의 최소 뒤집기 횟수들을 미리 구해놓는다.

 

#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
// toSort[vector] = vector를 정렬시키는데 필요한 뒤집기 횟수
map<vector<int>, int> toSort;
// 크기가 n인 배열이 배치될수 있는 모든 경우의 뒤집기 횟수 계산
void precalc(int n) {
vector<int> perm(n);
for (int i = 0; i < n; i++)
perm[i] = i;
queue<vector<int>> q;
q.push(perm);
toSort[perm] = 0;
while (!q.empty()) {
vector<int> here = q.front();
q.pop();
// 현재 비용
int cost = toSort[here];
// 모든 뒤집기 상황 고려
for(int i=0; i<n; i++)
for (int j = i + 2; j <= n; j++) {
reverse(here.begin() + i, here.begin() + j);
// 배열을 뒤집었을때 아직 계산이 안된 배열이면
if (toSort.count(here) == 0) {
// 현재 배열 비용에 +1
toSort[here] = cost + 1;
q.push(here);
}
// 배열 원상복구
reverse(here.begin() + i, here.begin() + j);
}
}
}
// 상대적 크기만 고려하면 되므로 입력으로 주어진 perm을 정규화 시킨후 toSort에서 찾기
int solve(const vector<int>& perm) {
int n = perm.size();
vector<int> fixed(n);
for (int i = 0; i < n; i++) {
int smaller = 0;
for (int j = 0; j < n; j++)
if (perm[j] < perm[i])
smaller++;
fixed[i] = smaller;
}
return toSort[fixed];
}
int main() {
for (int i = 1; i <= 8; i++)
precalc(i);
int testcase;
cin >> testcase;
while (testcase--) {
int n;
cin >> n;
vector<int> v;
int tmp;
for (int i = 0; i < n; i++) {
cin >> tmp;
v.push_back(tmp);
}
cout << solve(v) << endl;
}
}
view raw algospot Sorting Game(문제 ID: SORTGAME).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/29.%20BFS/SORTGAME.cpp

 

GitHub - sbl133/JongmanBook

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

github.com

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

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

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

algospot 하노이의 탑 (문제 ID: HANOI4B) c++  (0) 2021.10.29
algospot 어린이날 (문제 ID: CHILDRENDAY) c++  (0) 2021.10.28
algospot 단어 제한 끝말잇기 (문제 ID: WORDCHAIN) c++  (0) 2021.10.22
algospot 고대어 사전 (문제 ID: DICTIONARY) c++  (0) 2021.10.21
algospot 에디터 전쟁 (문제 ID: EDITORWARS) c++  (0) 2021.10.18

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

 

algospot.com :: WORDCHAIN

단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이

www.algospot.com

입력된 단어들을 한번씩만 사용하여 끝말잇기를 한다.

모든 단어를 사용하여 게임이 끝날 수 있는 경우 어떤 순서로 단어를 사용해야 하는지 출력하는 문제이다.

만약 모든 단어를 사용하고 게임이 끝나느 경우가 없다면 IMPOSSIBLE를 출력한다.

 

알파벳 26개를 정점으로 하는 그래프에서 각 단어의 시작 알파벳을 나오는 방향, 끝나는 알파벳을 들어가는 방향으로 하는 간선을 추가한다.

그래프를 생성한 후에 오일러 서킷/트레일을 이용하여 각 간선의 방문순서를 기록한다.

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// 그래프의 인접 행렬 표현. adj[i][j]=i와 j사이의 간선의 수
vector<vector<int>> adj;
// graph[i][j] = i로 시작해서 j로 끝나는 단어의 목록
vector<string>graph[26][26];
// indegree[i]=i로 시작하는 단어의 수
// outdegree[i]=i로 끝나는 단어의 수
vector<int> indegree, outdegree;
void makeGraph(const vector<string>& words) {
// 전역변수 초기화
for (int i = 0; i < 26; i++)
for (int j = 0; j < 26; j++)
graph[i][j].clear();
adj = vector<vector<int>>(26, vector<int>(26, 0));
indegree = outdegree = vector<int>(26, 0);
// 주어진 단어들을 그래프에 추가
for (int i = 0; i < words.size(); i++) {
int a = words[i][0] - 'a';
int b = words[i][words[i].length() - 1] - 'a';
graph[a][b].push_back(words[i]);
adj[a][b]++;
outdegree[a]++;
indegree[b]++;
}
}
// 유향 그래프의 인접 행렬 adj가 주어질 때 오일러 서킷 혹은 트레일 계산
void getEulerCircuit(int here, vector<int>& circuit) {
for (int there = 0; there < adj.size(); there++)
while (adj[here][there] > 0) {
adj[here][there]--;
getEulerCircuit(there, circuit);
}
// push를 마지막에 함으로써 한 정점에 나가는 간선이 여러개여도
// 방문 순서가 꼬이지 않게 circuit을 거꾸로 구성
circuit.push_back(here);
}
// 현재 그래프의 오일러 트레일이나 서킷을 반환
vector<int> getEulerTrailOrCircuit() {
vector<int> circuit;
// 그래프의 형태가 트레일이면 시작점에서 순환 시작
for(int i=0; i<26; i++)
if (outdegree[i] == indegree[i] + 1) {
getEulerCircuit(i, circuit);
return circuit;
}
// 트레일이 아니면 서킷이니, 아무 정점에서나 시작
for(int i=0; i<26; i++)
if (outdegree[i]) {
getEulerCircuit(i, circuit);
return circuit;
}
// 모두 실패한경우 빈 배열 반환
return circuit;
}
// 현재 그래프의 오일러 서킷/트레일 존재 여부를 확인
bool checkEuler() {
// 트레일의 경우 시작점과 끝점이 하나씩인지 체크
int plus1 = 0, minus1 = 0;
for (int i = 0; i < 26; i++) {
// 각 정점의 차수 계산
int delta = outdegree[i] - indegree[i];
if (delta < -1 || 1 < delta) return false;
if (delta == 1)plus1++;
if (delta == -1)minus1++;
}
return (plus1 == 1 && minus1 == 1) || (plus1 == 0 && minus1 == 0);
}
string solve(const vector<string>& words) {
makeGraph(words);
if (!checkEuler())return "IMPOSSIBLE";
// 오일러 서킷이나 경로 탐색
vector<int> circuit = getEulerTrailOrCircuit();
// 모든 간선을 다 들렸으면, 방문한 정점의 수가 모든 간선의 수보다 1많아야 된다.
if (circuit.size() != words.size() + 1) return "IMPOSSIBLE";
// 거꾸로 circuit채운거 다시 뒤집기
reverse(circuit.begin(), circuit.end());
string ret;
for (int i = 1; i < circuit.size(); i++) {
int a = circuit[i - 1], b = circuit[i];
if (ret.size())ret += " ";
ret += graph[a][b].back();
graph[a][b].pop_back();
}
return ret;
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
int wordNum;
vector<string> words;
string str;
cin >> wordNum;
for (int i = 0; i < wordNum; i++) {
cin >> str;
words.push_back(str);
}
cout << solve(words) << endl;
}
}
view raw algospot 단어 제한 끝말잇기 (문제 ID: WORDCHAIN).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/28.%20DFS/WORDCHAIN.cpp

 

GitHub - sbl133/JongmanBook

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

github.com

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

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

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

algospot 어린이날 (문제 ID: CHILDRENDAY) c++  (0) 2021.10.28
algospot Sorting Game(문제 ID: SORTGAME) c++  (0) 2021.10.27
algospot 고대어 사전 (문제 ID: DICTIONARY) c++  (0) 2021.10.21
algospot 에디터 전쟁 (문제 ID: EDITORWARS) c++  (0) 2021.10.18
algospot 삽입 정렬 시간 재기 (문제 ID: MEASURETIME)c++  (0) 2021.10.15

+ Recent posts

티스토리툴바