제1회 류호석배 알고리즘 코딩 테스트

운이 좋게 류호석님이 준비하신 코딩 테스트에 검수자로 참여했습니다.

소마 11기 활동을 하면서 검수활동을 시작해보려 했는데 호석님이 절 검수자로 뽑아주셔서 참여하게 되었습니다. 

검수는 거의 처음이라 잘 해낼 수 있을지 걱정이 되었지만 하기 쉬운것부터 하나씩 했습니다. 골목 대장 호석 문제의 정해가 이분탐색 + 다익스트라인데 옛날에 최단경로에서 잘못짠 다익스트라로 고통을 받은 기억이 떠올라 다른 분들 소스코드를 보고 그 데이터가 없어서 추가하는 것부터 시작했습니다. (하지만 커팅 등 다른 풀이는 생각못하고 있었네요.. )

문제를 보고 풀이 실수할만 부분들을 찾아 그 풀이가 통과되는지 등 데이터가 약하지는 않은지, 문제 지문 오류 등을 검수했습니다.

 

대회에 작은 이슈가 있었지만 이번 대회를 통해 검수할 방향이 어느정도 잡힌거 같습니다. 

 

Thanks to BaaaaaaaaaaarkingDog dlstj0923 rhs0266

1. 홀수 홀릭 호석

알고리즘 분류 : 완전탐색, 구현

 

입력되는 수의 최대는 999,999,999이다. 문자열로 본다면 길이가 9이므로 문자열로 처리하여 완전탐색하면 됩니다.

 

#include<bits/stdc++.h>

#define siz(x) (int)(x).size()

using namespace std;

int ansmx, ansmn = INT_MAX;
int getOddCount(int x){
    int res = 0;
    while(x){
        res += x % 2;
        x /= 10;
    }
    return res;
}

void dfs(int x, int cnt){
    cnt += getOddCount(x);

    if(x < 10){
        ansmx = max(ansmx, cnt);
        ansmn = min(ansmn, cnt); 
        return;
    }
    else if(x < 100)dfs(x % 10 + x / 10, cnt);
    else{
        string str = to_string(x);
        for(int i=1;i<siz(str)-1;i++){
            for(int j=i+1;j<siz(str);j++){
                string l = str.substr(0, i);
                string m = str.substr(i, j - i);
                string r = str.substr(j); 
                dfs(stoi(l) + stoi(m) + stoi(r), cnt);
            }
        }
    }
}

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

    int x;cin >> x;
    dfs(x, 0);
    cout << ansmn << ' ' << ansmx;
    
    return 0;
}

2. 인내의 도미노 장인 호석

알고리즘 분류 : 시뮬레이션, 구현

 

이 문제도 지문에 있는 그대로 하나씩 구현하면 됩니다.

 

#include<bits/stdc++.h>

#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define FOR(i,s,e) for(int i=s;i<=e;i++)
#define FORI(i,s,e,d) for(int i=s;i<=e;i+=d)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int dy[] = {-1,1,0,0,-1,-1,1,1};
const int dx[] = {0,0,-1,1,-1,1,-1,1};
// N S W E

const ll MOD = 1e9 + 7;

int Map[101][101];
bool used[101][101];

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

    int n, m, r; cin >> n >> m >> r;
    int ans = 0;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin >> Map[i][j];
    for(int i=0;i<r;i++){
        int y, x; char u; cin >> y >> x >> u;
        int dir;
        if(u == 'N')dir = 0;
        if(u == 'S')dir = 1;
        if(u == 'W')dir = 2;
        if(u == 'E')dir = 3;
        y--; x--;

        int t = 1, score = 0;
        while(t){
            if(!used[y][x]){
                t = max(Map[y][x], t);
                score++;
            }
            --t;
            used[y][x] = true;
            y += dy[dir];
            x += dx[dir];
            if(0 > y || y >= n || 0 > x || x >= m)break;
        }

        cin >> y >> x;
        y--; x--;
        used[y][x] = false;
        ans += score;
    }
    cout << ans << '\n';
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(used[i][j])cout << "F ";
            else cout << "S ";
        }
        cout << '\n';
    }
    
    return 0;
}

3. 문자열 지옥에 빠진 호석 

알고리즘 분류 : 트라이, 해시를 사용한 집합과 맵, 완전 탐색

 

DFS로 신이 좋아하는 문자열 길이를 1부터 5까지 선택을 하면 됩니다. 조심해야하는 부분은 (1, 1)에서 (1, N), (M, 1), (N, M)으로 다 갈 수 있습니다.

DFS로 돌면서 선택되는 문자열이 몇개 있는지 파악해놓고 쿼리가 들어오면 그 문자열이 몇개 있었는지 출력하면 됩니다.

 

맨 처음에 신이 좋아하는 문자열이 몇개 있었는지 파악할 때 트라이를 이용해도 되고 map, unordered_map 등 편한 자료구조로 사용하면 됩니다.

 

 - 맵을 이용한 풀이

#include<bits/stdc++.h>

#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define FOR(i,s,e) for(int i=s;i<=e;i++)
#define FORI(i,s,e,d) for(int i=s;i<=e;i+=d)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int dy[] = {-1,1,0,0,-1,-1,1,1};
const int dx[] = {0,0,-1,1,-1,1,-1,1};

const ll MOD = 1e9 + 7;

string Map[11];
int n, m, k;
map<string, int> mp;
vector<string> v;
string cur;

void dfs(int y, int x){
    if(siz(cur) > 5)return;
    if(mp.count(cur))mp[cur]++;
    for(int i=0;i<8;i++){
        int qy = (y + dy[i] + n) % n;
        int qx = (x + dx[i] + m) % m;
        cur += Map[qy][qx];
        dfs(qy, qx);
        cur.pop_back();
    }
}

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

    cin >> n >> m >> k;
    for(int i=0;i<n;i++)cin >> Map[i];
    for(int i=0;i<k;i++){
        string str;cin >> str;
        mp[str] = 0;
        v.push_back(str);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cur += Map[i][j];
            dfs(i,j);
            cur.pop_back();
        }
    }
    for(auto &i: v)cout << mp[i] << '\n';
    return 0;
}

 

 - 트라이를 이용한 풀이

#include<bits/stdc++.h>

#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define FOR(i,s,e) for(int i=s;i<=e;i++)
#define FORI(i,s,e,d) for(int i=s;i<=e;i+=d)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int dy[] = {-1,1,0,0,-1,-1,1,1};
const int dx[] = {0,0,-1,1,-1,1,-1,1};

const ll MOD = 1e9 + 7;

struct Node{
    map<char, Node*> mp;
    char ch;
    int cnt, res;
    Node(char Ch=0, int Cnt=0):ch(Ch), cnt(Cnt), res(0) {}
    Node* next(char name, bool End=false){
        if(mp.count(name)){
            if(End)mp[name]->cnt++;
            return mp[name];
        }
        Node* newNode = new Node(name);
        if(End)newNode->cnt++;
        mp[name] = newNode;
        return newNode;
    }
    Node *findnext(char name){
        if(mp.count(name))return mp[name];
        return NULL;
    }
    void addCnt(int Cnt){ res += Cnt; }
    bool isEnd() { return cnt != 0; }
};

Node *trie;
char Map[11][11];
int n, m, k, ans;
vector<string> v;

void Input(string str){
    Node *now = trie;
    for(int i=0;i<siz(str);i++)now = now->next(str[i], i + 1 == siz(str));
    return;
}

void Search(const string &str){
    Node *now = trie;
    for(int i=0;i<siz(str);i++){
        Node *cur = now->findnext(str[i]); 
        if(cur == NULL)break;
        if(i == siz(str) - 1)cur->addCnt(1);
        now = cur;
    } 
}

void trace(int y, int x, string str=""){
    if(siz(str) > 5)return;
    Search(str);
    for(int i=0;i<8;i++){
        int qy = (y + dy[i] + n) % n;
        int qx = (x + dx[i] + m) % m;
        trace(qy,qx,str+Map[qy][qx]);
    }
}

int answer(const string &str){
    Node *now = trie;
    for(int i=0;i<siz(str);i++)now = now->findnext(str[i]);
    return now->res;
}

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

    cin >> n >> m >> k;
    trie = new Node();
    for(int i=0;i<n;i++) cin >> Map[i];
    for(int i=0;i<k;i++){
        string str;cin >> str;
        v.push_back(str);
        Input(str);
    }    

    for(int i=0;i<n;i++)for(int j=0;j<m;j++)trace(i,j,string("") + Map[i][j]);
    for(auto &i: v) cout << answer(i) << '\n';

    return 0;
}

 

 

4. 꿈틀꿈틀 호석 애벌레 (기능성, 효율성)

알고리즘 분류 : 두 포인터, 다이나믹 프로그래밍

[ 시간 복잡도 O (N) ]

 

원래 버전은 하나 조건이 더 있어서 난이도가 있었습니다. 하지만 문제 난이도가 어려운거 같아 그 조건을 빼기로 하였습니다. 

이 문제는 어느정도 난이도가 있는 문제입니다. (코딩테스트 기준) 아래 식을 세워서 코딩으로 잘 옮기면 되지만 이 식을 생각하기 살짝 힘들수 있습니다. 

 

 v[i]를 l부터 r까지 다 더할때 만족도가 k이상이 되는 순간에 멈춥니다. 예를 들어 배열 [ 1, 2, 3, 4, 5, 6, 7 ]이 있다고 가정을 하면 맨 처음부터 합이 15가 되는 순간까지 더한다고 하면 l은 0, r은 4가 됩니다.

 

구간 l부터 r까지 먹이를 문제 조건에 맞게 먹었을 때 축적된 탈피 에너지와 그 전에 쌓은 탈피 에너지 중 최대를 가지고 가면 됩니다. 이 에너지들은 r까지 갔을때의 탈피 에너지이므로 dp[r]에 최댓값을 갱신해주면 됩니다.

 

그리고 dp에 갱신된 값들 중 최대를 뽑으면 됩니다.

 

 

 - C++

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

ll dp[101101], v[101101], cur, mx;

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

    int n, k;cin >> n >> k;
    for(int i=1;i<=n;i++)cin >> v[i];
    int r = 0;
    for(int i=1;i<=n;i++){
        //1 ~ i - 1 max(dp[k]) ll 
        mx = max(mx, dp[i-1]);
        while(r <= n && cur < k)cur += v[r++];
        dp[r-1]=max(dp[r-1],mx+max(0LL,cur-k));
        cur -= v[i];
    }
    cout << *max_element(dp+1, dp+n+1);
    return 0;
}

 

- Python 3

import sys

input = sys.stdin.readline
N, K = map(int, input().split())
v  = [ 0 ] + list(map(int, input().split()))
dp = [ 0 for _ in range(N+1) ]

r, cur, mx = 0, 0, 0

for i in range(1, N+1):
    mx = max(mx, dp[i-1])
    while r <= N and cur < K:
        cur = cur + v[r]
        r += 1

    dp[r-1] = max(dp[r-1], mx + max(0, cur - K))
    cur = cur - v[i]

print(max(dp))

 

5. 골목 대장 호석 (기능성, 효율성 1, 효율성 2)

효율성 1

알고리즘 분류 : 다익스트라

[ 시간복잡도 O(20 M log N) ]

 

골목 별 수금액이 20밖에 안된다. 

골목 별 수금액 최대를 결정하면 되는 문제므로 1부터 20까지 다익스트라를 총 20번 돌리면 된다.

 

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define MAXN 100001
#define INF 0x3f3f3f3f3f3f3f3f

vector<pii> graph[MAXN];
ll S, E, C;

bool dijkstra(int mid){
    priority_queue<pll> pq;
    vector<ll> Cost(MAXN, INF);
    pq.push(pll(0, S));
    Cost[S] = 0; 

    while(!pq.empty()){
        auto [_c, cur] = pq.top(); pq.pop();
        if(Cost[cur] != -_c)continue;

        for(auto &[nxt, cost]: graph[cur]){
            if(cost > mid)continue;
            if(Cost[nxt] > Cost[cur] + cost){
                Cost[nxt] = Cost[cur] + cost;
                pq.push(pll(-Cost[nxt], nxt));
            }
        }
    }
    return Cost[E] <= C;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    
    int n, m; cin >> n >> m >> S >> E >> C;
    S--; E--;
    for(int i=0;i<m;i++){
        int a,b,c;cin >> a >> b >> c;
        graph[--a].emplace_back(--b, c);
        graph[b].emplace_back(a, c);
    }
    for(int i=1;i<=20;i++){
        if(!dijkstra(i))continue;
        cout << i;
        return 0;
    }
    cout << -1;
    
    return 0;
}

 

효율성 2

 

알고리즘 분류 : 이분탐색, 다익스트라

[ 시간복잡도 O(M log N log 10^9) ]

 

파이썬 때문에 검수할 때 가장 머리 아팠던 문제.... 코딩테스트는 파이썬으로 하시는 분들이 많아서 파이썬이 통과되도록 시간을 3초로 잡았지만 오늘 대회 전에 테스트를 해보니 시간초과가 떠서 5초로 늘렸습니다. 

 

골목의 수금액의 최댓값을 결정하고 다익스트라를 이용하여 A(출발)에서 골목의 수금액의 최대값 이하인 간선으로만 이동하여 B(도착)까지 C이하로 갈 수 있는지 판단하면 됩니다.

 

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define MAXN 100001
#define INF 0x3f3f3f3f3f3f3f3f

vector<pii> graph[MAXN];
ll S, E, C;

bool dijkstra(int mid){
    priority_queue<pll> pq;
    vector<ll> Cost(MAXN, INF);
    pq.push(pll(0, S));
    Cost[S] = 0; 

    while(!pq.empty()){
        auto [_c, cur] = pq.top(); pq.pop();
        if(Cost[cur] != -_c)continue;

        for(auto &[nxt, cost]: graph[cur]){
            if(cost > mid)continue;
            if(Cost[nxt] > Cost[cur] + cost){
                Cost[nxt] = Cost[cur] + cost;
                pq.push(pll(-Cost[nxt], nxt));
            }
        }
    }
    return Cost[E] <= C;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    
    int n, m; cin >> n >> m >> S >> E >> C;
    S--; E--;
    for(int i=0;i<m;i++){
        int a,b,c;cin >> a >> b >> c;
        graph[--a].emplace_back(--b, c);
        graph[b].emplace_back(a, c);
    }
    int L = 0, R = 1e9, ans = INT_MAX;
    while(L <= R){
        int mid = (L + R) / 2;
        if(dijkstra(mid)){
            ans = min(ans, mid);
            R = mid - 1;
        }
        else L = mid + 1;
    }
    if(ans == INT_MAX)ans = -1;
    cout << ans;
    
    return 0;
}