1.

6개월 정도의 단기유학이 끝났다. 여름학기에 SBU에 있을 때는 주변에 놀 것도 먹을 것도 없는데 수업도 쉬워서 시간을 주체할 수 없는 기분이었는데, UCB는 주변에 먹을 것도 많고 수업 로드도 적절하고 방도 잘 얻어 걸려서 즐거운 생활을 했다. 한국에 비하면 많이 놀았다. Machine Structures랑 Linear Algebra를 제일 열심히 했고, Introduction to Neuroscience를 그 다음으로 열심히 했다. 수업들 질이 정말 좋았는데 괜히 명문대 소리 듣는게 아니구나 싶었다.

선형대수는 포스텍의 선형대수가 모든 학생이 다 듣는 기초필수과목인 것에 비해, 학점변환이 인정되는 버클리의 선형대수학 과목은 수학과 Upper Division 과목이었다. 처음에는 생소한 개념들이 많이 나와서 헤맸지만 그런 개념들을 하나 둘 이해하고 증명하는 과정이 정말 재미있었다. 포스텍에서 미적분학 들으면서도 느꼈던 거지만 나한테 프로그래밍이 워낙 잘 맞아서 그렇지 수학을 전공했어도 재밌게 했을 것 같다.

2.

학기가 끝나고 나서 내 룸메이트는 바로 한국으로 돌아갔고, 나는 좀 더 미국을 보고 가려고 미리 비행기표를 일주일 쯤 연장해 두었다. 하지만 게으른 나머지 계획을 세우지 않고 있다가, 학과 친구들의 LA 여행에 꼽사리로 놀러가게 되었다. 도시 구경도 하고 테마파크도 가고 아쿠아리움도 갔다. 내가 집을 좋아하긴 하지만 나가서 노는 것도 좋아하기는 한다. 하지만 물고기가 물 밖에 너무 오래 있으면 죽듯이, 집 밖에 너무 오래 있었는지 날짜가 지날수록 컨디션이 조금씩 나빠졌다. 다행히 많이 안 좋아지기 전에 버클리로 돌아가고 있다.

LA에서는 에어비엔비로 숙박했다. 집 주변에 한인타운이 있었는데, 화폐 단위가 달러라는 점을 빼면 한국과 다를 게 없었다. 한국인 주인이 한국어 간판을 달고 운영하는 식당, PC방, 노래방, 당구장, 카페 등이 있었다. LA 도착한 첫날에는 부대찌개랑 곱창전골을 먹으러 갔는데 반찬으로 나온 깍두기가 정말 맛있었다. 식당 사장님께서 공기밥하고 콜라도 서비스로 주시고 혹시 궁금한 거 있으면 전화하라고 명함도 주셨다. 한국에 있을 때였다면 이런 잘 모르는 사람의 과도한 관심은 별로 안 좋아했겠지만, 오랜만에 겪으니 이런 게 한국인의 장점인가 하는 생각이 들었다. 주변에 맛있어 보이는 한식집이 많았지만 어차피 한국 가면 많이 먹을 것들이란 생각에 많이 가지는 않기로 친구들과 합의를 보았다.

3.

미국은 해가 지고 나면 정말 무섭다. 다행히 우리 과 사람들이 직접 겪은 사례는 없었지만 질의응답 사이트에 노트북이 털렸는데 과제 제출마감을 연장해 줄 수 있냐고 물어보는 사람도 보았고, 친구의 룸메이트가 총 든 2인조 노상강도를 만나 가지고 있던 물건을 전부 털린 얘기도 한 다리 건너서 들었다. LA에서 버클리로 돌아갈 때는 새벽 급행 버스를 타는 일정이었는데, 메트로 첫 차가 막 다닐 때 쯤의 시간이었지만 멀쩡하게 역까지 갈 자신이 없어서 우버를 처음으로 타 봤다.

4.

우버 기사 분은 안타깝게도 내가 별로 좋아하지 않는 말이 많은 스타일이었다. 처음에는 내가 밤에 검은 옷을 입고 있어서 나를 못 봤다는 이야기부터 시작해서, 자기 애들이 머리를 분홍색이랑 초록색으로 염색했고 곧 피어싱을 할 거라는데 내기해도 좋다는 이야기, 할리우드에서 픽업해서 다운타운까지 내려다 주는데 한 시간은 걸렸는데 3 달러도 못 벌었다는 이야기를 했다.

나는 적당히 심드렁하게 맞장구를 쳐 주면서 버클리에 살다가 크리스마스 시즌에 LA로 놀러왔다는 얘기를 했다. 그랬더니 우버 기사 분이 나를 royalty라고 부르면서 신세한탄을 하셨다. Royalty들은 자식을 키우면서 “우리 애들은 스페인어를 공부했으면 좋겠어요.” 같은 얘기를 하지만, 자기 같은 사람들은 자식들이 변호사나 의사가 됐으면 정말 좋을 것 같다는 생각을 한다는 얘기를 하셨다. 처음에는 나를 공격하는 것 같아서 약간 당황스러웠는데 지금 생각해보면 그냥 자기 같은 사람들이 있다는걸 알아줬으면 했던 게 아닐까 싶다. 재미있게 읽었던 단편 카툰 ‘특권에 대한 짧은 이야기(On a Plate)’도 비슷한 내용을 다루고 있는데 혹시 시간 남으면 보길 바란다.

자본주의 사회에서 부의 불평등과 기울어진 운동장 문제는 아직도 뜨거운 감자인 채로 남아 있는데, 그렇기 때문에 이번 미국 대선에서 버니 샌더스 아재가 이겨서 미국이 사회주의 지상락원이 될 지 도날드 트럼프 아재가 이겨서 매드맥스 불지옥미국이 될 지 결과가 무척 기다려진다.

5.

터미널에 도착해서 의식의 흐름은 헬조센 담론으로 이어졌다. 나는 헬조센이라는 단어를 사용하는걸 꺼리는 편이다. 진지충, 선비 같은 단어들이 진지한 문제제기를 들을 가치가 없는 헛소리로 평가절하 해버리는 것처럼, 헬조센이라는 단어는 함께 풀어 나가야 할 사회문제들을 한국이 미개해서 어쩔 수 없이 생기는 문제들로 포장하기 때문이다.

이런 생각을 하며 페이스북 스크롤을 내리고 있는데 크로아티아에서 최초의 여성 대통령이 당선되었다는 기사가 보였다. 기사 썸네일에는 그 대통령이 비키니를 입고 해변에서 여가를 즐기는 사진이 있었고, 댓글에는 “ㅅㅂ 나보다 가슴 크네”가 3천개 가량의 좋아요를 받아 맨 위에 걸려 있었다. 기사 본문에는 미모의 대통령이 당선되어 SNS에서 화제가 되고 있다는 ‘최근 네티즌들의 반응’만이 자리를 차지하고 있었고, 어디에서도 그 사람이 어떤 사람인지를 알려주려는 노력의 흔적을 찾을 수 없었다. 그저 모두가 그 사람의 아름다운 외견을 소비하고 있을 뿐이었다. 비단 이 게시글 뿐 아니라 약자에 대한 폭력과 위협을 상남자라고 칭송하거나, 혐오표현을 할 수 있는 표현의 자유를 달라는 이해할 수 없는 주장에 공감을 표하는 사람들을 찾기란 그리 어렵지 않다.

눈에 보이는 가치만을 좇는 가벼움과 자신의 가치로 남을 멋대로 재단하는 행위는 어느새 솔직함과 쿨함이 되었다. 열심히 마음속에서 ‘대한민국이 고칠 점은 많아도 헬조센 까지는 아니지 않을까’ 하면서 실드를 쳐 주고 있었는데 이래서 헬조센 헬조센 하나 싶더라. 요새 생각을 하지 않고 살아가는 사람이 너무 많다고 느끼는 경우가 늘어났지만 어쩌면 이것도 그냥 내 중2병에 지나지 않을지도 모른다.

나는 게임을 할 때도 애니메이션을 볼 때도 음식을 먹을 때도 망작 헌터를 자처하며 남들이 망작이라고 평하는 걸 굳이 직접 체험해보면서 “음, 정말 듣던대로 망작이지만 이러저러한 점들은 나쁘지 않았어!” 같은 평을 즐기는 편인데, 이게 대한민국에도 적용되는건 아닐까 잠깐 생각했다. 최근에 했던 망작 헌팅으로는 트리오브세이비어와 코코넛 워터 ZICO가 있다. 다음 체험대상으로는 롯데리아의 모짜렐라 인 더 버거를 노리고 있다.

6.

사회 얘기에서 다시 좀 더 개인적인 얘기로 돌아와 보자. 터미널에서 읽었던 연애를 고양이 키우기에 비유한 대나무숲 게시글도 꽤 재미있었다. 그 글은 모든 사람이 고양이를 좋아하는 건 아니라는 얘기에서 시작해서, 고양이를 좋아하지만 고양이에게 쏟아야 하는 비용과 관심을 생각하면 키우지 않는게 좋을 것이라는 판단을 내린 사람에게 “왜 고양이를 좋아하면서 키우지 않느냐”고 묻지는 않는다는 이야기로 이어진다. 그리고 자기는 연애를 못 하는게 아니라 안 하는 거라고 주장하며 글이 끝난다. 물론 게시글 하단에는 울지 말고 천천히 얘기해 보라는 댓글이 달려 있었지만…

나는 안 하는게 아니라 못 하는 거긴 하지만 이 글을 쓴 사람과 연애에 관한 입장은 상당히 비슷하다고 느꼈다. 연애도 좋지만 나는 공부하는 것도 좋고 혼자 있는 시간도 중요하다. 그래서 일반적인 연인 관계에서 기대하는 ’10분에 한 번 카톡 확인’이나 ‘모든 일의 우선순위는 너’ 같은 걸 해 줄 자신이 없다. 평소에는 각자 자기 할 일 하면서 살다가 며칠에 한 번 정도의 빈도로 서로의 일상을 공유하면서 잘 살고 있는지 확인하고, 기념일에는 화려한 데이트코스보다는 편지나 주고 받으며 요리나 해 먹는, 딱 그 정도의 가볍지만 따뜻한 관계를 원하는 것 같다. 하지만 문제는 나랑 비슷한 연애를 추구하는 사람이 있다 치더라도 둘 모두 이 정도의 거리를 유지하고 있으면 연애를 시작할 수가 없다. 으앙 쥬금 ㅠㅠ

7.

기다리고 있던 버스에 드디어 탑승했는데 옆자리에 앉은 사람이 나랑 너무 비슷한 점이 많았다. 일단 나랑 똑같은 가방을 썼고, 복장도 둘 다 셔츠 안에 입은 티와 함께 청바지를 입었다. 심지어 그 사람도 프로그래머였다. 자세히 보지는 못했는데 Node로 웹개발 하고 있었던 듯. 나는 오클랜드까지 가고 그 분은 산호세에서 내렸다. 내가 열심히 글을 쓰는 동안 그 사람은 열심히 서브라임으로 코딩을 했다. 나중에 자다 일어나서 보니까 문명도 하더라. 나도 원래는 버스에서 코딩을 할 계획이었는데 버스 안에서 인터넷이 안 돼서 계획이 바뀌어서 오랜만에 일기를 쓰고 있다.

Greyhound사의 버스를 탔는데, 안에서 전기도 되고 와이파이도 된다는 걸 그렇게 광고했고 LA 갈 때는 유용하게 잘 사용했지만, 버클리로 돌아오는 버스에서는 되는게 없었다. 처음에는 전기도 안 됐는데 버스가 잠깐 휴게소에 멈췄을 때 옆자리에 앉은 그 분께서 기사님께 뭐라고 말을 하더니 전기가 들어오기 시작했다. 와이파이는 끝까지 되지 않았다. 서비스를 홍보한대로 제공하는데 실패했으니 티켓값 일부를 환불해 주면 좋겠지만 6개월 살아 본 결과 미국에는 원래 안 되는게 많아서 이 정도에 불만을 가지지 않는 사람이 대부분이고, 나머지 사람들은 환불요청이 아니라 고소를 한다.

8.

두서 없이 많은 이야기들을 했다. 평소대로 각 주제 하나하나를 하나의 완성된 글로써 다루고 싶은 마음도 있었지만 왠지 버스에서 다 쓰고 싶은 기분이 들어서 그냥 생각 나는 이야기들을 다 짧게 써 보았다. 인터넷이 없어서 글 쓰는 것 이외에 딱히 할 일이 없기도 했고. 글로 생각을 남기는 건 시간이 많이 드는 피곤한 작업이지만, 다 쓰고 났을 때의 성취감과 시간이 지나고 나서 예전에 어떤 생각들을 했었는지 돌아보는 재미 덕분에 종종 글을 쓰게 된다. 초등학교 때는 일기 쓰기를 별로 좋아하지 않았었는데 역시 누가 시켜서 하는 것보다는 알아서 할 때 작업 효율이 더 좋은 법이다.

SCC

SCC는 Strongly Connected Component의 약자로, 방향 그래프의 SCC는 다음 조건을 만족하는 서브그래프들입니다.

  • 같은 SCC 내에 속하는 임의의 서로 다른 두 정점은 서로 도달 가능합니다.
  • 어떤 정점이나 간선도 1의 조건을 만족하면서 이 SCC에 추가될 수 없습니다.(최대부분집합)

SCC Example

위의 예시에서는 (a, b, e) (f, g) (c, d, h)가 하나의 SCC가 됩니다. 임의의 방향 그래프에서 SCC를 구했을 때 모든 정점은 단 하나의 SCC에만 속하게 되며, SCC 자체를 하나의 정점으로 보았을 때 전체 그래프를 사이클이 없는 방향 그래프(DAG) 형태로 변환할 수 있습니다.

임의의 방향 그래프가 주어질 때 SCC를 찾는 알고리즘으로 코사라주의 알고리즘과 타잔의 알고리즘이 유명하고, 둘 모두 O(V+E)에 동작함이 증명되어 있습니다. 아래는 각 알고리즘의 설명과 구현 코드입니다. 입출력은 BOJ의 Strongly Connected Component 문제를 기준으로 작성했습니다.

코사라주의 알고리즘(Kosaraju’s Algorithm)

코사라주의 알고리즘은 다음과 같이 동작합니다.

  1. 방향 그래프 G, 빈 스택 S, G의 간선 방향을 뒤집은 역방향 그래프 G’를 준비합니다.
  2. G에서 아직 방문되지 않은 정점들에 대해 DFS를 시행하고, 각 정점의 탐색이 끝나는 순서대로 S에 넣습니다.(위상정렬) 스택에 모든 정점이 들어갈 때까지 반복합니다.
  3. S가 빌 때까지 다음을 반복합니다.
  4. S의 가장 위쪽에 있는 정점 v를 뽑습니다. v가 G’에서 이미 방문된 정점이라면 정점을 다시 뽑습니다.
  5. G’에서 v에서 DFS를 시행해 이번 시도에 처음 방문한 정점들을 v와 같은 SCC로 묶습니다.

코사라주의 알고리즘은 정방향 그래프와 역방향 그래프가 동일한 SCC를 가진다는 점을 이용합니다. 정방향 DFS를 통해 정점들을 위상정렬하고, 역방향 DFS에서 SCC를 찾는다고 생각할 수 있습니다.

Kosaraju's Algorithm Code
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX = 10020;

int V, E;
vector < int > front[MAX], rev[MAX];

void input() {
    scanf("%d%d", &V, &E);

    // 그래프 초기화
    for (int i = 0; i < E; i++) {
        int f, s;
        scanf("%d%d", &f, &s);
        front[f].push_back(s);
        rev[s].push_back(f);
    }
}

int visited[MAX], stack[MAX], top;
vector < vector < int > > sccGroup;

void front_dfs(int node) {
    visited[node] = 1;
    for (auto next : front[node]) {
        if (!visited[next]) {
            front_dfs(next);
        }
    }
    // DFS를 빠져 나올 때 스택에 쌓음
    stack[top++] = node;
}

void rev_dfs(int node) {
    visited[node] = 1;
    // 마지막 그룹에 정점 추가
    sccGroup[sccGroup.size()-1].push_back(node);
    for (auto next : rev[node]) {
        if (!visited[next]) {
            rev_dfs(next);
        }
    }
}

void solve() {
    // 위상 정렬
    for (int v = 1; v <= V; v++) {
        if (!visited[v]) {
            front_dfs(v);
        }
    }

    // 그룹 묶기
    memset(visited, 0, sizeof(visited));
    while (top) {
        int node = stack[top-1];
        top--;
        if (!visited[node]) {
            // 빈 그룹 추가
            sccGroup.push_back(vector < int >());
            rev_dfs(node);
        }
    }

    // 문제 요구 조건대로 정렬
    for (auto &vec : sccGroup)
        sort(vec.begin(), vec.end());
    sort(sccGroup.begin(), sccGroup.end());

    // 출력
    printf("%dn", sccGroup.size());
    for (auto &vec : sccGroup) {
        for (auto elem : vec) {
            printf("%d ", elem);
        }
        puts("-1");
    }
}

int main() {
    input();

    solve();

    return 0;
}

코사라주의 알고리즘은 기억하기 쉬운 편이지만, 동일한 그래프를 두 가지 형태로 저장해야 하고 DFS를 두 번 시행하기 때문에 일반적으로 타잔의 알고리즘보다 약간 낮은 성능을 보여줍니다. 하지만 시간복잡도에는 차이가 없기 때문에 알고리즘 문제풀이에서는 문제 없이 사용할 수 있습니다.

타잔의 알고리즘(Tarjan’s Algorithm)

타잔의 알고리즘은 다음과 같이 동작합니다.

  1. 방향 그래프 G, 빈 스택 S, 각 정점의 방문 순서를 저장할 배열 index, 각 정점에서 도달 가능한 정점을 저장할 배열 lowlink를 준비합니다.
  2. 아직 방문되지 않은 정점 v에서 DFS를 시작합니다.
  3. v를 S에 쌓고, index[v]에 방문 순서를 저장합니다.
  4. lowlink[v] = index[v]
  5. v의 이웃 정점 u에 대해:
  6. u를 아직 방문하지 않았다면 u에 대해 DFS를 시행하고, lowlink[u]가 lowlink[v]보다 작은 경우 lowlink[v]를 갱신합니다.
  7. u가 스택에 들어있고, index[u]가 lowlink[v]보다 작은 경우 lowlink[v]를 갱신합니다.
  8. lowlink[v]와 index[v]가 동일하다면, v를 포함해 v 이후로 S에 쌓인 정점들을 새로운 SCC 컴포넌트로 묶습니다.

타잔의 알고리즘은 각각의 SCC가 DFS 트리에서 서브트리를 이룬다는 점을 이용한 알고리즘입니다. 임의의 정점 v에 대한 탐색이 종료된 시점에서, v 이전에 스택에 쌓인 정점에 대한 경로가 존재하는 경우에만 v가 스택에 남아 있을 수 있습니다. 그렇지 않은 경우 v는 v 이전에 스택에 쌓인 정점들과 같은 SCC에 속할 수 없기 때문에 v가 SCC의 경계가 되어 현재 스택에 쌓인 정점들과 SCC를 구성합니다.

Tarjan's Algorithm Code
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX = 10020;

int V, E;
vector < int > from[MAX];

void input() {
    scanf("%d%d", &V, &E);

    // 그래프 초기화
    for (int i = 0; i < E; i++) {
        int f, s;
        scanf("%d%d", &f, &s);
        from[f].push_back(s);
    }
}

int stack[MAX], top, id[MAX], currentId, groupId[MAX];
vector < vector < int > > sccGroup;

int traverse(int node) {
    id[node] = ++currentId;
    stack[top++] = node;

    // lowlink를 return 값으로 사용
    int lowlink = id[node];
    for (auto next : from[node]) {
        if (id[next] == 0) {
            // 방문하지 않은 정점
            lowlink = min(lowlink, traverse(next));
        } else if (groupId[next] == 0) {
            // 이미 스택에 들어 있는 정점
            lowlink = min(lowlink, id[next]);
        }
    }

    if (lowlink == id[node]) {
        // 그룹 추가
        sccGroup.push_back(vector < int >());
        while (1) {
            int now = stack[top-1];
            top--;

            // node 하위의 서브트리를 SCC 그룹으로 묶기
            groupId[now] = sccGroup.size();
            sccGroup[groupId[now]-1].push_back(now);

            if (now == node) break;
        }
    }

    return lowlink;
}

void solve() {
    for (int v = 1; v <= V; v++) {
        if (id[v] == 0) {
            traverse(v);
        }
    }

    // 문제 요구 조건대로 정렬
    for (auto &vec : sccGroup)
        sort(vec.begin(), vec.end());
    sort(sccGroup.begin(), sccGroup.end());

    // 출력
    printf("%dn", sccGroup.size());
    for (auto &vec : sccGroup) {
        for (auto elem : vec) {
            printf("%d ", elem);
        }
        puts("-1");
    }
}

int main() {
    input();

    solve();

    return 0;
}

타잔의 알고리즘은 기억해야 할 조건들이 코사라주의 알고리즘에 비해 헷갈리는 편이지만, DFS를 한 번만 작성해도 된다는 점에서 타잔의 알고리즘을 더 쉽다고 평가하는 의견도 있습니다. 둘 모두 시간복잡도는 동일하기 때문에 문제를 풀 때는 일반적으로 어떤 알고리즘을 사용해도 괜찮습니다.

2-SAT

SCC 알고리즘의 응용 사례 중 유명한 것으로 2-SAT 문제가 있습니다. SAT 문제는 논리 변수와 논리식이 주어질 때 논리식을 참으로 만드는 논리 변수 조합이 존재하는지를 찾는 문제입니다. 2-SAT은 SAT 문제들 중 특수한 형태의 문제로, 다음 예시에서 볼 수 있듯이 두 개의 변수의 or 연산들이 and 연산으로 결합된 형태의 논리식을 다루는 문제입니다. 이런 형태의 식을 2-CNF 또는 Krom formulas라고 부릅니다.

(neg x_1 vee x_3) wedge (neg x_2 vee neg x_3) wedge (x_1 vee x_2) wedge (neg x_1 vee x_4) wedge (x_2 vee neg x_4)

이제 논리식을 그래프로 바꾸는 방법을 알아봅시다.

  1. 각각의 논리 변수 x에 대해 두 개의 정점 x, ~neg x을 생성합니다.
  2. 논리식에 포함된 각각의 A vee B에 대해, neg A rightarrow B 간선과 neg B rightarrow A 간선을 생성합니다.

위의 예시에서 보여드린 식을 그래프로 바꾸면 다음과 같습니다.

이렇게 그래프를 생성하면 or로 묶인 두 개의 변수 중 적어도 하나는 참이어야 하기 때문에, A에서 B로 가는 간선은 A가 참이라면 B도 반드시 참이라는 것을 의미하게 됩니다. 이제 이 그래프에 SCC 알고리즘을 적용해서 정점들을 컴포넌트로 묶은 이후를 생각해봅시다. SCC의 정의와 간선을 그은 조건 때문에, 컴포넌트 내에 하나의 정점이라도 참이라면 그 컴포넌트는 모두 참이 됩니다. 따라서 같은 컴포넌트에 속한 정점들은 전부 참이거나 전부 거짓이라는 것을 알 수 있습니다.

xneg x는 다음 세 가지 중 한 가지 관계를 가집니다.

  • xneg x가 같은 컴포넌트에 속하는 경우
  • x에서 neg x로 가는 경로(또는 neg x에서 x로 가는 경로)만 존재하는 경우
  • xneg x간에 경로가 존재하지 않는 경우

첫 번째는 답이 존재하지 않는 경우입니다. 주어진 논리식을 참으로 만드는 논리 변수 조합이 존재하는 것과, 논리 변수 forall x에 대해 xneg x 정점이 같은 컴포넌트에 속하지 않는 것이 필요충분조건임이 증명되어 있습니다.

두 번째는 위상정렬 했을 때 더 뒤쪽에 존재하는 정점만이 참입니다. 세 번째는 둘 중 어느 것을 참으로 결정해도 상관 없습니다.

그래프가 skew-symmetric하기 때문에 A, ~B가 같은 컴포넌트에 속한다면 neg A, ~neg B 또한 같은 컴포넌트에 속하고, 이 특징을 이용해 위의 성질들을 증명할 수 있습니다.

위의 성질들을 이용해 각 논리 변수의 값을 다음 방법으로 찾을 수 있습니다.

  1. 논리식에서 그래프를 생성합니다.
  2. 생성된 그래프에 SCC 알고리즘을 적용합니다.
  3. 만약 xneg x의 SCC 번호가 같은 정점이 존재한다면 주어진 논리식을 만족하는 조합은 존재하지 않습니다.
  4. 아니라면, x의 SCC 번호가 neg x의 SCC 번호보다 작은 경우 x가 참입니다.

아래는 구현 코드입니다. BOJ의 2-SAT – 4 문제를 기준으로 작성했습니다.

2-SAT
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX = 20020;

int N, M;
vector < int > from[MAX];

inline int neg(int x) {
    if (x > N) return x - N;
    else return x + N;
}

void input() {
    scanf("%d%d", &N, &M);

    // 그래프 초기화
    for (int i = 0; i < M; i++) {
        int f, s;
        scanf("%d%d", &f, &s);

        // ~X는 N+X로 표현
        if (f < 0) f = -f + N;
        if (s < 0) s = -s + N;

        from[neg(f)].push_back(s);
        from[neg(s)].push_back(f);
    }
}

int stack[MAX], top, id[MAX], currentId, groupId[MAX];
vector < vector < int > > sccGroup;

int traverse(int node) {
    id[node] = ++currentId;
    stack[top++] = node;

    // lowlink를 return 값으로 사용
    int lowlink = id[node];
    for (auto next : from[node]) {
        if (id[next] == 0) {
            // 방문하지 않은 정점
            lowlink = min(lowlink, traverse(next));
        } else if (groupId[next] == 0) {
            // 이미 스택에 들어 있는 정점
            lowlink = min(lowlink, id[next]);
        }
    }

    if (lowlink == id[node]) {
        // 그룹 추가
        sccGroup.push_back(vector < int >());
        while (1) {
            int now = stack[top-1];
            top--;

            // node 하위의 서브트리를 SCC 그룹으로 묶기
            groupId[now] = sccGroup.size();
            sccGroup[groupId[now]-1].push_back(now);

            if (now == node) break;
        }
    }

    return lowlink;
}

void solve() {
    for (int v = 1; v <= 2*N; v++) {
        if (id[v] == 0) {
            traverse(v);
        }
    }

    // x와 ~x가 같은 컴포넌트 안에 속하면 답 없음
    for (int v = 1; v <= N; v++) {
        if (groupId[v] == groupId[neg(v)]) {
            puts("0");
            return;
        }
    }

    // x가 ~x보다 컴포넌트 번호가 작은 경우(그래프 상에서 뒤에 있는 경우) x는 참
    puts("1");
    for (int v = 1; v <= N; v++) {
        printf("%d ", groupId[v] < groupId[neg(v)]);
    }
    puts("");
}

int main() {
    input();

    solve();

    return 0;
}

USACO Gold랑 Platinum을 쳤다. 나쁘지 않지만 약간 아쉬운 결과. Gold는 1시간컷, Platinum은 A, C 풀고 B 짜다가 시간 종료.

Gold는 특별히 언급할만한건 없다. C가 구현이 좀 귀찮은 편이었지만 전체적인 난이도는 예전 실버급. 오랜만에 USACO 풀어서 파일 입출력을 안 하기도 하고, 정렬을 begin부터 begin까지 하는 등 멍청한 실수를 많이 했다.

Platinum은 칠까 말까 고민했는데 주변에서 들리는 2시간컷 가능하다는 말에 속아서 쳤다. 저 ‘주변’에 속하는 인물들이 다 갓들이라 나는 시간 내에 다 풀지 못했다. 시험공부 해야 하는데 흑흑 여기서는 전형적인 문제들이 많이 나왔다. A는 전형적인 트리 DP, C는 전형적인 Lazy Propagation 문제였다. B는 익숙한 개념을 한 번 꼬아서 낸 좋은 문제였지만 풀이를 찾고 시간 내에 코드를 작성하지 못했다. C에서 코딩이 말려서 오래 걸렸던 것이 원인이라 생각되지만 그걸 빼고 생각해도 약간 어려운 수준의 문제라고 평가된다.

나중에 시험이 끝나거나 해서 시간이 좀 많아졌을 때 B를 다시 풀어보는걸로 하고 오늘은 이걸로 마무리!

코드포스 #335 div. 1

3개월만에 코드포스를 쳤다. 시험기간이라 요 며칠 사이에 백준에서 쉬운 문제들 몇 개 깔짝대고 있었는데, 마침 코드포스가 아침 8시라 시간이 괜찮아서 오랜만에 쳤다. 원래는 잠을 좀 자고 7시쯤 일어나서 씻고 칠 예정이었는데 3시간 반 넘게 누워 있었는데 잠에 들지 못해서 그냥 일어나서 문제 풀면서 손을 풀면서 아침을 맞았다. 잠을 못 잔 덕분에 대회 때 잠기운이 약간 있긴 했지만 다행히 크게 방해되지는 않았다.

대회 시작 즈음에는 ABC 풀면 레드 갈 줄 알았는데, 예상한대로 풀었지만 여기저기 실수하는 바람에 감점을 받아 레이팅 변화는 거의 없을 것 같다. 이번에도 그냥저냥 실력만큼 본 것 같은데, 예전에 실력대로만 보면 되는 시험들에서 망한 경험이 너무 많아서 이런 사소한 사실에도 만족감을 느끼고 있다. 최종 순위는 127위.

A

문제를 대충 읽다가 틀렸다. 기차를 뽑아서 맨 앞이나 맨 뒤에만 넣을 수 있는데, 뽑아서 아무데나 넣을 수 있을 때 최소 정렬횟수를 구하는 게 잘 알려진 문제라 왜 이런 유명한 걸 냈냐고 투덜대면서 풀었다가 Hack 당했다. 저렇게 짜도 pretest 통과하게 해 놓은데서 출제진의 악랄함을 느낄 수 있다. 내가 착각한 문제와 풀이가 크게 다르지 않고, 번호가 연속하는 LIS 중 가장 긴 것을 찾으면 된다.

#include <cstdio>

const int MAX = 100020;

int n, len[MAX];

int main() {
    scanf("%d", &n);

    int maxLen = 1;
    for (int i = 0; i < n; i++) {
        int t;
        scanf("%d", &t);
        if (len[t-1] != 0) {
            len[t] = len[t-1]+1;
            if (maxLen < len[t])
                maxLen = len[t];
        }  else len[t] = 1;
    }

    printf("%d\n", n - maxLen);

    return 0;
}

B

ABC 중 가장 마음에 드는 문제였다. 트리의 간선 길이와 그 간선이 최소신장트리에 포함되는지 여부가 주어지면 그래프를 알아서 잘 구성하면 되는 문제다. 크루스칼 알고리즘으로 MST를 찾을 때, 간선을 길이 순으로 정렬했을 때 특정 간선이 포함되지 않는 경우는 이전의 간선들과 사이클을 이룰 때라는 사실을 적절히 이용하면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 100020;

struct Edge {
    int id, len;
    bool used;

    Edge() {}
    Edge(int id, int len, bool used) : id(id), len(len), used(used) {}
};

bool compareLen(const Edge &f, const Edge &s) {
    if (f.len == s.len) return f.used > s.used;
    return f.len < s.len;
}

int n, m;
Edge edge[MAX];

void input() {
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; i++) {
        int len, used;
        scanf("%d%d", &len, &used);
        edge[i] = Edge(i, len, used);
    }

    sort(edge, edge+m, compareLen);
}

int from[MAX], to[MAX];

bool solve() {
    int last = 1, now = 3, remain = 1;
    for (int i = 0; i < m; i++) {
        Edge &cur = edge[i];
        if (cur.used) {
            from[cur.id] = last;
            to[cur.id] = last+1;
            last++;
        } else {
            if (last < now) return 0;
            from[cur.id] = now;
            to[cur.id] = remain;
            remain--;
            if (remain == 0) {
                now++;
                remain = now-2;
            }
        }
    }
    return 1;
}

void print() {
    for (int i = 0; i < m; i++)
        printf("%d %d\n", from[i], to[i]);
}

int main() {
    input();

    if (solve()) print();
    else puts("-1");

    return 0;
}

C

2015 구글 코드잼 R2 B Kiddie Pool과 굉장히 유사한 문제였다. 코드잼 칠 때는 시간 내에 풀이를 못 떠올렸는데 이번 라운드에서는 풀이 찾는건 금방 성공했다. 하지만 코딩에서 잔실수를 너무 많이 해서 3번이나 WA를 받고 통과할 수 있었다. 말도 안 되는 코드를 짜서 냈는데 pretest에서 걸려서 다행이었다.

문제는 전혀 기하처럼 생기지 않았지만 2차원 벡터로 생각해서 컨벡스헐을 구한 뒤 교차점을 통해 값을 계산하는 문제다. 선분 교차지점 구하는 코드는 안 졸렸으면 금방 유도했을텐데 졸려서 계산하기 싫은 마음에 그냥 StackOverflow에서 가져다 붙였다.

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair < ll, ll > pll;

#define x first
#define y second

const int MAX = 100020;

int n, targetExp, targetMoney;
pll target, point[MAX];

void input() {
    scanf("%d%d%d", &n, &targetExp, &targetMoney);
    target = pll(targetExp, targetMoney);

    for (int i = 0; i < n; i++) {
        int exp, money;
        scanf("%d%d", &exp, &money);
        point[i] = pll(exp, money);
    }
}

ll ccw(pll a, pll b, pll c) {
    return a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x;
}

pll origin = pll(0, 0);
bool compare(const pll &f, const pll &s) {
    return ccw(origin, f, s) > 0;
}

pll stack[MAX];
int top;

void solve() {
    sort(point, point + n, compare);

    stack[top++] = point[0];
    for (int i = 1; i < n; i++) {
        if (top && ccw(origin, stack[top-1], point[i]) == 0) {
            if (stack[top-1].x <= point[i].x) {
                top--;
                while (top >= 2 && ccw(stack[top-2], stack[top-1], point[i]) <= 0) top--;
                stack[top++] = point[i];
            }
        } else {
            while (top >= 2 && ccw(stack[top-2], stack[top-1], point[i]) <= 0) top--;
            stack[top++] = point[i];
        }
    }

    int start = 0, end = top-1;
    while (start != top-1 && stack[start].x <= stack[start+1].x) start++;
    while (end != start && stack[end].y <= stack[end-1].y) end--;

    if (start == end || ccw(origin, stack[start], target) <= 0 || ccw(origin, stack[end], target) >= 0) {
        printf("%.10lf\n", max((double)target.y / stack[end].y, (double)target.x / stack[start].x));
    } else {
        for (int i = start; i < end; i++) {
            double p0_x = 0, p0_y = 0, p1_x = target.x, p1_y = target.y,
                p2_x = stack[i].x, p2_y = stack[i].y, p3_x = stack[i+1].x, p3_y = stack[i+1].y;

            double s1_x, s1_y, s2_x, s2_y;
            s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
            s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;

            double s, t;
            s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
            t = (s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);

            if (s >= 0 && s <= 1) {
                printf("%.10lf\n", target.x / (p0_x + (t * s1_x)));
                break;
            }
        }
    }
}

int main() {
    input();

    solve();

    return 0;
}