글쓴이 ·0개의 댓글

방학하고 게임하느라 독서량이 줄었다. 하지만 게임을 할 수록 경쟁전 점수도 줄고 있다. 방학 전에 읽은 책 중에 소개하고 싶은 것들도 많지만 타이밍을 놓쳐버린게 아쉽다. 작년에 미국에 있을 때 등교 시간에 페이스북 보는 것보다 조금이라도 의미 있게 시간을 보내야겠다는 생각에 e북을 읽기 시작했는데, 그게 이번 학기까지 이어져서 재밌는 책들을 많이 읽었다.

크림슨의 미궁

작년에 <신세계에서> 읽고 빠진 작가인데, 올해 제대로 덕질을 시작해서 유스케씨 책을 꾸준히 읽고 있다. 도서관에다 책 사달라고 신청도 하고 절판된 작품은 중고로 사 모아서 이제 도서관에 있는 책과 내가 소장하고 있는 책들을 모으면 유스케 작품이 전부 모인다. <크림슨의 미궁>은 다른 작품에 비해 오락성이 강했던 책으로 <헝거 게임> 같은 생존 서바이벌을 소재로 하고 있다. 나름대로 여운 있는 결말과 적절한 반전이 있었지만 유스케의 다른 명작들에 비해서는 주제의식이 가벼웠던 점이 살짝 아쉽다. 나중에 기시 유스케는 영업글을 한 번 쓸 예정.

오감도

이상의 시집. 예전부터 소문으로만 들어서 직접 읽어봐야겠다고 생각하다 도서관에서 발견했다. 한자가 많아서 절반 정도밖에 이해하지 못했다. 정신분열 걸리는 시라는 세간의 인식과는 달리 막상 읽어보니 괜찮은 시도 많았다. 특유의 소재와 문체가 어울려 몽환적인 분위기를 만듦. 한자를 한글로 쓴 판본이 있다면 다시 읽어보고 싶다. 모자랑 거울 나오는 시들이 특히 좋았다.

공부중독

창의설계 수업 마지막 시간에 나눠준 책. 공부가 유일한 길이라고 믿는 현재 한국 사회의 교육문화를 분석한 책이다. 흥미로운 부분 두 가지를 꼽자면 인성교육이나 픽업 아티스트 등 배움의 영역이 아닌 것들이 포장되고 상품화되어 공부 산업이 되어버렸다는 부분과, 공부를 한다는 핑계로 사회 진출을 미루는 사람이 늘었다는 부분이었다. 사회에 공부하는 사람만 필요한 것도 아닌데 모두가 공부만이 길이라고 믿는 건 이상한 현상이고, 이런 믿음은 많은 부작용을 낳으니 해결해야 한다는 것이 저자들의 주장이었다. 대중의 입장에서는 흥미롭고 설득력 있었지만, 내 주변에는 진짜 자기 길이 공부였던 사람이 많아서 일반화 당하는 듯한 기분이 살짝 있었다.

차회 예고

e북으로 <Crystal Society>를 읽고 있다. 강인공지능의 눈으로 바라본 인간 세상 이야기인데 영문에다가 엄청 길어서 언제 다 읽을 수 있을 지 모르겠다. AI에 관심 있는 사람들이 보면 진짜 재미있게 볼 수 있을거라 생각한다. 공짜니까 검색해서 받아 보시면 됩니다. 한강의 <채식주의자>는 <Crystal Society> 다 읽고 나서 읽으려고 e북을 사 놓기는 했는데 아마 근시일 내에는 읽지 못할 것 같다.

기시 유스케 작품을 열심히 읽어서 이제 <다크 존>이랑 <자물쇠가 잠긴 방> 두 개 남았다. <다크 존>을 먼저 읽을 예정이다.

PL 수업시간에 괴델, 튜링 등 수학자들 얘기 들었던게 너무 재밌어서 수학사 책도 읽고 있다. 고등학교 때 읽었던 <수학의 반전> 같은 느낌으로 수학자 소개와 연습 문제를 잘 섞어 놓은 책인데, 내가 원하던 방향성이랑은 약간 달랐지만 내용이 적당히 재밌어서 이것도 자기 전에 조금씩 읽고 있다.

글쓴이 ·0개의 댓글

도서관에서 빌렸던 <천사의 속삭임> 다 읽었다. 책의 마지막 장을 넘길 때 전율을 주체할 수 없었다. <말벌>은 이게 기시 유스케 작품이 맞나 싶을정도로 실망이었는데, 이건 정말 읽은 보람이 있는 작품이었다.

<신세계에서> 읽고 기시 유스케 입덕한지 1년이 좀 넘었다. 작가의 다른 소설들도 꽤 재밌었지만 신세계에서에 비할 바는 아니었는데 <천사의 속삭임>은 그에 비견할만한 작품이었다. 얼마나 재밌었는지 이렇게 바쁜 와중에도 3일만에 500쪽을 다 읽었다.

나는 기시 유스케의 강점들로 숨막히는 심리 묘사 및 효과적인 호러 분위기 전달, 철저한 사전조사를 통해 전문지식을 자연스레 드러내는 점, 색다른 소재, 뼈대 있는 메시지를 자연스레 전달한다는 점을 꼽는다. 이런 관점에서 <신세계에서>와 <천사의 속삭임>은 정말 최고였다. 나중에 작가 다른 작품들을 다 읽고 나서 한 번에 정리하는 소개 겸 영업글을 써야겠다.

꽤 징그러운 묘사가 자주 나오는데 비위 약한 사람은 읽기 전에 주의하셔야 할 듯 합니다.

글쓴이 ·0개의 댓글

시작할 때는 컨디션이 좋아서 빠르게 A, C를 풀었지만 B에서 삽질을 많이 하면서 4 WA(…)를 받았다. 심지어 system test에서 B Large가 나갔다. 436위로 마무리. R2 액땜했다고 생각하자.

A

ZERO, ONE, TWO, THREE, …, NINE으로 이루어진 아나그램을 주고, 각 숫자를 몇 번씩 사용했는지 출력하는 문제다. 0, 2, 4, 6, 8, 1, 5, 3, 7, 9 순서로 그리디하게 빼 주면 유일해를 쉽게 찾을 수 있다. 구조화를 잘못해서 코드를 몇 번 지우고 다시 짜서 문제 난이도에 비해 코딩이 오래 걸렸다.

A Code
#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAX = 2999;
using namespace std;

int countAlphabet[99], countDigit[10][99], usedDigit[10];

char * digitName[] = {
    "ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"
};

void countNumber(char * str) {
    for (int i = 0; str[i]; i++)
        countAlphabet[str[i] - 'A']++;
}

void greedyUse(int digit) {
    int maxUse = MAX;

    for (char abc = 'A'; abc <= 'Z'; abc++) {
        if (countDigit[digit][abc - 'A'])
            maxUse = min(maxUse, countAlphabet[abc - 'A'] / countDigit[digit][abc - 'A']);
    }

    usedDigit[digit] += maxUse;

    for (char abc = 'A'; abc <= 'Z'; abc++) {
        countAlphabet[abc - 'A'] -= maxUse * countDigit[digit][abc - 'A'];
    }
}

int main() {
    freopen("output.txt", "w", stdout);

    for (int i = 0; i < 10; i++) {
        for (int j = 0; digitName[i][j]; j++) {
            countDigit[i][digitName[i][j] - 'A']++;
        }
    }

    int numCase, nowCase;
    scanf("%d", &numCase);
    for (nowCase = 1; nowCase <= numCase; nowCase++) {
        memset(countAlphabet, 0, sizeof(countAlphabet));
        memset(usedDigit, 0, sizeof(usedDigit));

        char str[MAX];
        scanf("%s", str);

        countNumber(str);

        greedyUse(0); //Zero
        greedyUse(2); //tWo
        greedyUse(4); //foUr
        greedyUse(6); //siX
        greedyUse(8); //eiGht
        //absoulute greedy

        greedyUse(1); //One
        greedyUse(5); //Five
        greedyUse(3); //THRee
        greedyUse(7); //SeVen
        greedyUse(9); //NINE
        //relative greedy

        printf("Case #%d: ", nowCase);
        for (int digit = 0; digit < 10; digit++) {
            for (int i = 0; i < usedDigit[digit]; i++)
                printf("%d", digit);
        }
        puts("");
    }

    return 0;
}

26:58 AC

C

B가 내가 약한 문제 유형이라 C부터 풀기로 했다. string을 정점으로 변환한 뒤 이분 그래프에서 minimum vertex cover를 찾으면 된다. 이분매칭을 너무 오랜만에 짜서 검색하느라 오래 걸렸지만 문제 자체는 알면 쉽다.

C Code
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <vector>

const int MAX = 1020;
using namespace std;

int fCount, sCount;
map < string, int > fWord, sWord;

int n, crossS[MAX];
bool visitS[MAX];
vector < int > edges[MAX];

bool dfs(int f) {
    for (int s : edges[f]) {
        if (!visitS[s]) {
            visitS[s] = 1;

            if (crossS[s] < 0 || dfs(crossS[s])) {
                crossS[s] = f;
                return true;
            }
        }
    }

    return false;
}

int bipartiteMatch() {
    int ret = 0;

    memset(crossS, -1, sizeof(crossS));

    for (int f = 0; f < fCount; f++) {
        memset(visitS, 0, sizeof(visitS));

        if (dfs(f)) {
            ret++;
        }
    }

    return ret;
}

int main() {
    freopen("output.txt", "w", stdout);

    ios::sync_with_stdio(true);

    int numCase, nowCase;
    scanf("%d", &numCase);
    for (nowCase = 1; nowCase <= numCase; nowCase++) {
        fWord.clear();
        sWord.clear();
        for (int i = 0; i < fCount; i++)
            edges[i].clear();
        fCount = sCount = 0;

        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            string fStr, sStr;
            cin >> fStr >> sStr;

            int fIndex, sIndex;
            if (fWord.find(fStr) == fWord.end()) {
                fWord[fStr] = fCount;
                fIndex = fCount;
                fCount++;
            } else {
                fIndex = fWord[fStr];
            }
            if (sWord.find(sStr) == sWord.end()) {
                sWord[sStr] = sCount;
                sIndex = sCount;
                sCount++;
            } else {
                sIndex = sWord[sStr];
            }

            edges[fIndex].push_back(sIndex);
        }

        int numMatch = bipartiteMatch();

        printf("Case #%d: %d\n", nowCase, n - (fCount + sCount - numMatch));
    }

    return 0;
}

58:57 AC

B

내가 잘 풀지 못하는 유형이라 생각하고 넘기고 풀었는데, 정말로 잘 못 푸는 유형이라 4번의 오답 끝에 small을 맞출 수 있었다. Large는 푼 줄 알았는데 system test에서 틀렸다.

문자열 두 개 모두 ?가 아니면서 서로 다른 위치 중 가장 앞에 있는 위치를 찾는다. 존재하지 않는 경우는 두 점수를 동일하게 만들 수 있다. 존재하는 경우는 그 위치를 기준으로 뒤쪽은 모두 0 또는 9로 채우고, 앞쪽을 최대한 비슷하게 만들면 된다.

PL 수업을 수강하면서 코드 설계력이 좋아지고 버그를 내는 빈도가 줄었다고 생각하고 있었는데, B 코드는 확실히 설계는 잘 한 것 같은데 사소한 버그를 너무 많이 내서 슬펐다. 값 비교할 때 절댓값을 취하지 않는다든가, break을 잊었다든가 하는 실수를 4번이나 저질렀다고 한다…

아래 코드는 small만 통과한다. ??8? ?02?는 0989 1020가 나와야 하는데 0089 0029가 나온다. ‘앞 부분을 최대한 비슷하게’ 하는 방법이 틀렸음.

B Code
#include <cstdio>
#include <cstring>
#include <string>

const int MAX = 20;
using namespace std;
typedef long long ll;

void makeSame(char *a, char *b, int n) {
    for (int i = 0; i < n; i++) {
        if (a[i] == '?') {
            if (b[i] == '?') {
                a[i] = b[i] = '0';
            } else {
                a[i] = b[i];
            }
        } else {
            if (b[i] == '?') {
                b[i] = a[i];
            }
        }
    }
}

void fill(char c, char *s, char *end) {
    while (s != end) {
        if (*s == '?') *s = c;
        s++;
    }
}

bool inc(char *s, char *tpl, int n) {
    for (int i = n-1; i >= 0; i--) {
        if (tpl[i] == '?') {
            if (s[i] == '9') {
                s[i] = '0';
            } else {
                s[i]++;
                return true;
            }
        }
    }
    return false;
}

bool dec(char *s, char *tpl, int n) {
    for (int i = n-1; i >= 0; i--) {
        if (tpl[i] == '?') {
            if (s[i] == '0') {
                s[i] = '9';
            } else {
                s[i]--;
                return true;
            }
        }
    }
    return false;
}

int main() {
    freopen("output.txt", "w", stdout);

    int numCase, nowCase;
    scanf("%d", &numCase);
    for (nowCase = 1; nowCase <= numCase; nowCase++) {
        int n;
        char f[MAX], s[MAX];
        char rf[MAX], rs[MAX];

        scanf("%s%s", f, s);

        n = strlen(f);

        int diff = -1;
        for (int i = 0; i < n; i++) {
            if (f[i] != '?' && s[i] != '?' && f[i] != s[i]) {
                diff = i;
                break;
            }
        }

        if (diff == -1) {
            //can be same
            makeSame(f, s, n);

            strcpy(rf, f);
            strcpy(rs, s);
        } else {
            ll fsDiff = 1e18;

            auto update = [&](char *fCand, char *sCand) {
                ll rfCand = atoll(fCand);
                ll rsCand = atoll(sCand);
                ll candDiff = abs(rsCand - rfCand);

                if (fsDiff > candDiff ||
                    (fsDiff == candDiff &&
                    (atoll(rf) > rfCand || (atoll(rf) == rfCand && atoll(rs) > rsCand)))) {
                    strcpy(rf, fCand);
                    strcpy(rs, sCand);
                    fsDiff = candDiff;
                }
            };

            char tf[MAX], ts[MAX];

            if (f[diff] < s[diff]) {
                //f < s
                strcpy(tf, f);
                strcpy(ts, s);
                makeSame(tf, ts, diff);
                fill('9', tf+diff, tf+n);
                fill('0', ts+diff, ts+n);
                update(tf, ts);

                //f > s
                strcpy(tf, f);
                strcpy(ts, s);
                makeSame(tf, ts, diff);
                if (inc(tf, f, diff)) {
                    fill('0', tf+diff, tf+n);
                    fill('9', ts+diff, ts+n);
                    update(tf, ts);
                }

                //f > s
                strcpy(tf, f);
                strcpy(ts, s);
                makeSame(tf, ts, diff);
                if (dec(ts, s, diff)) {
                    fill('0', tf+diff, tf+n);
                    fill('9', ts+diff, ts+n);
                    update(tf, ts);
                }
            } else {
                //f > s
                strcpy(tf, f);
                strcpy(ts, s);
                makeSame(tf, ts, diff);
                fill('0', tf+diff, tf+n);
                fill('9', ts+diff, ts+n);
                update(tf, ts);

                //f < s
                strcpy(tf, f);
                strcpy(ts, s);
                makeSame(tf, ts, diff);
                if (inc(ts, s, diff)) {
                    fill('9', tf+diff, tf+n);
                    fill('0', ts+diff, ts+n);
                    update(tf, ts);
                }

                //f < s
                strcpy(tf, f);
                strcpy(ts, s);
                makeSame(tf, ts, diff);
                if (dec(tf, f, diff)) {
                    fill('9', tf+diff, tf+n);
                    fill('0', ts+diff, ts+n);
                    update(tf, ts);
                }
            }
        }

        //printf("%s %s\n", f, s);
        printf("Case #%d: %s %s\n", nowCase, rf, rs);
    }

    return 0;
}

2:03:41 small AC