한국공학대학교 S/W 경진대회 예선 후기
- 기타
- 2020년 10월 16일
학교공부에 치여 살다보니 알고리즘 문제 풀이를 안한지 3달정도가 지났는 데 학교 엘레베이터에 위와 같은 코테 포스터가 붙여진 것을 보았는데 실력 테스트도 해보고 상금도 노릴겸 해서 겸사겸사 신청을 했다.
대회 시상관련은 본선 진출시 기념품과, 대상 1명 50만원, 우수상 7명 30만원, 장려상 15명 10만원이었다.
사실 예선 통과후 본선에 들면 40명중 절반 이상인 23명안에만 들어도 10만원의 상금을 준다는 것을 보고 10만원을 목표로 신청했다.
예선전은 2020. 10. 07. 수요일에 18:00 ~ 22:00 까지 온라인을 통해 이루어졌는데 나는 수요일 당일 20시까지 수업이 있어 늦게 시작해야했는데, 수업이 조금 일찍 끝나 20시쯤 부터 문제풀이를 시작했기때문에 두시간 밖에 없어 떨어질 생각하고 편하게 테스트 봤다.
예선전 문제
1) 다음 순열
Description
1, 2,…,n의 모든 순열을 출력하는 프로그램을 작성하는 것은 흥미로운 연습입니다.
그러나 1, 2,…, 13의 순열의 개수가 6227020800이므로 10보다 큰 크기의 입력에서 모든 순열을 출력하기는 어렵습니다.
그러나 여기에 또 다른 흥미로운 순열 문제가 있습니다.
사전 순서로 1, 2,…,n순열을 정렬 할 수 있습니다.
다음은 사전 순으로 1,2,3의 순열입니다.
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
1,2,…,n의 순열이 주어지면 사전 순으로 다음 순열을 생성합니다.
예를 들어2 3 1 4의경우 답은2 3 4 1입니다.
Input
입력의 첫 번째 줄에는 두 개의 정수N및K가 포함됩니다.
그 뒤에는각각 1, 2,…,N의순열을 포함하는K개줄이 이어집니다.
1 ≤N≤ 1000,K≤ 10 입니다.
Output
출력은K개줄로구성되어야합니다.
i번째 줄은입력i+1번째순열에 해당하는 사전 식 다음 순열을 포함해야합니다.
Sample Input 1
3 2
3 1 2
2 3 1
Sample Output 1
3 2 1
3 1 2
1번 문제는 다음 순서로 올 순열을 출력하는 쉬운 문제여서 next_permutation 함수를 이용하여 쉽게 풀 수 있었다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int N,K;
cin >> N >> K;
vector<vector<int>> arr(K,vector<int>(N,0));
for(int i=0; i <K;i++){
for(int j=0; j < N; j++){
cin >> arr[i][j];
}
}
for(int i=0; i < K; i++){
next_permutation(arr[i].begin(),arr[i].end());
}
for(int i=0; i < K; i++){
for(int j=0; j < N ; j++){
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
}
2️) 베스트 앨범
Description
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
속한 노래가 많이 재생된 장르를 먼저 수록합니다.
장르 내에서 많이 재생된 노래를 먼저 수록합니다.
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 genre와 노래별 재생 횟수를 나타내는 정수 play가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 출력하도록 하세요.
Input
입력의 첫번째 줄에서 노래의 갯수 N이 주어집니다.
그 다음 N개 줄에는 각 줄마다노래의 장르를 나타내는 문자열 genre와 노래별 재생 횟수를 나타내는 정수 play가 주어집니다.
제한사항
i+1번째 줄의 문자열 genre는 고유번호가 i인 노래의 장르입니다.
i+1번째 줄의 재생 횟수 play는 고유번호가 i인 노래가 재생된 횟수입니다.
1<=N<=10,000
장르 종류는 100개 미만입니다.
장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
모든 장르는 재생된 횟수가 다릅니다.
Output
베스트 앨범에 들어갈 노래의 고유 번호를 한 줄에 하나씩 순서대로 출력하세요.
입력의 예가 다음과 같으면
5
classic 500
pop 600
classic 150
classic 800
pop 2500
classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.
고유 번호 3: 800회 재생
고유 번호 0: 500회 재생
고유 번호 2: 150회 재생
pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.
고유 번호 4: 2,500회 재생
고유 번호 1: 600회 재생
따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.
Sample Input 1
5
classic 500
pop 600
classic 150
classic 800
pop 2500
Sample Output 1
4
1
3
0
2번 문제는 블로그에도 한번 포스팅했던 프로그래머스의 베스트 앨범 문제였다.
프로그래머스에서도 풀어보고 포스팅하면서 다시 풀어보고 여러번 풀어봤던 문제였기에, map(hash table) 을 이용하여 값을 더해주고 value를 기준으로 내림차순 정렬하여 값을 출력하는 방법으로 쉽게 풀이 했다.
Note
c++ 에서 map을 key가 아닌 value로 정렬을 쉽게 하는 방법은 pair을 갖는 vector로 옮겨 vector로 정렬 하는 방법이 있습니다.
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
bool compare(pair<int,int> a,pair<int,int> b){
return a.first > b.first;
}
bool compare_map_value(pair<string,int> a,pair<string,int> b){
return a.second > b.second;
}
int main() {
int N; cin >> N;
vector<string> genres(N,"");
vector<int> plays(N,0);
for(int i=0; i < N; i++){
cin >> genres[i] >> plays[i];
}
unordered_map<string,vector<pair<int,int>>> genre_playlist;
unordered_map<string,int> genre_play_cnt;
vector<pair<string,int>> genre_play_cnt_v;
for(int i=0; i < genres.size(); i++){
genre_playlist[genres[i]].push_back(make_pair(plays[i],i));
genre_play_cnt[genres[i]]+=plays[i];
}
for(auto &k : genre_playlist){
sort(k.second.begin(),k.second.end(),compare);
}
genre_play_cnt_v.assign(genre_play_cnt.begin(),genre_play_cnt.end());
sort(genre_play_cnt_v.begin(),genre_play_cnt_v.end(),compare_map_value);
for(int i=0; i < genre_play_cnt_v.size(); i++){
string genre_name = genre_play_cnt_v[i].first;
for(int j=0; (j < genre_playlist[genre_name].size() ) && (j < 2) ; j++){
cout << genre_playlist[genre_name][j].second <<endl;
}
}
}
3) 등교길
Description
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다.
집에서 학교까지 가는 길은 너비 (m) x 높이 (n) 크기의 격자모양으로 나타낼 수 있습니다.
아래 그림은 m = 4, n = 3 인 경우입니다.
가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.
입력으로 격자의 너비 m, 높이 n과 물이 잠긴 지역의 좌표 (x,y)를 담은 2차원 배열 puddles이 주어집니다.
집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 출력하세요.
제한사항
격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
물에 잠긴 지역은 0개 이상 10개 이하입니다.
집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.
입력의 예로써 너비 m=4, 높이 n=3이고 puddles 배열은 [[2,2]] 가 주어지면 최단 경로의 개수는 아래의 그림과 같이 4입니다.
Input
입력의 첫번째 줄에서는 격자의 너비 m과 높이 n이 주어집니다.
두번째 줄에는 puddles 배열의 개수 N이 주어집니다.
이어지는 N개 줄에는 각 줄마다 물웅덩이 x좌표와 y좌표가 주어집니다.
Output
집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 출력하세요.
Sample Input 1
4 3
1
2 2
Sample Output 1
4
문제 설명 마지막에 친절하게도 hint로 dp를 이용하여 풀라고 설명이 되어 있어 dp를 이용해 풀었으며, 중학교 수학문제의 확률과 통계에서 최단 거리 경우의 수 문제를 풀듯이 풀었다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main(){
int m,n; cin >> m >> n;
int N; cin >> N;
vector<vector<int>> puddles(N,vector<int>(2,0));
for(int i=0; i < N; i++){
for(int j=0; j < 2; j++){
cin >> puddles[i][j];
}
}
vector<vector<bool>> map(n+1,vector<bool>(m+1,false));
vector<vector<int>> dis(n+1,vector<int>(m+1,0));
for(auto puddle : puddles)
map[puddle[1]][puddle[0]] = true;
dis[0][1] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m ; j++){
if(!map[i][j])
dis[i][j] = (dis[i-1][j] %1000000007 + dis[i][j-1] % 1000000007) % 1000000007;
else dis[i][j] = 0;
}
}
cout << dis[n][m] % 1000000007;
}
4️) 토큰 기계
Description
M개의 서로 다른기계와 T 종류의 토큰이 있습니다. 각각의 기계는 다음과 같이 1개의 토큰을 입력받아서 1개의 토큰과 다음 기계 번호를 출력합니다.
기계 입력 : T 종류의 토큰 중에서 1개 토큰
기계 출력 : T 종류의 토큰 중에서 1개 토큰과 다음 기계번호 출력
이전 기계에서 출력한 토큰을 다음 기계에 넣으면 다음 기계도 토큰 1개와 다음 기계 번호를 출력합니다.
예를 들어, 3개의 기계와 2가지 종류의 토큰이 있고 기계에 대한 설명이 다음과 같다고 합니다.
당신이 처음에 토큰 T1을 기계 M1에 넣기 시작하면, 방문하는 기계의 순서는 M1, M2, M3, M1, M2, M3, ... 이다. 따라서 4번째 방문 기계는 M1이고 5번째 방문 기계는 M2 입니다.
당신이 할일은 M개 기계와 T종류 토큰이 있을 때, S 번호 기계에서 시작해서 N번째 방문하는 기계 번호를 출력합니다. 시작은 1번 토큰에서 시작합니다.
Input
입력의 첫번째 줄에는 M (기계 개수 1...M), T (토큰의 종류 1...T), S (시작 기계 번호), N (N번째 방문) 이 주어 집니다.
그 다음 M x T 개의 줄에는 각각 2개의 정수가 주어 집니다. M개 기계에 대해서 T개의 토큰의 입력에 대한 출력을 차례로 설명합니다.
즉 입력의 2번째 줄에는 1번 기계에 1번 토큰을 삽입하면 출력되는 토큰 번호와 다음 기계 번호가 주어집니다.
입력의 3번째 줄에는 1번 기계에 2번 토큰을 삽입하면 출력되는 토큰 번호와 다음 기계 번호가 주어집니다.
(m-1)×T+i+1 (1 ≤m≤M, 1 ≤i≤T) 번째 줄에는 m번 기계에 i번 토큰을 삽입하면 출력되는 토큰 번호와 다음 기계 번호가 주어집니다.
1 ≤M≤ 200, 1 ≤T≤ 20,N≤ 1000000000 입니다.
입력의 50% 는N≤ 1000000 입니다.
Output
N번째 방문하는 기계 번호를 출력합니다.
시작은 1번 토큰에서 시작합니다
Sample Input 1
3 2 1 4
2 2
1 2
1 3
2 3
1 1
2 1
Sample Output 1
1
이때 시간이 40분도 채 남지 않았는 데, 문제는 3문제가 남아 있어 선택을 해야하는 상황이 왔었다.
그래서 남은 세 문제중 한 문제만 더 풀자 하고 가장 통과율이 높은 마지막 문제를 선택했기 때문에, 4,5 번은 문제는 보지도 못했다..
5️) 사회적 거리두기 1
Description
전세계적으로 퍼진 신종 코로나-19 감염병 예방을 위해서 김교수는 중간고사에서 사회적 거리두기를 시행하려고 합니다.
일렬로 배치된 N (2≤N≤10^5)개의 책상에 중간고사를 보기위한 학생들이 중간 중간에 앉아 있습니다. 어떤 책상은 학생들이 앉아있고 어떤 책상은 비어 있습니다.
새로운 학생 2명이 중간고사를 보기 위해서 책상에 앉으려고 합니다. 김교수는 사회적 거리두기를 시행하기 위해서 가장 가까운 학생간의 거리, D가 최대가 되도록 신규 학생 2명의 배치를 하려고 합니다.
김교수는 이미 자리에 앉아 있는 학생들은 자리 이동을 허락하지 않습니다.
Input
입력의 첫번째 줄에는 책상 개수 N을 포함합니다.
두번째 줄에는 학생들의 책상 점유 상태를 나타내는 길이가 N인 0과 1로 이루어진 숫자의 나열이 나옵니다. 0은 학생이 없고 1은 학생이 앉아 있는 것을 나타냅니다. 2개 이상의 0을 포함하므로 2명의 신규 학생을 수용할 충분한 공간이 있습니다.
Output
새로운 학생 2명을 배치한 후에 가장 가까운 학생간 거리, D의 최대값을 출력하십시오.
입력의 예가 다음과 같다고 가정합시다.
18
100000100100000010
그러면 새로운 학생 배치를 x로 표시해서 다음과 같이 배치할 수 있습니다.
100x00100100x00010
이러한 배치의 경우에 D의 최대값은 3가 됩니다.
또 다른 입력의 예가 다음과 같다고 가정합시다.
6
000000
그러면 새로운 학생 배치를 x로 표시해서 다음과 같이 배치할 수 있습니다.
x0000x
이러한 배치의 경우에 D의 최대값은 5가 됩니다.
Sample Input 1
18
100000100100000010
Sample Output 1
3
Sample Input 2
6
000000
Sample Output 2
5
6️) 마우스 미로
Description
미로는 사각형 격자 셀들로 구성되어 있습니다. 미로 안에 일부 셀은 차단되어 있고 나머지 셀들은 비어 있습니다.
마우스(Mouse)는 M으로 표시된 빈 셀 중 하나에서 시작하고 D로 표시된 목적지 셀까지 이동하려고 합니다.
셀에서 마우스는 아래 주어진 규칙에 따라 빈 이웃 셀로 이동할 수 있습니다.
당신의 목표는 마우스가 이 미로를 통과하여 목적지 셀(D)에 도달 할 수 있는지를 결정하는 것입니다.
R 행과 C 열이있는 미로는 각각 C개의 문자가있는 일련의 R 행으로 표시됩니다.
문자 # 은 차단 된 셀을 나타내고 문자 . 은 빈 셀을 나타냅니다.
마우스 시작 셀(M)과 목적지 셀(D)는 별개의 빈 셀에 있습니다.
다음은 7 행 11 열의 미로입니다.
#####..####
.M.#.#..D.#
#.#..#....#
...#.#..#..
....#.#.#.#
...##.###.#
........###
행과 열 위치로 셀을 참조합니다. 행은 위에서 아래로 번호가 매겨지고 열은 왼쪽에서 오른쪽으로 번호가 매겨집니다.
예를 들어, 위의 미로에서 마우스는 처음에 두 번째 행과 두 번째 열을 나타내는 위치 (2,2)에 배치되고 목적지 셀은 두 번째 행과 열 번째 열을 나타내는 위치 (2,9)에 있습니다.
마우스는 셀에서 셀 위쪽, 아래쪽, 왼쪽 또는 오른쪽으로 이동할 수 있습니다.
또한, 가장 왼쪽 열의 셀에서 마우스는 가장 오른쪽 열의 동일한 행에 있는 셀로 이동할 수 있으며 가장 오른쪽 열의 셀에서 가장 왼쪽 열의 같은 행에있는 셀로 이동할 수 있습니다.
마찬가지로 맨 위 행의 셀에서 마우스는 맨 아래 행의 동일한 열에있는 셀로 이동할 수 있고 맨 아래 행의 셀에서 맨 위 행의 같은 열에있는 셀로 이동할 수 있습니다.
따라서 위의 미로에서 마우스는 셀 (4,1)로 부터 (4,11)로 이동할 수 있고, 셀 (7,7)로 부터 (1,7)으로 이동할 수 있습니다.
위의 예에서, 마우스는 (2,2), (3,2), (4,2), (4,1), (4,11), (4,10), (3,10), (3,9), (2,9)와 같은 일련의 셀들을 통해 목적지에 도달 할 수 있습니다.
이 경로에는 아래에 x가 표시되어 있습니다.
#####..####
.M.#.#..D.#
#x#..#..xx#
xx.#.#..#xx
....#.#.#.#
...##.###.#
........###
또한 다른 경로를 다음과 같이 나타낼 수도 있습니다.
#####.x####
.M.#.#xxD.#
#x#..#....#
.x.#.#..#..
.x..#.#.#.#
.x.##.###.#
.xxxxxx.###
당신의 임무는 마우스가 목적지에 도달 할 수 있는지 여부를 결정하는 것입니다.
Input
입력의 첫 번째 줄에는 각각 행 및 열을 나타내는 두 개의 숫자 R과 C가 포함됩니다.
그 다음 줄 부터는 각각 C개 문자가 있는 R 행이 있으며, 각 줄은 # 또는 . 또는 M 또는 D 문자를 갖는다.
M과 D는 정확히 한개 씩만 있습니다.
R≤ 1000,C≤ 1000 로 가정합니다.
Output
마우스가 목적지까지 가는 경로가 없으면 NO라는 단어가 포함 된 한 줄을 인쇄하십시오.
마우스가 목적지까지 가는 경로가 있는 경우 출력의 첫 번째 행은 단어 YES로 구성되어야합니다.
그 뒤에는 각각 C 문자의 R 행이 있어야합니다.
여기서 각 문자는 # 또는 . 또는 x 또는 M 또는 D 입니다.
상기 예시 된 바와 같이 x 를 사용하여 M에서 D 로의 경로를 설명합니다.
많은 경로가 있을 수 있으며 하나의 경로를 설명하면 충분합니다.
Sample Input 1
7 11
#####..####
.M.#.#..D.#
#.#..#....#
...#.#..#..
....#.#.#.#
...##.###.#
........###
Sample Output 1
YES
#####..####
.M.#.#..D.#
#x#..#..xx#
xx.#.#..#xx
....#.#.#.#
...##.###.#
........###
Sample Input 2
4 6
##.#..
.M.#.#
#.#.D.
...#.#
Sample Output 2
NO
시간안에 한두개 케이스라도 통과해보자는 마음으로 문제 풀이를 시작 했고, 최단 경로가 있는지 없는지 검사만 하는것이 아니라 최단 경로까지의 길을 x로 출력해야 해서 bfs로는 최단 경로에 포함되지 않은 길은 x표시를 제외하려고 하면 복잡해질 것 같아 dfs로 풀이를 시작했다.
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
을 이용했으며, 제일 끝 쪽 벽이 막혀있는 것이 아니라 다음 벽으로 이어져 있기 때문에 현재 위치에서 dir값과 총 배열 길이(x축이면 C,y축이면 R)을 더하고 배열 길이만큼 나눈 나머지를 이용하여 dfs를 풀이했다.
int next_x = (x + dir[i][0] + C) % C;
int next_y = (y + dir[i][1] + R) % R;
하지만, 마음이 급했는 지 **==**을 **=**로 잘못쓰는 등 잔실수들 때문에 버그 고치느라 타임아웃되어 제출을 하지 못하고 예선이 끝났다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int R, C;
int M_x, M_y;
int D_x, D_y;
bool arrive = false;
vector<vector<char>> answer;
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void dfs(vector<vector<char>> map, vector<vector<bool>> &visit, int x, int y)
{
if (y == D_y && x == D_x){
arrive = true;
answer = map;
return;
}
if (map[y][x] != 'M')
map[y][x] = 'x';
visit[y][x] = true;
for (int i = 0; i < 4; i++){
int next_x = (x + dir[i][0] + C) % C;
int next_y = (y + dir[i][1] + R) % R;
if ((map[next_y][next_x] == '.' || map[next_y][next_x] == 'D') && visit[next_y][next_x] == false){
visit[next_y][next_x] == true;
dfs(map, visit, next_x, next_y);
}
}
return;
}
int main()
{
cin >> R >> C;
vector<vector<char>> arr(R, vector<char>(C, '0'));
vector<vector<bool>> visit(R, vector<bool>(C, false));
string str;
for (int i = 0; i < R; i++){
int j = 0;
cin >> str;
for (auto c : str){
arr[i][j] = c;
if (arr[i][j] == 'M'){
M_x = j;
M_y = i;
}
if (arr[i][j] == 'D'){
D_x = j;
D_y = i;
}
j++;
}
}
dfs(arr, visit, M_x, M_y);
if (arrive){
cout << "YES" << endl;
for (int i = 0; i < answer.size(); i++){
for (int j = 0; j < answer[i].size(); j++){
cout << answer[i][j];
}
cout << endl;
}
}
else{
cout << "NO";
}
return 0;
}
예선전 후기
10시에 칼같이 시험이 끝나고 바로 점수가 집계되었는데, 총 점 120점 만점에 40점으로 16등으로 통과했다.(생각도 못했는데 이게 웬 걸)
늦게 시작했지만 예선 통과해서 좋았고, 1등은 108점으로 19학번이 한것을 보고 대단하다는 생각과 동시에 자괴감이 들었으며, 총원과 점수들을 보니 생각보다 많은 사람이 참여를 안했구나 싶었다.
Tip
그래서 덕분에 40점을 받아 16등으로 예선을 통과했다. 😄
본선 후기는 다음글에 이어서 포스팅 할 예정이다.
