창의IT설계는 우리 학과의 간판 과목으로 한 학기 동안 자유 주제로 자신이 “창의IT스럽다”고 생각하는 프로젝트를 진행하는 과목이다. 총 네 단계로 이루어져 있으며 1, 2는 팀으로, 3, 4는 개인으로 진행하며 1, 2에서는 학기별로 주제를 변경하고 3, 4는 한 주제를 1년동안 진행하는 경우가 많다. 나는 자신이 원하는 프로젝트를 마음대로 진행할 수 있다는 자율성과, 학점을 통한 압박으로 마냥 놀지 못하게 하는 강제성이 절묘하게 시너지를 내는 훌륭한 과목이라고 생각한다. 창의IT융합공학과 진학을 선택하면서 고려했던 것도, 어차피 어느 학교에 가든 관심 있는 기술들을 바탕으로 개인 프로젝트를 진행할텐데 창의IT설계 과목 덕분에 주마다 프로젝트 진행 시간도 보장해주고 학점까지 챙겨갈 수 있으니 훨씬 집중하기 쉬운 환경이라고 생각했었다. 장학금 덕분에 신경 쓸 부분이 적어진다는 점도 마음에 들었었다.

사실 앞 문단은 은근슬쩍 끼워 넣은 학과 홍보였고, 본론으로 들어가면 학기 시작이 다가오면서 창의IT설계 3, 4 주제 선정 때문에 고민하고 있다. 교수님들께서는 방학 때 프로젝트를 시작하는 것을 추천하시지만 대부분의 학생들이 학기가 시작하고 프로젝트를 시작한다. 동아리에서 해킹을 하면서 기존 디버거들에 느꼈던 불만을 바탕으로 창의IT설계 3, 4에서는 바이너리 분석 및 디버깅 플랫폼을 주제로 하려고 생각하고 있었다. 시각적으로 좋은 프로젝트와 일상생활과 연관이 있는 프로젝트가 점수를 잘 받는 경향이 있기 때문에 학점 측면에서는 도박성이 있는 주제 선정이지만, 내가 즐겁게 할 수 있으면서 배우는 게 많고, 커리어에도 도움이 될 거라 생각해 이 주제를 일순위로 고려중이었다.

내가 해결하고 싶었던 문제들은 다음과 같다.

  • 디버깅 도구들의 높은 러닝 커브 낮추기
  • 바이너리 분석과 페이로드 제작 환경 통합
  • 중간 언어를 이용한 멀티 아키텍처 디컴파일링
  • codemap, qira, angr 등에 대한 쓰기 쉬운 프론트엔드 제공, 혹은 유사 기능 구현해 통합

주요 고려 대상이었던 건 gdbIDA 두 가지였다. gdb는 CUI에서 기반하는 명령어 암기 및 높은 러닝 커브가 문제라 생각했고, IDA는 높은 가격과 강력한 기능에 비해 아쉬운 UX(Undo 미지원 등)를 개선하고 싶었다. 또한 IDA처럼 실행 환경(주로 Unix)과 분석환경(주로 Windows)이 달라서 생기는 사소한 문제들도 해결할 수 있으면 좋겠다고 생각했다.

하지만 당연히 비슷한 생각을 하는 사람들이 있어서, Binary Ninja나, radare2 같은 2티어 바이너리 분석 툴들에서 이미 비슷한 문제에 대해 고민하고 있었다. 특히 radare2 같은 경우는 해외 커뮤니티에서 super stiff learning curve라는 이야기를 들을 정도로 어디서부터 시작하면 좋을지 모르게 생겼었는데, 최근에 웹 UI를 도입하면서 사용성이 크게 개선된 것처럼 보였다.

Radare2 Web UI

내가 생각하고 있던 구조도 서버에서 바이너리를 실행하고 웹 기반 GUI로 상호작용 하는 것이었는데, radare2의 웹 UI와 특징이 많이 겹쳤다. Binary Ninja는 웹UI는 아니지만 이것도 쓰기 좋은 크로스 플랫폼 UI를 제공하기 때문에 UI 사용성에서는 크게 우위를 보이기 힘들 것이라는 생각이 들었다.

중간 언어를 이용한 디컴파일링 기능은 Hex-Rays 만큼은 당연히 구현하지 못하겠지만, 함수 시그니처 인식, 조건문과 반복문 정도만 구현해도 무료 도구 치고는 경쟁력을 가질 수 있다고 생각했다. 하지만 radare2에서 이미 구현중이었고, Binary Ninja의 로드맵에도 주 목표 중 하나로 제시되어 있었다. 조사하다보니 lldb, gdb, vdb, windbg에 대한 추상화 레이어를 제공하는 Voltron 같은 프로젝트도 있었고, 알아볼수록 기존에 잘 만든 도구들이 많아서 이 주제를 그대로 고르는 것이 맞는지 계속 고민된다. 만약 그대로 이 주제를 선택한다면 완성도는 Binary Ninja Python Prototype 정도를 목표로 하려고 한다. 또한, 기존 도구들에 비해 어떤 차별성을 가질 수 있을지를 더 심도있게 고민해야 할 것으로 보인다.

만약의 경우를 대비해 생각해 두고 있는 다른 주제들도 몇 개 있다. 첫 번째는 1학년 때 MS 이매진컵 주제였던 복셀 기반 월드 에디터 + 비주얼 프로그래밍 언어를 이용한 교육용 프로그래밍 플랫폼 프로젝트다. SangJa라는 이름으로 나갔었는데, JS가 처음이기도 했고 협업에 익숙하지 않아 코드 관리가 조금 아쉬웠지만 주제 자체는 훌륭했다고 생각한다. 지금 생각하고 있는 주제 중 “창의IT”에 제일 적합하다고 생각되기는 한다. 팀 프로젝트라 내가 마음대로 주제를 쓸 수 있는게 아니라서 만약 이 주제를 고르게 된다면 이전에 같이 진행했던 사람들에게 연락해 내가 주제를 다시 써도 되는지 물어보아야 할 것 같다.

두 번째 주제는 안드로이드 매크로다. G매크로류의 매크로 프로그램들은 PC만 지원하는 경우가 많은데, 안드로이드까지 지원을 확장하고 비전 기반 기능들을 추가하려고 생각하고 있다(체력바를 읽는다든지 카드 희귀도를 알아내서 리세마라를 해 준다든지). 이 주제를 하게 되면 본의 아니게 또 OpenCV와 한 학기를 보내게 될 것이다. 이것도 적다보니 오토핫키 안드로이드 열화 카피가 되는 건 아닌지 걱정된다. sl4a 같은 프로젝트도 있고…

원래는 미리 고민해서 개발을 시작하려고 했는데, 연구참여도 하고 동아리도 하다 보니 짧은 방학이 훌쩍 지나가버렸다. 이번 학기에는 기초필수 과목이 끝난 덕분에 학기중 연참을 하면서 창의IT설계와 연구참여 투탑 체제로 프로그래밍 비중이 높은 학기를 보내려고 계획하고 있다.

이 글은 예전 버전 certbot을 기준으로 작성되었습니다. certbot이 업데이트 되면서 nginx 플러그인이 베타를 벗어나 자동 설정이 가능하게 되었습니다. 자세한 정보는 certbot 홈페이지를 참고해주세요.

블로그에 HTTPS 붙여야지 붙여야지 계속 말만 하면서 안 붙이고 있었는데, 연휴를 맞아 실행하게 되었습니다. 이 글은 NGINX 위에서 직접 호스팅하는 WordPress 블로그에 Let’s Encrypt 인증서를 적용하는 튜토리얼입니다.

1. Certbot으로 인증서 받아오기

Let’s Encrypt는 인증 기관(Certificate Authority, CA) 중 하나입니다. Self-signed 인증서를 이용해 HTTPS를 구현할 수도 있습니다만 HTTPS를 제대로 지원하려면 인증 기관에서 발급 받은 인증서가 필요합니다. 대부분의 인증 기관이 인증서를 유료로 발급해주는데 반해, Let’s Encrypt는 무료로 갱신 가능한 90일짜리 인증서를 발급해준다는 장점이 있습니다. Let’s Encrypt는 인증서를 발급할 때 ACME 프로토콜을 사용하는데, Certbot은 다양한 ACME 클라이언트 중 Let’s Encrypt에서 공식적으로 추천하는 클라이언트입니다.

먼저 Certbot을 설치하고 디펜던시 설치를 위해 설치 후 한 번 실행해 줍시다(루트 권한이 필요합니다). 글 작성일을 기준으로 아직 NGINX auto-config 기능이 기본 클라이언트에 포함되어 있지 않기 때문에 실행 결과 마지막에 관련된 에러 메시지가 뜰텐데, 큰 문제가 아니니 걱정하지 않으셔도 됩니다.

$ cd /usr/local/sbin
$ sudo wget https://dl.eff.org/certbot-auto
$ sudo chmod a+x certbot-auto
$ certbot-auto

다음 단계는 설치된 Certbot으로 인증서를 받아오는 것입니다. Certbot은 플러그인 방식으로 동작하며, $ certbot-auto [SUBCOMMAND] --{plugin name}처럼 실행하면 해당 플러그인 모드로 실행됩니다. WordPress 블로그의 경우 보통 정적 파일 serving이 세팅되어 있기 때문에, webroot 플러그인을 사용하는 것을 추천드립니다. 다른 플러그인을 사용하는 경우 여기를 참고하시면 됩니다.

webroot 플러그인은 certonly 모드로 동작시켜야 합니다. -w 옵션 뒤에는 Top-level 디렉토리(WordPress 설치 경로)를 넣고, -d 옵션 뒤에 Host 주소를 넣으면 됩니다. 제 경우에는 qwaz.io, blog.qwaz.io에 적용되는 인증서를 얻기 위해 $ certbot-auto certonly --webroot -w /home/qwaz/blog/www -d qwaz.io -d blog.qwaz.io 명령을 실행했습니다.

webroot 플러그인은 Top-level 디렉토리에 .well-known/acme-challene/{HASH} 파일을 자동으로 생성해 해당 서버에 대한 소유 권한을 확인합니다. 인증 후에는 자동으로 삭제까지 이루어집니다. 프롬프트에 이메일 주소를 입력하고 약관에 동의하면 verification이 이루어지고, /etc/letsencrypt/live/{domain}/에 인증서가 저장됩니다. 또한, 이후 renewal을 위한 계정 정보 등도 /etc/letsencrypt에 함께 저장되며 주기적인 백업을 추천하는 안내 메시지를 보실 수 있습니다.

인증서 디렉토리에 가서 확인하시면 cert.pem, chain.pem, fullchain.pem, privkey.pem 총 네 가지 파일이 생성된 것을 확인하실 수 있을 겁니다. 마지막으로, $ openssl dhparam -out dhparam.pem 2048 명령어를 이용해 디피-헬만 그룹을 생성해 저장합니다. 시간이 좀 걸리니 천천히 기다리셔야 합니다.

인증서 갱신은 $ cerbot-auto renew 명령으로 가능하며, 인증서 유효기간이 90일인 것을 염두에 두고 주기적으로 실행하시면 됩니다. crontab 등의 유틸리티를 이용해 자동 갱신을 설정하실 수도 있습니다.

2. NGINX에 HTTPS 적용하기

/etc/nginx/sites-enabled 디렉토리에서 HTTPS를 지원하도록 서버 설정을 바꾸어 주어야 합니다. HTTPS를 적용하기 이전 제 블로그 conf 파일은 다음과 같습니다.

# configuration of the server
server {
        # the port your site will be served on
        listen 80;

        # the domain name it will serve for
        server_name     blog.qwaz.io;
        charset         utf-8;

        root /home/qwaz/blog/www;
        index index.php;

        location = /favicon.ico {
                log_not_found off;
                access_log off;
        }

        location = /robots.txt {
                allow all;
                log_not_found off;
                access_log off;
        }

        access_log      /home/qwaz/blog/log/access.log;
        error_log       /home/qwaz/blog/log/error.log;

        client_max_body_size 10M;

        location / {
                try_files $uri $uri/ /index.php?$args;
        }

        location ~ \.php$ {
                include fastcgi.conf;
                fastcgi_intercept_errors on;
                fastcgi_pass unix:/var/run/php5-fpm.sock;
        }

        location ~* \.(js|css|png|jpg|jpeg|gif|ico)$ {
                expires max;
                log_not_found off;
        }
}

Mozilla SSL Configuration Generator의 설정 파일을 기본으로 다음과 같이 수정했습니다. NGINX은 1.10.2 버전, OpenSSL은 1.0.1f 버전을 사용중입니다. NGINX 버전 확인은 $ nginx -v, OpenSSL 버전 확인은 $ openssl version명령을 사용하시면 됩니다.

server {
    listen 80;
    listen [::]:80;

    server_name     blog.qwaz.io;

    # Redirect all HTTP requests to HTTPS with a 301 Moved Permanently response.
    return 301 https://$host$request_uri;
}

server {
    listen 443 ssl http2;
    listen [::]:443 ssl http2;

    # the domain name it will serve for
    server_name     blog.qwaz.io;
    charset         utf-8;

    # certs sent to the client in SERVER HELLO are concatenated in ssl_certificate
    ssl_certificate /etc/letsencrypt/live/qwaz.io/fullchain.pem;
    ssl_certificate_key /etc/letsencrypt/live/qwaz.io/privkey.pem;
    ssl_session_timeout 1d;
    ssl_session_cache shared:SSL:50m;
    ssl_session_tickets off;

    # Diffie-Hellman parameter for DHE ciphersuites, recommended 2048 bits
    ssl_dhparam /etc/letsencrypt/live/qwaz.io/dhparam.pem;

    # intermediate configuration. tweak to your needs.
    ssl_protocols TLSv1 TLSv1.1 TLSv1.2;
    ssl_ciphers 'ECDHE-ECDSA-CHACHA20-POLY1305:ECDHE-RSA-CHACHA20-POLY1305:ECDHE-ECDSA-AES128-GCM-SHA256:ECDHE-RSA-AES128-GCM-SHA256:ECDHE-ECDSA-AES256-GCM-SHA384:ECDHE-RSA-AES256-GCM-SHA384:DHE-RSA-AES128-GCM-SHA256:DHE-RSA-AES256-GCM-SHA384:ECDHE-ECDSA-AES128-SHA256:ECDHE-RSA-AES128-SHA256:ECDHE-ECDSA-AES128-SHA:ECDHE-RSA-AES256-SHA384:ECDHE-RSA-AES128-SHA:ECDHE-ECDSA-AES256-SHA384:ECDHE-ECDSA-AES256-SHA:ECDHE-RSA-AES256-SHA:DHE-RSA-AES128-SHA256:DHE-RSA-AES128-SHA:DHE-RSA-AES256-SHA256:DHE-RSA-AES256-SHA:ECDHE-ECDSA-DES-CBC3-SHA:ECDHE-RSA-DES-CBC3-SHA:EDH-RSA-DES-CBC3-SHA:AES128-GCM-SHA256:AES256-GCM-SHA384:AES128-SHA256:AES256-SHA256:AES128-SHA:AES256-SHA:DES-CBC3-SHA:!DSS';
    ssl_prefer_server_ciphers on;

    # HSTS (ngx_http_headers_module is required) (15768000 seconds = 6 months)
    add_header Strict-Transport-Security max-age=15768000;

    # OCSP Stapling ---
    # fetch OCSP records from URL in ssl_certificate and cache them
    ssl_stapling on;
    ssl_stapling_verify on;

    ## verify chain of trust of OCSP response using Root CA and Intermediate certs
    ssl_trusted_certificate /etc/letsencrypt/live/qwaz.io/chain.pem;

    resolver 8.8.8.8 8.8.4.4 valid=86400;
    resolver_timeout 5s;

    root /home/qwaz/blog/www;
    index index.php;

    location = /favicon.ico {
        log_not_found off;
        access_log off;
    }

    location = /robots.txt {
        allow all;
        log_not_found off;
        access_log off;
    }

    access_log      /home/qwaz/blog/log/access.log;
    error_log       /home/qwaz/blog/log/error.log;

    client_max_body_size 10M;

    location / {
        try_files $uri $uri/ /index.php?$args;
    }

    location ~ \.php$ {
        include fastcgi.conf;
        fastcgi_intercept_errors on;
        fastcgi_pass unix:/var/run/php5-fpm.sock;
    }

    location ~* \.(js|css|png|jpg|jpeg|gif|ico)$ {
        expires max;
        log_not_found off;
    }
}

conf 파일을 저장한 후, $ sudo service nginx restart로 NGINX를 재시작합니다. 설정 파일을 검증하려면 $ nginx -t를 이용해 문제가 있는지 확인하실 수 있습니다.

3. WordPress 설정 변경

이제 http로 접속을 시도하는 경우 https로 리디렉팅 되는 것을 확인하실 수 있을 겁니다. 사소한 남은 변경사항들을 적용합시다.

  1. WordPress의 설정 > 일반에서 WordPress 주소와 사이트 주소를 http에서 https로 변경합니다.
    https 설정 페이지
  2. 기존 글에 있던 http 링크들을 https로 업데이트 합니다. 저는 Velvet Blues Update URLs라는 플러그인을 이용했습니다.
    velvet blues update urls capture

이제 블로그에 들어가시면 기분 좋은 자물쇠 마크를 확인하실 수 있습니다!

참고한 링크

Let’s Encrypt – Getting Started
Certbot HowTo
Outsider’s Dev Story
Digital Ocean 튜토리얼

들어가며

Qualification 라운드에서 “파싱을 FSM으로 짜볼까?” 같은 이상한 생각을 하고 그렇게 풀었는데(잘못된 선택이었다), 이번 라운드에서도 “요즘 Rust 배우는 중인데 Rust로 짜볼까?” 같은 이상한 생각을 하고 그렇게 풀었다(역시 잘못된 선택이었다). 대신 Rust 숙련도가 기대했던 것보다 많이 늘었다. 이번 라운드는 Rust의 패배가 아니라 러폭도 콰즈의 패배다…

Rust 좋고 튼튼한 언어긴 한데, 확실히 C++에 비해 코드가 장황한 점은 있었다. 해커컵 치기 전에 BOJ에서 몇 문제 풀고 왔는데 남들 500 바이트 나오는 코드가 2500 바이트 나왔다. Rust로 더럽게(모든 루틴을 main에 넣는다든지) 짜면 더 줄일 수 있을 것 같긴 한데, 일단은 Rust로 PS를 계속 하려면 여러 스타일을 다양하게 테스트 해 볼 필요성이 있다고 느꼈다.

이게 다 Rust 때문이고 C++로 풀었으면 더 잘했을 거거든요! – 정신승리를 시전중

풀이

Pie Progress

각 날짜별로 파이 가격을 sorting하고, 세금까지 계산해서 파이를 k개 샀을 때 돈을 얼마나 내야 하는지를 계산한다. 다음으로 각 날짜 i가 지났을 때 파이 j개가 남도록 할 때, 최적의 전략을 선택했을 때 소모하는 금액을 DP를 이용해 계산한다.

pie_progress.rs
use std::fmt::Debug;
use std::str::{FromStr, SplitWhitespace};

trait Parser {
    fn read<T, E>(&mut self) -> T
        where T: FromStr<Err = E>,
              E: Debug;
}

impl<'a> Parser for SplitWhitespace<'a> {
    fn read<T, E>(&mut self) -> T
        where T: FromStr<Err = E>,
              E: Debug {
        self.next().expect("End of file")
            .parse::<T>().expect("Parse Error")
    }
}

//==============================================================================
use std::cmp::min;
use std::io;
use std::io::Read;

struct Input {
    num_day: i32,
    num_pie: i32,
    price: Vec<Vec<i32>>,
}

fn read_input(iter: &mut SplitWhitespace) -> Input {
    let num_day: i32 = iter.read();
    let num_pie: i32 = iter.read();
    let mut price = Vec::new();

    price.push(vec!());
    for _ in 0..num_day {
        let mut day_price = Vec::with_capacity(num_pie as usize);
        for _ in 0..num_pie {
            day_price.push(iter.read());
        }
        price.push(day_price);
    }

    Input {
        num_day: num_day,
        num_pie: num_pie,
        price: price,
    }
}

fn solve(input: Input) -> i32 {
    let num_day = input.num_day;
    let price = input.price;

    let day_size = (num_day+1) as usize;
    let mut dp = vec!(vec!(std::i32::MAX; day_size); day_size);

    dp[0][1] = 0;

    for day in 1usize..day_size {
        let mut today_price = price[day].clone();
        today_price.sort();

        let mut cost = Vec::with_capacity(day_size);
        cost.push(0);
        for (i, pie_price) in today_price.iter().enumerate() {
            let current_cost = cost[i] + pie_price + 2*(i as i32) + 1;
            cost.push(current_cost);
        }

        for stored_pie in 1usize..day_size {
            let prev_price = dp[day-1][stored_pie];
            if prev_price == std::i32::MAX { break }
            for (i, pie_cost) in cost.iter().enumerate() {
                if stored_pie-1+i >= day_size { break }
                let cell = &mut dp[day][(stored_pie-1+i) as usize];
                *cell = min(*cell, prev_price + pie_cost);
            }
        }
    }

    dp[num_day as usize][1]
}

fn main() {
    let mut buffer = String::new();
    io::stdin().read_to_string(&mut buffer).expect("Failed to read input");

    let mut iter = buffer.split_whitespace();

    let num_case: i32 = iter.read();

    for now_case in 1..(num_case+1) {
        let input = read_input(&mut iter);
        println!("Case #{}: {}", now_case, solve(input));
    }
}

Manic Moving

플로이드-와셜 알고리즘으로 각 도시들 사이의 최단 경로를 구해 두고, 1차원 DP를 돌렸다. i번째 사람의 이사 계획이 s[i]에서 e[i]로 가는 것이라고 하면, 내가 시작할 수 있는 상태는 두 가지가 있다.

  1. s[i]에서 시작(i-1번째 사람의 짐을 내려놓고 그 다음 i번째 사람의 짐을 들러 왔다)
  2. e[i-1]에서 시작(i-1번째 사람의 짐을 나르는 도중 i번째 사람의 짐을 들었다)

각 두 가지 시작 케이스에 대해 (current) -> e[i] -> s[i+1]인 경우와 (current) -> s[i+1] -> e[i]인 경우 두 가지를 처리하면 된다.

근데 틀렸다. 왜 틀렸지?

(추가) 제보를 받고 틀린 부분을 찾았다. 중복 간선이 있어서 floyd[edge.from][edge.to] = edge.gas; 이렇게 하면 안 되고 min을 씌워 주어야 한다.

manic_moving.rs
use std::fmt::Debug;
use std::str::{FromStr, SplitWhitespace};

trait Parser {
    fn read<T, E>(&mut self) -> T
        where T: FromStr<Err = E>,
              E: Debug;
}

impl<'a> Parser for SplitWhitespace<'a> {
    fn read<T, E>(&mut self) -> T
        where T: FromStr<Err = E>,
              E: Debug {
        self.next().expect("End of file")
            .parse::<T>().expect("Parse Error")
    }
}

//==============================================================================
use std::cmp::min;
use std::io;
use std::io::Read;

#[derive(Clone)]
struct Edge {
    from: usize,
    to: usize,
    gas: i32,
}

struct Customer {
    start: usize,
    dest: usize,
}

struct Input {
    num_city: usize,
    graph: Vec<Vec<Edge>>,
    customers: Vec<Customer>,
}

fn read_input(iter: &mut SplitWhitespace) -> Input {
    let num_city = iter.read();
    let num_edge = iter.read();
    let num_customers = iter.read();

    let city_size = (num_city+1) as usize;
    let mut graph = vec![vec!(); city_size];
    for _ in 1..city_size { graph.push(Vec::new()); }

    for _ in 0..num_edge {
        let a: usize = iter.read();
        let b: usize = iter.read();
        let gas: i32 = iter.read();

        graph[a].push(Edge {
            from: a,
            to: b,
            gas: gas,
        });
        graph[b].push(Edge {
            from: b,
            to: a,
            gas: gas,
        });
    }

    let mut customers = Vec::new();

    for _ in 0..num_customers {
        customers.push(Customer {
            start: iter.read(), dest: iter.read()
        })
    }

    Input {
        num_city: num_city,
        graph: graph,
        customers: customers,
    }
}

const INF: i32 = 7_0000_0000;

fn solve(input: Input) -> i32 {
    let customers = &input.customers;

    let city_size = (input.num_city+1) as usize;
    let customer_size = customers.len();

    let mut floyd = vec!(vec!(INF; city_size); city_size);
    for i in 1..city_size { floyd[i][i] = 0; }
    for v in input.graph {
        for edge in v {
            floyd[edge.from][edge.to] = edge.gas;
        }
    }
    for k in 1..city_size {
        for i in 1..city_size {
            for j in 1..city_size {
                if floyd[i][j] > floyd[i][k]+floyd[k][j] {
                    floyd[i][j] = floyd[i][k]+floyd[k][j];
                }
            }
        }
    }

    let mut load = vec![INF; customer_size];
    let mut preload = vec![INF; customer_size];

    let mut last_preload = 0;

    load[0] = floyd[1][input.customers[0].start];

    let last_index = input.customers.len()-1;
    for (i, customer) in input.customers.iter().enumerate() {
        if i == last_index { break }

        let next_start = input.customers[i+1].start;
        load[i+1] = min(
            load[i] + floyd[customer.start][customer.dest] + floyd[customer.dest][next_start],
            preload[i] + floyd[last_preload][customer.dest] + floyd[customer.dest][next_start],
        );

        preload[i+1] = min(
            load[i] + floyd[customer.start][next_start] + floyd[next_start][customer.dest],
            preload[i] + floyd[last_preload][next_start] + floyd[next_start][customer.dest],
        );

        if load[i+1] >= INF && preload[i+1] >= INF {
            return -1;
        }

        last_preload = customer.dest;
    }

    let customer = &customers[last_index];
    let ans = min(
        load[last_index] + floyd[customer.start][customer.dest],
        preload[last_index] + floyd[last_preload][customer.dest],
    );

    if ans == INF { -1 } else { ans }
}

fn main() {
    let mut buffer = String::new();
    io::stdin().read_to_string(&mut buffer).expect("Failed to read input");

    let mut iter = buffer.split_whitespace();

    let num_case: i32 = iter.read();

    for now_case in 1..(num_case+1) {
        let input = read_input(&mut iter);
        println!("Case #{}: {}", now_case, solve(input));
    }
}

Fighting the Zombies

리넘버링 해서 O(N^4)으로 사각형 두 개를 잡아서 루프를 돌며 세는 문제라고 생각했으나, 원 영역에 애매하게 걸치는 바람에 이동 후 사각형 밖에 존재하게 되어 버리는 점이 생기지 않는지를 엄밀하게 검증하기 싫어서 Beach Umbrellas 문제로 넘어갔다. 맞은 분들 솔루션 보니까 처음 생각한대로 풀면 되는 것 같다. 대회 끝나고 후기를 퇴고하면서 항상 가능하다는 걸 보였는데, 원 반지름을 무한으로 보내서 사각형이 겹치지 않는 경우 그 사이에 선을 긋고(여기까진 대회 도중 생각했다), 겹치는 경우에는 교점 두 개를 대상으로 선을 그어 공간을 분할하면 항상 사각형 두 개를 고르는 경우로 치환 가능하다는 걸 알게 되었다.

Beach Umbrellas

가장 끝에 들어갈 우산 두 개를 루프 돌리고, 나머지 빈 칸에 대해 중복조합과 순열을 이용해 열심히 계산하면 된다. 수식으로는 다음과 같고, modular inverse를 써서 계산한 뒤 2\times(n-2)!을 곱해 차례로 더하면 된다.

\,_{n+1}H_{free\_spot} = \,_{free\_spot+n}C_{free\_spot} = \,_{free\_spot+n}C_n

내 코드 시간복잡도가 O(N^2)인줄 알고 input 파일을 다운 받았는데 알고보니 O(N^3)이라서 망한 문제다. 최적화 하려면 할 수는 있는 부분이었지만 6분만에 익숙하지 않은 언어로 고치기는 불가능했다. 다행히 6분은 꽤 길기 때문에 시간 내에 답이 나올듯 말듯 진행됐는데, 30초쯤 남았을 때 95번 정도고 마지막에 최대 크기 데이터가 몰려 있는걸 보고 포기하고 코드 전시라도 하자 싶어서 그 때까지의 출력을 복사한 다음 뒤쪽을 다 0으로 채운 fuck.txt를 제출했다. 그런데 7초 남기고 100번까지 결과가 다 나왔다! 하지만 파일 포커스가 fuck.txt에 맞춰져 있어서 output.txt로 바꿔야 했고, Rust는 Working Directory의 src 폴더 안에 소스가 들어 있어서 output.txtmain.rs가 들어 있는 디렉터리가 달라 제출 할 때 폴더 이동이 필요했다. 결국 클릭이 2초쯤 느려서 제출하지 못했다. 맞은 분들 코드 보니까 O(N^3)도 종종 보이는 걸 보고 아쉬웠다.

Expire 되고 나서 20분쯤 남았는데, 제출한 게 다 맞아야 R2를 진출한다는 부담감이 있었지만 20분 안에 한 문제를 못 풀 것 같아서 씻으러 갔다. 씻고 왔더니 3번이 틀려 있었고 R2의 꿈은 저편으로…

beach_umbrellas.rs
use std::fmt::Debug;
use std::str::{FromStr, SplitWhitespace};

trait Parser {
    fn read<T, E>(&mut self) -> T
        where T: FromStr<Err = E>,
              E: Debug;
}

impl<'a> Parser for SplitWhitespace<'a> {
    fn read<T, E>(&mut self) -> T
        where T: FromStr<Err = E>,
              E: Debug {
        self.next().expect("End of file")
            .parse::<T>().expect("Parse Error")
    }
}

//==============================================================================
use std::io;
use std::io::Read;

struct Input {
    num_spot: i64,
    radius: Vec<i64>,
}

fn read_input(iter: &mut SplitWhitespace) -> Input {
    let num_umbrella = iter.read();
    let num_spot = iter.read();
    let mut radius = Vec::new();

    for _ in 0..num_umbrella {
        radius.push(iter.read());
    }

    Input {
        num_spot: num_spot,
        radius: radius,
    }
}

const MOD: i64 = 1_000_000_007;

fn modinv(val: i64) -> i64 {
    let (mut a, mut b) = (val, MOD);
    let (mut x0, mut x1) = (0, 1);
    while a > 1 {
        let q = a / b;

        let t = b;
        b = a%b;
        a = t;

        let t = x0;
        x0 = x1 - q*x0;
        x1 = t;
    }
    if x1 < 0 { x1 += MOD };
    x1
}

fn solve(input: Input) -> i64 {
    let n = input.radius.len();
    let radius = &input.radius;
    if n == 1 {
        return (input.num_spot as i64) % MOD;
    }

    let radius_sum = radius.iter().fold(0, |acc, v| acc+v*2) as i64;

    let ordering = (1i64..(n-1) as i64).fold(1i64, |acc, v| acc*v%MOD);
    let inversed = (1i64..(n+1) as i64).fold(1i64, |acc, v| acc*modinv(v)%MOD);

    let mut ans = 0i64;
    for left in 0..n {
        for right in left+1..n {
            let radius_sum = radius_sum - radius[left] - radius[right];
            let free_spot = input.num_spot-1 - radius_sum;

            if free_spot < 0 {
                continue;
            }

            // n+1 H free_spot = free_spot+n C free_spot = free_spot+n C n
            let mut delta = ordering * inversed % MOD;
            for i in 0i64..n as i64 {
                delta = delta * (free_spot+n as i64 - i) % MOD;
            }
            ans = (ans + delta*2) % MOD;
        }
    }

    ans % MOD
}

fn main() {
    let mut buffer = String::new();
    io::stdin().read_to_string(&mut buffer).expect("Failed to read input");

    let mut iter = buffer.split_whitespace();

    let num_case: i32 = iter.read();

    for now_case in 1..(num_case+1) {
        let input = read_input(&mut iter);
        println!("Case #{}: {}", now_case, solve(input));
    }
}

OpenCV와 Android Studio 버전에 따라 다른 내용이 생길 수 있으니 주의 바랍니다.

1. 안드로이드 SDK 다운로드

OpenCV 다운로드 페이지에서 OpenCV for Android를 다운 받습니다. 다운 받은 파일을 원하는 위치에 압축 해제합니다. 저는 편리한 접근을 위해 C 드라이브에 바로 압축해제 했습니다.

2. 프로젝트 생성

새롭게 프로젝트를 생성합니다. 안드로이드에서 OpenCV를 사용할 때는 OpenCV JAVA API를 사용할 수도 있고, OpenCV Native API를 JNI 형태로 사용할 수도 있습니다. 후자가 지원하는 기능이 더 많지만 추가로 설정이 필요합니다. 이 문서에서는 JNI를 사용하는 부분까지 전부 다룰 예정이지만 JAVA API 부분만 사용할 예정이라면 C++ 지원은 해제하셔도 됩니다.

다음으로 최소 SDK 버전 설정 페이지가 나오는데, API 21 이상으로 설정합니다. OpenCV 3.1 버전에서는 안드로이드의 camera2 클래스를 사용하기 때문에 최소 SDK 버전을 21 이상으로 맞출 필요가 있습니다. 이후는 기존의 안드로이드 프로젝트 생성과 동일합니다. Empty Activity를 선택했고, C++11 지원을 켠 것 이외에는 모두 기본 설정으로 진행했습니다.

CMake, NDK 등 JNI 사용에 필요한 도구들이 설치되어 있지 않아 에러 메시지가 발생하는 경우 Tools > Android > SDK Manager의 SDK Tools 탭에서 설치할 수 있습니다. 설치 후에 build.gradle 파일을 열어 프로젝트를 동기화 합니다.

3. OpenCV JAVA API 사용하기

File > New > Import Module을 클릭해 모듈을 추가합니다. Source Directory에 <OpenCV Path>/sdk/java를 입력하면 모듈 이름을 자동으로 감지합니다.

다음으로, OpenCVLibrary310/build.gradle 파일을 열어 compileSdkVersion과 buildToolsVersion을 app/build.gradle 파일과 동일하게 맞춥니다. minSdkVersion도 21로 조정합니다. 최종적으로 수정된 제 build.gradle 파일은 다음과 같으며, 사용하는 안드로이드 컴파일 SDK 버전에 따라 수치가 다를 수 있습니다. 수정 후 gradle 파일 sync 버튼을 눌러 빌드가 되는지를 확인합니다.

apply plugin: 'com.android.library'

android {
    compileSdkVersion 24
    buildToolsVersion "24.0.2"

    defaultConfig {
        minSdkVersion 21
        targetSdkVersion 21
    }

    buildTypes {
        release {
            minifyEnabled false
            proguardFiles getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.txt'
        }
    }
}

다음으로는 모듈 사이의 의존성을 설정해 주어야 합니다. 프로젝트 탐색기에서 프로젝트 폴더를 우클릭하고, Open Module Settings를 클릭한 뒤, app 모듈을 선택하고 Module Dependency로 openCVLibrary310을 추가합니다.

마지막으로, JAVA API 로드가 성공적으로 되었는지를 확인하기 위해 다음 코드를 Main Activity에 추가합니다.

    private BaseLoaderCallback mLoaderCallback = new BaseLoaderCallback(this) {
        @Override
        public void onManagerConnected(int status) {
            switch (status) {
                case LoaderCallbackInterface.SUCCESS:
                {
                    Log.i("OpenCV", "OpenCV loaded successfully");
                } break;
                default:
                {
                    super.onManagerConnected(status);
                } break;
            }
        }
    };

    @Override
    public void onResume()
    {
        super.onResume();
        OpenCVLoader.initAsync(OpenCVLoader.OPENCV_VERSION_3_1_0, this, mLoaderCallback);
    }

빌드 후 디바이스에서 실행하려고 하면, OpenCV Manager가 설치되어 있지 않다는 메시지와 함께 구글 플레이 스토어로 이동 됩니다. 그대로 설치하면 되고, 에뮬레이터 등 플레이 스토어가 존재하지 않는 환경에서는 <OpenCV Path>/apk에서 CPU 아키텍처에 맞는 apk 파일을 이용해 설치할 수도 있습니다. 이렇게 사용하는 경우 OpenCV를 사용하는 애플리케이션끼리 라이브러리 하나를 서비스 형태로 공유해서 사용할 수 있으며, OpenCV 홈페이지에서 권장하고 있는 방법입니다.

OpenCV Manager 없이 애플리케이션을 standalone 형태로 배포하고 싶은 경우에는 <OpenCV Path>/sdk/native/libs에 있는 라이브러리 파일을 사용해야 하며 여기서는 다루지 않겠습니다. OpenCV 3.1 튜토리얼Static Initialization 부분을 참고하시면 됩니다.

여기까지 완료하셨다면 빌드 후 디바이스에 설치한 뒤, Android Monitor 기능을 이용해 성공적으로 OpenCV API를 호출하는 것을 확인할 수 있습니다.

4. OpenCV JNI로 사용하기

OpenCV의 JAVA API에도 유용한 기능이 많지만, 퍼포먼스가 C++ Native Code보다 떨어지고 지원하는 기능이 적습니다. 이 때 JNI를 이용하면 기존의 C++ OpenCV API를 안드로이드 자바 코드에서 호출해 사용할 수 있습니다.

기존 튜토리얼 대다수가 안드로이드 스튜디오 하위 버전을 기준으로 작성되었고, Deprecated된 기능을 사용하고 있어 JNI 빌드 부분에서 고생을 했습니다. 구글의 안드로이드 스튜디오 가이드가 큰 도움이 되었습니다.

프로젝트를 생성할 때 C++ 지원을 활성화 하셨다면 CMakeLists.txt와 함께 native-lib.cpp 파일이 생성되셨을 겁니다. CMakeLists.txt에 다음 내용을 추가합니다. OpenCV Path는 자신의 설치 경로로 바꿔주시기 바랍니다.

set(OpenCV_DIR <OpenCV Path>/sdk/native/jni)
find_package(OpenCV REQUIRED)

그리고 target_link_libraries의 마지막에 ${OpenCV_LIBS}를 추가합니다. IDE 동기화가 성공적으로 이루어지는지 확인합니다.

<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout
    xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    xmlns:tools="http://schemas.android.com/tools"
    android:id="@+id/activity_main"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:paddingLeft="@dimen/activity_horizontal_margin"
    android:paddingRight="@dimen/activity_horizontal_margin"
    android:paddingTop="@dimen/activity_vertical_margin"
    android:paddingBottom="@dimen/activity_vertical_margin"
    tools:context="io.qwaz.androidopencv.MainActivity">

    <TextView
        android:id="@+id/sample_text"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:text="Hello World!" />

    <ImageView
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        app:srcCompat="@android:color/transparent"
        android:layout_below="@+id/sample_text"
        android:id="@+id/imageView"
        android:layout_alignParentStart="true"
        android:adjustViewBounds="false"
        android:cropToPadding="false"
        android:layout_marginTop="16dp" />
</RelativeLayout>
#include <jni.h>
#include <string>
#include <opencv2/opencv.hpp>

extern "C" {

JNIEXPORT jstring JNICALL
Java_io_qwaz_androidopencv_MainActivity_stringFromJNI(
        JNIEnv* env,
        jobject /* this */) {
    std::string hello = "Hello from C++";
    return env->NewStringUTF(hello.c_str());
}

JNIEXPORT void JNICALL
Java_io_qwaz_androidopencv_MainActivity_fillMatrixColor(
        JNIEnv* env,
        jobject,
        jlong addrMat,
        jint red,
        jint green,
        jint blue
) {
    using namespace cv;

    Mat &mat = *(Mat*)addrMat;
    mat = Scalar(red, green, blue);

    return;
}

}
package io.qwaz.androidopencv;

import android.graphics.Bitmap;
import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.util.Log;
import android.widget.ImageView;
import android.widget.TextView;

import org.opencv.android.BaseLoaderCallback;
import org.opencv.android.LoaderCallbackInterface;
import org.opencv.android.OpenCVLoader;
import org.opencv.android.Utils;
import org.opencv.core.CvType;
import org.opencv.core.Mat;

public class MainActivity extends AppCompatActivity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        // Example of a call to a native method
        TextView tv = (TextView) findViewById(R.id.sample_text);
        tv.setText(stringFromJNI());
    }

    private BaseLoaderCallback mLoaderCallback = new BaseLoaderCallback(this) {
        @Override
        public void onManagerConnected(int status) {
            switch (status) {
                case LoaderCallbackInterface.SUCCESS:
                {
                    Log.i("OpenCV", "OpenCV loaded successfully");
                    // OpenCV 초기화 이후 함수 호출
                    updateImageView();
                } break;
                default:
                {
                    super.onManagerConnected(status);
                } break;
            }
        }
    };

    @Override
    public void onResume()
    {
        super.onResume();
        OpenCVLoader.initAsync(OpenCVLoader.OPENCV_VERSION_3_1_0, this, mLoaderCallback);
    }

    private void updateImageView() {
        ImageView iv = (ImageView) findViewById(R.id.imageView);
        iv.getImageMatrix();

        Mat mat = Mat.zeros(iv.getHeight(), iv.getWidth(), CvType.CV_8UC3);
        fillMatrixColor(mat.getNativeObjAddr(), 200, 1, 80);

        Bitmap bmp = Bitmap.createBitmap(mat.cols(), mat.rows(), Bitmap.Config.ARGB_8888);
        Utils.matToBitmap(mat, bmp);

        iv.setImageBitmap(bmp);
    }

    /**
     * A native method that is implemented by the 'native-lib' native library,
     * which is packaged with this application.
     */
    public native String stringFromJNI();
    private native void fillMatrixColor(long addrMat, int red, int green, int blue);

    // Used to load the 'native-lib' library on application startup.
    static {
        System.loadLibrary("native-lib");
    }
}

screenshot_2016-10-16-16-48-29

위와 같이 ImageView에 색깔이 입혀진 것을 확인할 수 있습니다.