들어가며

대회 덕분에 오랜만에 또 문제풀이 코딩을 했다. 전부 풀긴 했는데 시간을 좀 오래 썼다. D에서 코딩 미스가 한 번 있었다. 문제풀이를 좀 쉬었을 때 풀 수 있는 문제 풀은 크게 안 변하는데, 코딩 속도나 풀이를 떠올리는 속도가 좀 줄어든 것 같다는 기분을 느꼈다.

풀이

Problem A. Oversized Pancake Flipper

같은 위치에서 두 번 뒤집는 것은 불필요하므로 왼쪽부터 하나씩 뒤집어보면 된다. O(N^2)으로 Large input이 풀리기 때문에 특별히 자료구조를 쓸 필요도 없다.

A.cpp

Problem B. Tidy Numbers

입력이 tidy한 경우 그대로 출력한다. 입력이 tidy가 아닌 경우 112333445552 형태로 증가하다가 감소하는 지점이 있을텐데, 그 감소하기 직전의 반복되는 부분(여기서는 555)의 첫 숫자를 1 낮추고, 그 뒤쪽을 전부 9로 채우면 된다.

B.cpp

Problem C. Bathroom Stalls

시뮬레이션으로 풀 수 있다. 당연히 한 명씩 넣는 건 아니고, 연속된 구간의 크기와 개수를 이용해 시뮬레이션 하면 지수적으로 수를 줄여나가면서 O(log K)만에 해결 가능하다. 한 가지 관찰이 필요한데, 반씩 줄여 나가는 방식으로 시뮬레이션 하더라도 어떤 시점에서 구간의 크기의 종류가 최대 두 종류라는 사실이다. (n) -> (a, a+1) -> (b, b+1)과 같이 연속한 두 수에 대해서만 관리하면 되고, atomic하게 처리하지 않는 경우에도 최대 네 종류만 관리하면 된다. 탐색 최대 크기가 작아 굳이 Balanced Binary Tree를 쓸 필요는 없었지만 코딩하기 귀찮아서 set을 발라서 해결했다.

C.cpp

Problem D. Fashion Show

굉장히 마음에 드는 문제였다. 독립된 두 개의 문제를 하나의 문제인 것처럼 섞어서 꼬아 놓았는데, 두 제한조건이 사실 독립이라는 것을 깨달아야 해결할 수 있다. 임의의 같은 가로줄/세로줄에 있는 두 모델을 골랐을 때 둘 중 최소 하나가 +여야 한다는 말은, 바꿔서 말하면 +가 아닌 칸은 같은 가로줄/세로줄에 최대 하나 존재할 수 있다는 말이다. 비숍 배치 문제처럼 가로세로, 대각선 조건에 대해 각각 이분매칭으로 해결한 뒤 겹치는 칸은 o로, 겹치지 않는 칸은 x와 +로 설정해 주면 된다.

D.cpp

창의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 기능이 기본 클라이언트에 포함되어 있지 않기 때문에 실행 결과 마지막에 관련된 에러 메시지가 뜰텐데, 큰 문제가 아니니 걱정하지 않으셔도 됩니다.

다음 단계는 설치된 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 파일은 다음과 같습니다.

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

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

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

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